Finding long Collatz sequences in Haskell

Today, I am playing with Collatz sequences in Haskell ...

Here is my code:

collatzLength :: Int -> Integer -> Int
collatzLength count 1 = count
collatzLength count n = collatzLength (count+1) $ if n `mod` 2 == 0 then n `div` 2 else 3*n+1

main =
    print (collatzLength 1 (10^10000 + 1))

What I would like to do is to iterate infinitely on [1, 3 ..]. Each time a new maximum Collatz length is found, I want to display it on screen, and continue. I have no idea on how to do that in Haskell, as I have to keep and update the maximum length value somewhere.

Solution

Use map and an infinite range

main = print $ map (collatzLength 1) [1,3..]

or use explicit recursion

main :: IO ()
main = loop 1

loop :: Int -> IO ()
loop n = do
   print (collatzLength 1 n)
   loop (n+2)

The latter approach lets you have a finer control on the loop.

Note that every loop computes the sequence number from scratch, without exploiting previously computed results. For a more efficient approach, look up memoization (not to be confused with "memorization"). Such techniques allow the program to "remember" the result of previously computed recursive calls, so that new calls do not have to recompute the same value.

If you want to keep the maximum of all returned values, you can use

loop :: Int -> Int -> IO ()
loop n prevMax = do
   let m = collatzLength 1 n
   putStrLn $ "collatzLength 1 " ++ show n ++ " = " ++ show m
   let nextMax = max prevMax m
   putStrLn $ "current maximum = " ++ show nextMax
   loop (n+2) nextMax

But I do not want to print all the results. Only the lengths that are higher than the "current" maximum length.

Then, generate a list of those "higher" points:

-- Assumes a list of positive numbers.
-- Returns the list of those elements which are larger than all the
-- previous ones.
highPoints :: [Int] -> [Int]
highPoints xs = go 0 xs
   where
   go :: Int -> [Int] -> [Int]
   go _          []     = []
   go currentMax (n:ns) | n > currentMax = n : go n ns
                        | otherwise      = go currentMax ns

main :: IO ()
main = do 
   let collatzSequence :: [Int]
       collatzSequence = map (collatzLength 1) [1,3..]
   print (highPoints collatzSequence)