RE: Assembling lists start-to-end
sorry, forgot to send this to the list: Another way to do it is to use accumulating lists. As a simple example, let's consider: > myf p l = reverse (filter p l) (myf Char.isUpper "Hello Cruel World" ==> "WCH") that is, it returns elements of a list which match the predicate in reverse order. we could write this very slowly using explicit recursion as: > myf2 p [] = [] > myf2 p (x:xs) >| p x = myf2 p xs ++ [x] >| otherwise = myf2 p xs but traversing the recusive list is very slow. we might induce tail recursion in something like: > myf3 p l = myf3' l [] > where > myf3' [] acc = acc > myf3' (x:xs) acc = myf3' xs (x:acc) Now, the accumulator 'acc' holds the value we're going to return at the end. So this is pretty much what you want. Now, suppose we're just doing filter without the reversing, but we still want it to be tail recursive. We might think we have to write: > myf4 p l = reverse (myf3' l []) (where myf3' is as before) this is not so. We can have fun with function composition. What we do is change the accumulator from a list to a function from a list to a list. > myf4 p l = myf4' l id > where > myf4' [] acc = acc [] > myf4' (x:xs) acc > | p x= myf4' xs (\l -> acc (x:l)) > | otherwise = myf4' xs acc here, we start out the accumulator as the identity function. to add an element to it, we make a function which takes the old list, adds 'x' to the front and then applies the accumulator. in the base case, we simply apply the empty list to the accumulator function. the second-to-last line can be rewritten a bit more conveniently as: > | p x= myf4' xs (acc . (x:)) the neat thing about this is that you can easily change the way the list goes. as it is, we have filter, but if we flip the order for (.), as in: > | p x= myf4' xs ((x:) . acc) then we get (reverse . filter). HTH - Hal -- Hal Daume III | [EMAIL PROTECTED] "Arrest this man, he talks in maths." | www.isi.edu/~hdaume > -Original Message- > From: [EMAIL PROTECTED] > [mailto:[EMAIL PROTECTED] On Behalf Of Mark Carroll > Sent: Saturday, June 21, 2003 5:39 AM > To: [EMAIL PROTECTED] > Subject: Assembling lists start-to-end > > > I am assembling a list from start to end. I can add elements > to the end > with "previous ++ [current]" or I can add them with "current > : previous" > and reverse it when I'm done. Or, maybe I should use some other data > structure. (I don't know the length in advance.) Any thoughts? > > -- Mark > > ___ > Haskell-Cafe mailing list > [EMAIL PROTECTED] > http://www.haskell.org/mailman/listinfo/haskell-cafe > ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Assembling lists start-to-end
On Sat, 21 Jun 2003, Wolfgang Jeltsch wrote: > On Saturday, 2003-06-21, 14:38, CEST, Mark Carroll wrote: > > I am assembling a list from start to end. I can add elements to the end with > > "previous ++ [current]" or I can add them with "current : previous" and > > reverse it when I'm done. Or, maybe I should use some other data structure. > > (I don't know the length in advance.) Any thoughts? [snip] > adding with "current : previous" and finally reversing the list seems good > since the whole process takes linear time whereas adding to the end with > "previous ++ [current]" would take quadratic time. Another thing to consider is whether the list is both likely to be very, very long & you will be processing the list in a way in which groups of items at the top of the list are dealt with in small groups, so that lazy evaluation would make it desirable not to have to fully construct the list before processing any of it (and potentially removed, thus reducing memory & hence requiring less garbage collecting). In this case, it _may_ be better to build it up in a lazy-evaluation friendly way using functions f,g,... of the form f args=current:g args' where (current,args')= However, it may (a) not be possible to build it up that way and (b) depending on the size of the datastructures in args, this approach may make memory usage worse by requiring these big structures to be kept for longer whereas if the list were built all at once it could be garbage collected much quicker. Just a random thought basically saying `it sometimes of depends what you're going to do with the list' ___cheers,_dave_ www.cs.bris.ac.uk/~tweed/ | `It's no good going home to practise email:[EMAIL PROTECTED] | a Special Outdoor Song which Has To Be work tel:(0117) 954-5250 | Sung In The Snow' -- Winnie the Pooh ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Assembling lists start-to-end
On Saturday, 2003-06-21, 14:38, CEST, Mark Carroll wrote: > I am assembling a list from start to end. I can add elements to the end with > "previous ++ [current]" or I can add them with "current : previous" and > reverse it when I'm done. Or, maybe I should use some other data structure. > (I don't know the length in advance.) Any thoughts? > > -- Mark Hi, adding with "current : previous" and finally reversing the list seems good since the whole process takes linear time whereas adding to the end with "previous ++ [current]" would take quadratic time. Wolfgang ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Assembling lists start-to-end
I am assembling a list from start to end. I can add elements to the end with "previous ++ [current]" or I can add them with "current : previous" and reverse it when I'm done. Or, maybe I should use some other data structure. (I don't know the length in advance.) Any thoughts? -- Mark ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
