[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 [] = weave (rest []) -- goto next, check for  
>> (weave [])
>>         weave' rest ((x:xs):xss) = x : weave' (rest . (xs:)) xss
>
> The first parameter of weave' is the usual "difference list" trick  
> to allow
> efficient append with simple lists.

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:

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)

Compare this to the oh-so-useful reverseAppend function on lists  
(keeping variable names the same to make the connection obvious):

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.

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:

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

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

The use of the function trick doesn't change this fact, it just hides  
it in the closures which are constructed.

-Jan-Willem Maessen

> -- 
> Chris
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2425 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20070411/c3ffc6be/smime-0001.bin