Lazy Fibonacci
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.
loop :: Co (a, d) (b, d) -> Co a bloop (Co f) = Co gwhereg b = dolet ((c, d), c') = f (b, d) -- laziness feeds state back into a loopreturn (c, loop c')sumToN :: Co Int IntsumToN = 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 = answhere(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
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.relabel :: Tree Int -> Tree Intrelabel t = answhere(ans, vecOfLastStrip) = go (0:vecOfLastStrip) tgo :: [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''
