On 4/11/07, Chris Kuklewicz
... 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
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:))
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 )
The funny thing is that this definition looks very similar to my first weave. However the reverse parts are now removed because of the difference list trick:
weave :: [[a]] -> [a] weave ll = work ll [] [] where work ll = foldr f (\rst acc -> work (reverse rst) [] acc) ll f [] g = \_ acc -> reverse acc f (x:xs) g = \rst acc -> g (xs:rst) (x:acc)
Thanks, Bas van Dijk