Haskell: Concatenation vs. Prepending
Wednesday, January 14th, 2009This confused me a little until I grokked it. In Haskell, an item is not the same as a list containing the one item. (Obvious, I know, but some languages like XQuery take the opposite view).
The :
operator prepends an item to the beginning of a list. It can only be used to insert an item at the beginning of a list. It cannot be used to append an item to the end of a list. Thus x:xs
is correct but xs:x
is a syntax error. (Haskell’s design seems stuck with assumptions going all the way back to Lisp and 1950s era processors including that the singly linked list is a good implementation for the list abstract data type. This has other consequences. For instance, length
is an O(n) operation. And now that I look for it, insert into the middle of the list also seems to be missing.)
Lists are concatenated with the ++
operator, not :
.
So, to sum up:
- Use
:
to insert an item at the beginning of a list. - Use
++
to join two lists together. - To append an item to a list, insert the item into an empty list, and then concatenate the two lists together.
- More generally, to insert an item into a list at any position other than the first:
- Split the list into two sublists at the insertion point with
splitAt
. - Use
:
to prepend the new item to the second list. - Concatenate the two lists back together with
++
- Split the list into two sublists at the insertion point with
Am I missing something obvious here?