Re: [Haskell-cafe] Weaving fun

[Jan-Willem Maessen]

On Apr 11, 2007, at 6:00 AM, Chris Kuklewicz wrote:

I have a simply recursive solution that operates efficiently...

Bas van Dijk wrote:

Hello,

For my own exercise I'm writing a function 'weave' that "weaves" a
list of lists together. For example:

 weave [[1,1,1], [2,2,2], [3,3]] ==> [1,2,3,1,2,3,1,2]
 weave [[1,1,1], [2,2], [3,3,3]] ==> [1,2,3,1,2,3,1]

Note that 'weave' stops when a list is empty.

This version of weave works without Data.Sequence or using reverse, (++), or concat:

weave :: [[a]] -> [a]
weave [] = []
weave xss = weave' id xss
  where weave' _rest ([]:_) = [] -- end when any list is empty

        weave' rest ((x:xs):xss) = x : weave' (rest . (xs:)) xss

weave' rest [] = weave (rest []) -- goto next, check for (weave [])

efficient append with simple lists.

The first parameter of weave' is the usual "difference list" trick to allow

data Rest a = Id
            | RestOfCons (Rest a) [a]

apply :: Rest a -> [[a]] -> [[a]]
apply Id = id
apply (RestOfCons rest xs) = apply rest . (xs:)

Let's add the missing argument to apply:

apply :: Rest a -> [[a]] -> [[a]]
apply Id xss = id xss
apply (RestOfCons rest xs) xss = (apply rest . (xs:)) xss

And simplify:

apply :: Rest a -> [[a]] -> [[a]]
apply Id xss = xss
apply (RestOfCons rest xs) xss = apply rest (xs:xss)



reverseAppend :: [a] -> [a] -> [a]
-- reverseAppend a b == reverse a ++ b
reverseAppend [] xss = xss
reverseAppend (xs:rest) xss = reverseAppend rest (xs:xss)

So we've simply created the solution using "reverse" in new clothing.



enqueue t (hs,ts) = (hs,t:ts)

dequeue (h:hs,ts) = (h, (hs,ts))
dequeue ([],ts)   = dequeue (reverse ts, [])



-Jan-Willem Maessen

Interestingly, in this particular case what we obtain is isomorphic to constructing and reversing a list. Let's represent the function rest by the following data type: Compare this to the oh-so-useful reverseAppend function on lists (keeping variable names the same to make the connection obvious): This shouldn't be surprising, actually. Both the "reverse" solution and the one using Data.Sequence are maintaining a queue of visited lists. In the case of the reverse solution, we represent the queue as a pair of lists: The use of the function trick doesn't change this fact, it just hides it in the closures which are constructed.

--
Chris

smime.p7s
Description: S/MIME cryptographic signature

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe