[Haskell-cafe] Weaving fun

[Bas van Dijk]

On 4/11/07, Chris Kuklewicz <haskell at list.mightyreason.com> 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