haskell - 通过递归示例理解 Haskell 中的非严格性

Question

这两者在评价方面有什么区别？

为什么这个“服从”(怎么说？)不严格

recFilter :: (a -> Bool) -> [a] -> [a]
recFilter _ [] = []
recFilter p (h:tl) = if (p h) 
  then h : recFilter p tl
  else recFilter p tl

虽然这不是？

recFilter :: (a -> Bool) -> [a] -> Int -> [a]
recFilter _ xs 0 = xs
recFilter p (h:tl) len
  | p(h)  = recFilter p (tl ++ [h]) (len-1)
  | otherwise = recFilter p tl (len-1)

是否可以非严格地编写尾递归函数？

老实说，我也不明白第一个例子的调用堆栈，因为我看不到h: 的去向。有没有办法在 ghci 中看到这个？

Answer 1

非尾递归函数粗略地消耗一部分输入(第一个元素)来产生一部分输出(好吧，如果它至少没有被过滤掉的话)。然后递归处理输入的下一部分，依此类推。

你的尾递归函数将递归直到 len 变为零，并且只有在那个点它才会输出整个结果。

考虑这个伪代码:

def rec1(p,xs):
   case xs:
      []     -> []
      (y:ys) -> if p(y): print y
                rec1(p,ys)

并将其与这个基于累加器的变体进行比较。我没有使用 len，因为我使用了一个单独的累加器参数，我假设它最初是空的。

def rec2(p,xs,acc):
   case xs:
      []     -> print acc
      (y:ys) -> if p(y): 
                   rec2(p,ys,acc++[y])
                else:
                   rec2(p,ys,acc)

rec1 打印 before 递归:它不需要检查整个输入列表来开始打印输出。从某种意义上说，它以“steraming”方式工作。相反，rec2 只会在输入列表被完全扫描后的最后开始打印。

当然，在您的 Haskell 代码中没有 print，但是您可以返回 x : function call 作为“打印 x >"，因为 x 在 function call 实际执行之前可供我们函数的调用者使用。 (好吧，迂腐地说，这取决于调用者将如何使用输出列表，但我将忽略这一点。)

因此非尾递归代码也可以在无限列表上工作。即使在有限的输入上，性能也会得到改善:如果我们调用 head (rec1 p xs)，我们只会评估 xs 直到第一个未丢弃的元素。相比之下，head (rec2 p xs) 将完全过滤整个列表 xs，即使我们不需要它。