[Haskell-beginners] Appending to a list
thestonetable at gmail.com
Sat Feb 7 16:04:06 EST 2009
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 , 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?
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
> 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
> 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
> Beginners mailing list
> Beginners at haskell.org
More information about the Beginners