在没有++的情况下在Haskell中从左到右构建列表

Question

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

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

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

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]

Answer 1

确实有一种方法可以利用懒惰。在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>)，而 10 的计算结果将保持未计算状态。另一个优点是，在迭代列表时可以对列表节点进行垃圾回收。 foldl' (+) 0 (collatz n)在常量空间中运行，因为访问的节点不再被程序的其余部分引用，并且可以释放。原始函数中的情况并非如此，因为 - 尾递归 - 在计算整个列表之前，它无法提供任何部分结果。

Answer 2

这是你要找的吗？

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)