Is there a way to build lists from left-to-right in Haskell without using ++?
cons is a constant time operation and I want to keep the code efficient. I feel like there's a general way to take advantage of Haskell's laziness to do something like this, but I can't think of it.
Right now I'm writing a function that creates a Collatz Sequence, but it's building the list in the wrong direction:
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)
In GHCi:
*CollatzSequence> collatz 13 []
[1,2,4,8,16,5,10,20,40,13]
There is indeed a way to take advantage of laziness. In Haskell you can safely do recursive calls inside lazy data constructors, and there will be no risk of stack overflow or divergence. Placing the recursive call inside a constructor eliminates the need for an accumulator, and the order of elements in the list will also correspond to the order in which they are computed:
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
For example, the expression head $ collatz 10 evaluates to head (10 : <thunk>) which evaluates to 10, and the thunk in the tail will stay unevaluated. Another advantage is that list nodes can be garbage collected while iterating over the list. foldl' (+) 0 (collatz n) runs in constant space, since the visited nodes are no longer referenced by the rest of the program and can be freed. This is not the case in your original function, since - being tail recursive - it cannot provide any partial result until the whole list is computed.