Haskell: Concatenation vs. Prepending
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?
