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