2

有没有办法在 Haskell 中不使用从左到右构建列表++？

cons是一个恒定时间操作，我想保持代码高效。我觉得有一种通用的方法可以利用 Haskell 的懒惰来做这样的事情，但我想不出来。

现在我正在编写一个创建 Collat​​z 序列的函数，但它正在以错误的方向构建列表：

module CollatzSequence where

collatz :: (Integral a) => a -> [a] -> [a];
collatz n l
  | n <= 0    = error "Enter a starting number > 0"
collatz n []  = collatz n [n]
collatz n l@(x:_)
  | x == 1    = l
  | even x    = collatz n ((div x 2):l)
  | otherwise = collatz n ((x*3 + 1):l)

在 GHCi 中：

*CollatzSequence> collatz 13 []
[1,2,4,8,16,5,10,20,40,13]
4

2 回答 2

10

确实有一种方法可以利用懒惰。在 Haskell 中，您可以安全地在惰性数据构造函数中进行递归调用，并且不会有堆栈溢出或发散的风险。将递归调用放在构造函数中消除了对累加器的需要，并且列表中元素的顺序也将对应于它们的计算顺序：

collatz :: Integer -> [Integer]
collatz n | n <= 1 = []
collatz n = n : collatz next where
    next = if even n then div n 2 else n * 3 + 1

例如，表达式head $ collatz 10评估为head (10 : <thunk>)which 评估为10，并且尾部的 thunk 将保持未评估。另一个优点是列表节点可以在迭代列表时被垃圾收集。foldl' (+) 0 (collatz n)在恒定空间中运行，因为被访问的节点不再被程序的其余部分引用并且可以被释放。在您的原始函数中不是这种情况，因为 - 作为尾递归 - 在计算整个列表之前它不能提供任何部分结果。

于 2014-05-20T19:51:57.110 回答
4

这是你想要的？

collatz :: (Integral a) => a -> [a]
collatz n
  | n <= 0    = error "Enter a starting number > 0"
  | n == 1    = [1]
  | even n    = n : collatz (div n 2)
  | otherwise = n : collatz (n*3 + 1)
于 2014-05-20T19:51:02.187 回答