[Haskell-cafe] Weaving fun
Jan-Willem Maessen
jmaessen at alum.mit.edu
Wed Apr 11 09:29:10 EDT 2007
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
More information about the Haskell-Cafe
mailing list