Nice article. I don't really understand the final point, though. Here's a simple implementation of the collatz function that returns the entire list iterated through, using a simple data structure, and that is O(I) in the number of iterations I

    collatz_vec :: Int -> [Int]
    collatz_vec = reverse . go []
      where
	go acc 1 = acc
	go acc n = go (n:acc) (if even n
		then div n 2
		else 3 * n + 1)

You simply push new values to the front of the list rather than the end, and then reverse the list all in one go at the end. Sure, you could use a fancier data type like an IntMap, but why bother when you already have linear complexity with a simple one?

Edit: In fact, here's an even simpler solution that doesn't need to reverse the final result

    collatz_vec :: Int -> [Int]
    collatz_vec = takeWhile (/= 1) . iterate step
      where
        step 1 = 1
        step n = if even n then div n 2 else 3 * n + 1

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.