A cool demonstration of complex lazy evaluation and recursive list definitions

hailstone.hs

hailstone :: [[Int]]
hailstone = [] : [1] : map (\n -> let n' = collatz n in n : (hailstone !! n')) [2..]
  
collatz n = if even then half else 3 * n + 1
    where
      (half, r) = n `quotRem` 2
      even = r == 0

{- GHCI output, _ means that part hasn't been evaluated yet
Prelude> hailstone !! 3
[3,10,5,16,8,4,2,1]
Prelude> :sprint hailstone
hailstone = [] : [1] : [2,1] : [3,10,5,16,8,4,2,1] : [4,2,1] :
            [5,16,8,4,2,1] : _ : _ : [8,4,2,1] : _ : [10,5,16,8,4,2,1] : _ :
            _ : _ : _ : _ : [16,8,4,2,1] : _
Prelude> hailstone !! 7
[7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]
Prelude> :sprint hailstone
hailstone = [] : [1] : [2,1] : [3,10,5,16,8,4,2,1] : [4,2,1] :
            [5,16,8,4,2,1] : _ :
            [7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1] : [8,4,2,1] : _ :
            [10,5,16,8,4,2,1] : [11,34,17,52,26,13,40,20,10,5,16,8,4,2,1] : _ :
            [13,40,20,10,5,16,8,4,2,1] : _ : _ : [16,8,4,2,1] :
            [17,52,26,13,40,20,10,5,16,8,4,2,1] : _ : _ :
            [20,10,5,16,8,4,2,1] : _ :
            [22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1] : _ : _ : _ :
            [26,13,40,20,10,5,16,8,4,2,1] : _ : _ : _ : _ : _ : _ : _ :
            [34,17,52,26,13,40,20,10,5,16,8,4,2,1] : _ : _ : _ : _ : _ :
            [40,20,10,5,16,8,4,2,1] : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ :
            _ : [52,26,13,40,20,10,5,16,8,4,2,1] : _
:}

Another run showing that you can partially evaluate the individual elements of hailstone.

Prelude> take 3 (hailstone !! 7)
[7,22,11]
Prelude> :sprint hailstone
hailstone = [] : _ : _ : _ : _ : _ : _ : (7 : 22 : 11 : _) : _ :
            _ : _ : (11 : _) : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ :
            (22 : 11 : _) : _