In general, you want to be building a list "from the front". Consider the list constructor-- x:xs is a list, when x is an element, and xs is a list; on the other hand, xs:x will give you a type error. I think the lisp syntax is a bit more elucidating; in lisp, you use "cons" to create a pair e.g. (cons 1 2), and to create a list, you make a pair whose last element is empty, and cons elements to the front. E.g. (cons 2 '()) gives you the list '(2), which is lisp for [2], and (cons 1 (cons 2 (cons 3 (cons 4 '() ) ) ) ) gives you '(1 2 3 4)-- lisp for [1,2,3,4]). In order to add the end of the list, you need to unravel the whole list, (replacing the '() at the end with "(cons 5 '())" ). On the other hand, adding to the front requires you to just cons another value to it. Haskell works the same way, but it uses an infix operator [1,2,3,4] = 1:2:3:4:[] = 1 : (2 : (3 : (4 : [] ) ) ). So appending to the list is expensive, while adding to the front just requires x : list. Obviously, if you're actually concatenating two lists, you need to filter through one of them anyway, but if you're just putting an element on, it's better to put it on the front. Normally, this is practically accomplished by making recursive procedures which work towards the end of the list. For example, map will apply a function to the first element and then map to the rest: map f (x:xs) = (f x) : (map f xs) map _ [] = [] So, you use your list as a stack-- pulling everything off, and then placing it all back on with the function applied. Does that help, or did I miss the point? Cheers, Cory Knapp Francesco Bochicchio wrote:
Hi all,
in my haskell exercises I often build list by appending values at the end. But I read somewhere that in haskell this is inefficient since there is no 'pointer to the tail of the list'. I've also seen some example of recursive functions which build the list tail-first and then in the base case of the recursion returns the reverse of the accumulated results, counting on the fact that in haskell 'reverse list' just means 'consume the list from the tail'.
Just out of curiosity (I have no need to speed up my little programs with which I try to teach myself some haskell): is this a consolidated pattern? And are append really expensive?
Ciao ------- FB ------------------------------------------------------------------------
_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners