Haskell/Hierarchical libraries/Lists
The List datatype (see Data.List) is the fundamental data structure in Haskell — this is the basic building-block of data storage and manipulation. In computer science terms it is a singly-linked list. In the hierarchical library system the List module is stored in Data.List; but this module only contains utility functions. The definition of list itself is integral to the Haskell language.
Theory edit
A singly-linked list is a set of values in a defined order. The list can only be traversed in one direction (i.e., you cannot move back and forth through the list like tape in a cassette machine).
The list of the first 5 positive integers is written as
[ 1, 2, 3, 4, 5 ]
We can move through this list, examining and changing values, from left to right, but not in the other direction. This means that the list
[ 5, 4, 3, 2, 1 ]
is not just a trivial change in perspective from the previous list, but the result of significant computation (O(n) in the length of the list).
Definition edit
The polymorphic list datatype can be defined with the following recursive definition:
data [a] = []
| a : [a]
The "base case" for this definition is [], the empty list. In order to put something into this list, we use the (:) constructor
emptyList = [] oneElem = 1:[]
The (:) (pronounced cons) is right-associative, so that creating multi-element lists can be done like
manyElems = 1:2:3:4:5:[]
or even just
manyElems' = [1,2,3,4,5]
Basic list usage edit
Prepending edit
It's easy to hard-code lists without cons, but run-time list creation will use cons. For example, to push an argument onto a simulated stack, we would use:
push :: Arg -> [Arg] -> [Arg] push arg stack = arg:stack
Pattern-matching edit
If we want to examine the top of the stack, we would typically use a peek function. We can try pattern-matching for this.
peek :: [Arg] -> Maybe Arg peek [] = Nothing peek (a:as) = Just a
The a before the cons in the pattern matches the head of the list. The as matches the tail of the list. Since we don't actually want the tail (and it's not referenced anywhere else in the code), we can tell the compiler this explicitly, by using a wild-card match, in the form of an underscore:
peek (a:_) = Just a
List utilities edit
FIXME: is this not covered in the chapter on list manipulation?