Re: [Haskell-cafe] Weaving fun

The fun never ends... Bas van Dijk wrote:

On 4/11/07, Chris Kuklewicz wrote:

...

... My previous weave, uses composition of (xs:) thunks instead of pairs:

...

weave :: [[a]] -> [a] weave [] = [] weave xss = helper id xss where helper :: ([[a]] -> [[a]]) -> [[a]] -> [a] helper _rest ([]:_xss) = [] -- done helper rest [] = weave (rest []) helper rest ((x:xs):xss) = x : helper (rest . (xs:)) xss

The difference list is built with id and (rest . (xs:)) and (rest [])

...

One might imagine an 'optimized' case like in weave':

...

-- helper rest ((x:[]):xss) = let yss = rest ([]:[]) -- in x : helper (const yss) xss ...

Nice! The iteration over the list can be abstracted using foldr:

...

weave :: [[a]] -> [a] weave [] = [] weave xss = foldr f (\rest -> weave $ rest []) xss id where f [] _ = \_ -> [] f (x:xs) g = \rest -> x : g (rest . (xs:))

That abstraction kills my ability to quickly see what is going on. Renaming this to weavefgh and adding type signatures:

weavefgh :: [[a]] -> [a] weavefgh [] = [] weavefgh xss = h xss id

h :: [[a]] -> ([[a]] -> [[a]]) -> [a] h = foldr f g

g :: ([[a]] -> [[a]]) -> [a] g rest = weavefgh (rest [])

f :: [a] -> (([[a]] -> [[a]]) -> [a]) -> ([[a]] -> [[a]]) -> [a] f [] _ = \_ -> [] f (x:xs) g = \rest -> x : g (rest . (xs:))

Here we can see that the foldr builds a function h which is supplied id. let xss = [x1:x1s,x2:x2s] in h xss = foldr f g [(x1:x1s),(x2:x2s)] = (x1:x1s) `f` (foldr f g [(x2:x2s)]) = f (x1:x1s) (foldr f g [(x2:x2s)]) = \rest -> x1 : (foldr f g [(x2:x2s)]) (rest . (x1s:)) h xss id = x1 : (foldr f g [(x2:x2s)]) (id . (x1s:)) demanding the next element will compute... = x1 : (f (x2:x2s) (foldr f g []) (id . (x1s:)) = x1 : (\rest -> x2 : (foldr f g []) (rest . (x2s:))) (id . (x1s:)) = x1 : x2 : (foldr f g []) (id . (x1s:) . (x2s:)) demanding the next element will compute... = x1 : x2 : g (id . (x1s:) . (x2s:)) = x1 : x2 : weavefgs ((id . (x1s:) . (x2s:)) []) = x1 : x2 : weavefgh [x1s,x2s] which now can been see to work as desired. The end of the foldr is g which calls weavefgh which, if there is still work, call h/foldr again.

This is beginning to look scary :-) To enable your last optimization you can replace the last alternative of 'f' by:

...

f (x:xs) g = \rest -> x : g (\l -> rest $ case xs of [] -> [[]] xs -> xs:l )