Or perhaps like this if you do not want to use `reverse`
and want it to be tail recursive:
collatz :: Int -> [Int]
collatz x = go id x []
where
go :: ([Int] -> [Int]) -> Int -> [Int] -> [Int]
go f 1 = f . (1:)
go f n =
if even n
then go (f . (n:)) (n `div` 2)
else go (f . (n:)) (3 * n + 1)Why would you want to not use reverse? (tail-recursion is orthogonal, and I understand not really useful in haskell unless you force strict evaluation though I may be wrong)
It increases the constant time, as reverse is O(n).
Part of the point seems to be to explain the efficient implementation of such an approach. (How would you write GHC if you didn't have it available...?) Try to translate your code into C++...
I don't write C++, but if it has linked lists then at least the first one should be trivial. The second one would probably involve function pointers.
Maybe his point was that you need to use a linked list rather than an array to get an efficient solution? Coming from a Scheme/ML/Haskell background I tend to view linked lists as much simpler than arrays!
Consider the author concluded with
> In effect, the whole idea of an array is built on being able to change part of it, and if we intend to avoid changing memory once we have put values into it, we need another kind of data structure entirely. Next week, we'll look at what such a data structure might be.
I'm assuming that a linked list is precisely the data structure he'll introduce next week. ;)
Edit: In fact, here's an even simpler solution that doesn't need to reverse the final result
It's not tail recursive (because it uses `iterate`) but it's lazy -- so if the elements of the list are consumed as they are created, the whole computation can be done in constant space as well as being fast.