[Haskell-cafe] Weaving fun

Chris Kuklewicz haskell at list.mightyreason.com
Wed Apr 11 17:04:00 EDT 2007


You are correct, my weave did hide the list in the explicit composition of closure(s).
I can be even more declarative and let the closure construction be implicit in weave' below...
(and this message should be literate Haskell)

weave' uses a fixed point and pairs to tie the knot declaratively:

> import Data.List

> weave' :: [[a]] -> [a]
> weave' [] = []
> weave' xss = let (ans,rest) = helper rest xss in ans
>   where helper :: [[a]] -> [[a]] -> ([a],[[a]])
>         helper _rest ([]:_xss) = ([],[])
>         helper rest  [] = (weave' rest,[])
>         helper rest ((x:xs):xss) = let (ans,rest') = helper rest xss
>                                    in (x:ans,xs:rest')

The next case might be an optimization, since we know that nothing
after the [] will be used in the next pass:

> --       helper rest ((x:[]):xss) = let (ans,_) = helper rest xss
> --                                  in (x:ans,[]:[])

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

Some simple tests such that check should be True

> check = (ans == test 20 weave) && (ans == test 20 weave')
>
> test n w = map (take n . w) $
>             [] :
>             [[]] :
>             [[],[]] :
>             [[1..10]] :
>             [[1,3..10],[2,4..10]] :
>             [[1..],[11..15],[301..],[11..15]] :
>             [[1..],[11..15],[301..]] :
>             [[1..],[11..15],[301..],[]] :
>             [[1..],[11..15],[],[301..]] :
>             [[1..],[],[11..15],[],[301..]] :
>             [[],[1..],[11..15],[],[301..]] :
>             testInf :
>             []
> testInf = map enumFrom [1..]
> ans = [[],[],[],[1,2,3,4,5,6,7,8,9,10],[1,2,3,4,5,6,7,8,9,10]
>       ,[1,11,301,11,2,12,302,12,3,13,303,13,4,14,304,14,5,15,305,15]
>       ,[1,11,301,2,12,302,3,13,303,4,14,304,5,15,305,6]
>       ,[1,11,301],[1,11],[1],[]
>       ,[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]]



More information about the Haskell-Cafe mailing list