[Haskell-beginners] Appending to a list

[Cory Knapp]

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 at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>