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

Question

有没有办法在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]

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,并且尾部的thunk将保持未评估状态.另一个优点是列表节点可以在迭代列表时进行垃圾收集.foldl' (+) 0 (collatz n)在恒定的空间中运行,因为访问的节点不再被程序的其余部分引用并且可以被释放.原始函数不是这种情况,因为 - 尾递归 - 在计算整个列表之前,它不能提供任何部分结果.