On 4/11/07, Chris Kuklewicz <[EMAIL PROTECTED]> 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
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
_______________________________________________
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
