2

就评价而言，这两者有什么区别？

为什么这“服从”（怎么说？）非严格性

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 中看到这个？

4

2 回答 2

4

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

您的尾递归函数将递归直到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在递归之前打印：它不需要检查整个输入列表来开始打印它的输出。从某种意义上说，它以“steraming”方式工作。相反，rec2只会在输入列表被完全扫描后才开始打印。

当然，在您的 Haskell 代码中没有prints，但是您可以将x : function call其作为“打印x”返回，因为在实际生成之前x，我们的函数的调用者可以使用它。（好吧，要学究起来，这取决于调用者将如何使用输出列表，但我会忽略这一点。） function call

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

于 2021-10-16T09:25:46.353 回答
3

第二种实现没有多大意义：一个名为的变量len将不包含列表的长度。因此，您需要传递这个，对于无限列表，这是行不通的，因为根本没有长度。

你可能想要产生类似的东西：

recFilter :: (a -> Bool) -> [a] -> [a]
recFilter p = go []
    where go ys [] = ys  -- (1)
          go ys (x:xs) | p x = go (ys ++ [x]) xs
                       | otherwise = go ys xs

因此，我们有一个累加器，我们将列表中的项目附加到该累加器，然后最终返回累加器。

第二种方法的问题在于，只要不返回累加器，Haskell 就需要继续递归，直到至少我们达到弱头范式 (WHNF)。这意味着如果我们用[]or对结果进行模式匹配(_:_)，我们至少需要递归直到第一种情况，因为其他情况只产生一个新的表达式，因此它不会产生我们可以在其上进行模式匹配的数据构造函数。

这与第一个过滤器形成对比，如果我们在第一种情况下进行模式匹配，[]或者(_:_)在第一种情况 (1) 或第三种情况 93) 处停止就足够了，其中表达式生成具有列表数据构造函数的对象。仅当我们需要额外的元素来进行模式匹配时，例如(_:_:_)，它才需要评估recFilter p tl第一个实现的 in case (2)：

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

有关更多信息，请参阅有关Haskell的 Wikibook 的惰性部分，该部分描述了惰性如何与thunk一起工作。

于 2021-10-16T09:13:20.150 回答