3 ms·
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 th
by crntaylor 13y ago
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.
- wging 13y agoPart 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++...
- crntaylor 13y agoI 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!
- jfarmer 13y agoConsider 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. ;)
- secretguy 13y agoOr 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)