An ode to lazyness

Lazy Fibonacci

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

fibs = 0 : 1 : 1 : 2 : 3 : 5 : 8 ... tail fibs = 1 : 1 : 2 : 3 : 5 : 8 : 13 ... tail (tail fibs) = 1 : 2 : 3 : 5 : 8 : 13 : 21 ... tail (tail fibs) = zipWith (+) fibs (tail fibs) -- but fibs = 0 : 1 : (tail (tail fibs)) fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Loops

newtype Co a b = Co { runCo :: a -> (b, Co' m a b) }

loop :: Co (a, d) (b, d) -> Co a b

loop (Co f) = Co g

  where 

    g b = do

    let ((c, d), c') = f (b, d) -- laziness feeds state back into a loop

    return (c, loop c')




sumToN :: Co Int Int

sumToN = loop $     id *** init 0 

                >>> arr (\(acc, i) -> (acc+i, i+1))

The loop construct, in Arrow loop for a Mealy machine. Which allows us to express a traditional loop like construct. Writing our code in terms of iterations instead of recursion, the loop combinator allows us to feed the state back into the loop.

Impossibly efficient - replaceWithMax

replaceWithMax :: [Int] -> [Int]

replaceWithMax l = ans

  where

    (ans, maximum) = f (l, head l)

    f (l:ls, m) = Control.Arrow.first (maximum:) $ f (ls, max m l)

    f x = x

Where the function above allows to effectively replace an entire list of elements with the maximum element in the list with a single pass over the list as opposed to passing over the list twice, once to find the max and count the number of elements and the next, to create the list consisting only of the maximum element.

Impossibly efficient Relabelling of bin-trees

relabel :: Tree Int -> Tree Int

relabel t = ans

  where

   (ans, vecOfLastStrip) = go (0:vecOfLastStrip) t

   go :: [Int] -> Tree Int -> (Tree Int, [Int])

   go vecOfLabels (Leaf a) = (Leaf (head vecOfLabels, a), head vecOfLabels + 1 : tail vecOfLabels)

   go vecOfLabels (Internal t a t'') = (Internal t' (head vecOfLabels, a) t''', head vecOfLabels + 1 : e'')

    where

      (t', e') = go (tail vecOfLabels) t

      (t''', e'') = go e' t''

We have some beautiful code, to can tag each node of a binary tree with an id, where the id is its position as encountered during a Breadth First Search. The way it does this is by considering the tree as a set of diagnol parallel strips of nodes. It iterates across through and across these strips keeping track of a vector of labels to be used. Each index of the vector corresponds to the same index in the strip. The vector for strip (i+1) is an increment of each index of the vector for strip i. The vector for strip 0, is the increment of each index of the vector for the last strip. The invariant of go is that it returns the relabelled tree and the increment of each index of the vector for the last strip of the tree.