As the bread and butter of functional programming, lists
deserve some serious attention. The standard `Prelude`

defines dozens of functions for
dealing with lists. Many of these will be indispensable tools, so it’s
important that we learn them early on.

For better or worse, this section is going to read a bit like a laundry list of functions. Why present so many functions at once? Because they are both easy to learn and absolutely ubiquitous. If we don’t have this toolbox at our fingertips, we’ll end up wasting time by reinventing simple functions that are already present in the standard libraries. So bear with us as we go through the list; the effort you’ll save will be huge.

The `Data.List`

module is the
“real” logical home of all standard list functions. The
`Prelude`

merely re-exports a large
subset of the functions exported by `Data.List`

. Several
useful functions in `Data.List`

are *not*
re-exported by the standard `Prelude`

.
As we walk through list functions in the sections that follow, we will
explicitly mention those that are only in `Data.List`

:

`ghci>`

`:module +Data.List`

Because none of these functions is complex or takes more than about three lines of Haskell to write, we’ll be brief in our descriptions of each. In fact, a quick and useful learning exercise is to write a definition of each function after you’ve read about it.

The `length`

function tells us how many elements are in a list:

`ghci>`

length :: [a] -> Int`:type length`

`ghci>`

0`length []`

`ghci>`

3`length [1,2,3]`

`ghci>`

22`length "strings are lists, too"`

If you need to determine whether a list is empty, use
the `null`

function:

`ghci>`

null :: [a] -> Bool`:type null`

`ghci>`

True`null []`

`ghci>`

False`null "plugh"`

To access the first element of a list,
use the `head`

function:

`ghci>`

head :: [a] -> a`:type head`

`ghci>`

1`head [1,2,3]`

The converse, `tail`

, returns all *but* the head of a list:

`ghci>`

tail :: [a] -> [a]`:type tail`

`ghci>`

"oo"`tail "foo"`

Another function, `last`

, returns the very last element of a list:

`ghci>`

last :: [a] -> a`:type last`

`ghci>`

'r'`last "bar"`

The converse of `last`

is `init`

, which returns a list of all but the last element of its
input:

`ghci>`

init :: [a] -> [a]`:type init`

`ghci>`

"ba"`init "bar"`

Several of the preceding functions behave poorly on empty lists, so be careful if you don’t know whether or not a list is empty. What form does their misbehavior take?

`ghci>`

*** Exception: Prelude.head: empty list`head []`

Try each of the previous functions in *ghci*. Which ones crash when given an empty
list?

When we want to use a function such
as `head`

, where we
know that it might blow up on us if we pass in an empty list, there
initially might be a strong temptation to check the length of the list
before we call `head`

. Let’s
construct an artificial example to illustrate our point:

-- file: ch04/EfficientList.hs myDumbExample xs = if length xs > 0 then head xs else 'Z'

If we’re coming from a language such as
Perl or Python, this might seem like a perfectly natural way to write
this test. Behind the scenes, Python lists are arrays, and Perl arrays
are, well, arrays. So we necessarily know how long they are, and
calling `len(foo)`

or `scalar(@foo)`

is a
perfectly natural thing to do. But as with many other things, it’s not
a good idea to blindly transplant such an assumption into
Haskell.

We’ve already seen the definition of the
list algebraic data type many times, and we know that a list doesn’t
store its own length explicitly. Thus, the only way that `length`

can operate is to walk the entire
list.

Therefore, when we care only whether or
not a list is empty, calling `length`

isn’t a good strategy. It can potentially do a lot more work
than we want, if the list we’re working with is finite. Since Haskell
lets us easily create infinite lists, a careless use of `length`

may even result in an infinite
loop.

A more appropriate function to call here
instead is `null`

, which runs in
constant time. Better yet, using `null`

makes our code indicate what property
of the list we really care about. Here are two improved ways of
expressing `myDumbExample`

:

-- file: ch04/EfficientList.hs mySmartExample xs = if not (null xs) then head xs else 'Z' myOtherExample (x:_) = x myOtherExample [] = 'Z'

Functions that have only return values defined for a
subset of valid inputs are called partial functions (calling `error`

doesn’t qualify as returning a
value!). We call functions that return valid results over their entire
input domains total functions.

It’s always a good idea to know whether a function you’re using is partial or total. Calling a partial function with an input that it can’t handle is probably the single biggest source of straightforward, avoidable bugs in Haskell programs.

Some Haskell programmers go so far as to
give partial functions names that begin with a prefix such as
`unsafe`

so that they can’t shoot themselves in the foot
accidentally.

It’s arguably a deficiency of the
standard `Prelude`

that it defines
quite a few “unsafe” partial functions, such as `head`

, without also providing
“safe” total equivalents.

Haskell’s name for the append function is `(++)`

:

`ghci>`

(++) :: [a] -> [a] -> [a]`:type (++)`

`ghci>`

"foobar"`"foo" ++ "bar"`

`ghci>`

[1,2,3]`[] ++ [1,2,3]`

`ghci>`

[True]`[True] ++ []`

The `concat`

function takes a list of lists, all of the same type, and
concatenates them into a single list:

`ghci>`

concat :: [[a]] -> [a]`:type concat`

`ghci>`

[1,2,3,4,5,6]`concat [[1,2,3], [4,5,6]]`

It removes one level of nesting:

`ghci>`

[[1,2],[3],[4],[5],[6]]`concat [[[1,2],[3]], [[4],[5],[6]]]`

`ghci>`

[1,2,3,4,5,6]`concat (concat [[[1,2],[3]], [[4],[5],[6]]])`

The `reverse`

function returns the elements of a list in reverse order:

`ghci>`

reverse :: [a] -> [a]`:type reverse`

`ghci>`

"oof"`reverse "foo"`

For lists of `Bool`

, the
`and`

and `or`

functions
generalize their two-argument cousins,```
(&&)
```

and `(||)`

,
over lists:

`ghci>`

and :: [Bool] -> Bool`:type and`

`ghci>`

False`and [True,False,True]`

`ghci>`

True`and []`

`ghci>`

or :: [Bool] -> Bool`:type or`

`ghci>`

True`or [False,False,False,True,False]`

`ghci>`

False`or []`

They have more useful cousins, `all`

and `any`

, which operate on lists of any type.
Each one takes a predicate as its first argument; `all`

returns `True`

if that
predicate succeeds on every element of the list, while `any`

returns `True`

if the
predicate succeeds on at least one element of the list:

`ghci>`

all :: (a -> Bool) -> [a] -> Bool`:type all`

`ghci>`

True`all odd [1,3,5]`

`ghci>`

False`all odd [3,1,4,1,5,9,2,6,5]`

`ghci>`

True`all odd []`

`ghci>`

any :: (a -> Bool) -> [a] -> Bool`:type any`

`ghci>`

True`any even [3,1,4,1,5,9,2,6,5]`

`ghci>`

False`any even []`

The `take`

function, which we already discussed
in Function Application, returns a sublist consisting
of the first *k* elements from a list. Its
converse, `drop`

, drops
*k* elements from the start of the list:

`ghci>`

take :: Int -> [a] -> [a]`:type take`

`ghci>`

"foo"`take 3 "foobar"`

`ghci>`

[1]`take 2 [1]`

`ghci>`

drop :: Int -> [a] -> [a]`:type drop`

`ghci>`

"zy"`drop 3 "xyzzy"`

`ghci>`

[]`drop 1 []`

The `splitAt`

function combines the functions `take`

and `drop`

, returning a pair of the input lists,
split at the given index:

`ghci>`

splitAt :: Int -> [a] -> ([a], [a])`:type splitAt`

`ghci>`

("foo","bar")`splitAt 3 "foobar"`

The `takeWhile`

and `dropWhile`

functions take predicates. `takeWhile`

takes elements from the beginning
of a list as long as the predicate returns `True`

, while
`dropWhile`

drops elements from the
list as long as the predicate returns `True`

:

`ghci>`

takeWhile :: (a -> Bool) -> [a] -> [a]`:type takeWhile`

`ghci>`

[1,3,5]`takeWhile odd [1,3,5,6,8,9,11]`

`ghci>`

dropWhile :: (a -> Bool) -> [a] -> [a]`:type dropWhile`

`ghci>`

[7,9,10,12]`dropWhile even [2,4,6,7,9,10,12]`

Just as `splitAt`

“tuples up” the
results of `take`

and `drop`

, the functions `break`

(which we already saw in Warming Up: Portably Splitting Lines of Text) and
`span`

tuple up the results of
`takeWhile`

and `dropWhile`

.

Each function takes a predicate;
`break`

consumes its input while
its predicate fails, and `span`

consumes while its predicate succeeds:

`ghci>`

span :: (a -> Bool) -> [a] -> ([a], [a])`:type span`

`ghci>`

([2,4,6],[7,9,10,11])`span even [2,4,6,7,9,10,11]`

`ghci>`

break :: (a -> Bool) -> [a] -> ([a], [a])`:type break`

`ghci>`

([1,3,5],[6,8,9,10])`break even [1,3,5,6,8,9,10]`

As we’ve already seen, the `elem`

function indicates whether a value is present in a list. It has
a companion function, `notElem`

:

`ghci>`

elem :: (Eq a) => a -> [a] -> Bool`:type elem`

`ghci>`

True`2 `elem` [5,3,2,1,1]`

`ghci>`

False`2 `notElem` [5,3,2,1,1]`

For a more general search, `filter`

takes a predicate and returns every element of the list
on which the predicate succeeds:

`ghci>`

filter :: (a -> Bool) -> [a] -> [a]`:type filter`

`ghci>`

[1,3,5,7]`filter odd [2,4,1,3,6,8,5,7]`

In `Data.List`

, three
predicates—`isPrefixOf`

, `isInfixOf`

, and `isSuffixOf`

—let us
test for the presence of sublists within a bigger list. The easiest
way to use them is with infix notation.

The `isPrefixOf`

function tells us whether its
left argument matches the beginning of its right argument:

`ghci>`

`:module +Data.List`

`ghci>`

isPrefixOf :: (Eq a) => [a] -> [a] -> Bool`:type isPrefixOf`

`ghci>`

True`"foo" `isPrefixOf` "foobar"`

`ghci>`

False`[1,2] `isPrefixOf` []`

The `isInfixOf`

function indicates whether its
left argument is a sublist of its right:

`ghci>`

`:module +Data.List`

`ghci>`

True`[2,6] `isInfixOf` [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9]`

`ghci>`

False`"funk" `isInfixOf` "sonic youth"`

The operation of `isSuffixOf`

shouldn’t need any
explanation:

`ghci>`

`:module +Data.List`

`ghci>`

True`".c" `isSuffixOf` "crashme.c"`

The `zip`

function takes two lists and “zips” them into a
single list of pairs. The resulting list is the same length as the
shorter of the two inputs:

`ghci>`

zip :: [a] -> [b] -> [(a, b)]`:type zip`

`ghci>`

[(12,'z'),(72,'i'),(93,'p')]`zip [12,72,93] "zippity"`

More useful is `zipWith`

, which takes two lists and applies a function to each pair of
elements, generating a list that is the same length as the shorter of
the two:

`ghci>`

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]`:type zipWith`

`ghci>`

[5,7,9]`zipWith (+) [1,2,3] [4,5,6]`

Haskell’s type system makes it an
interesting challenge to write functions that take variable numbers of
arguments.^{[8]} So if we want to zip three lists together, we call
`zip3`

or `zipWith3`

, and so on, up to `zip7`

and `zipWith7`

.

We’ve already encountered the standard `lines`

function and its standard counterpart `unlines`

in the sectionWarming Up: Portably Splitting Lines of Text. Notice
that `unlines`

always places a
newline on the end of its result:

`ghci>`

["foo","bar"]`lines "foo\nbar"`

`ghci>`

"foo\nbar\n"`unlines ["foo", "bar"]`

The `words`

function splits an input string on
any whitespace. Its counterpart, `unwords`

, uses a single space to join a list of words:

`ghci>`

["the","quick","brown","fox"]`words "the \r quick \t brown\n\n\nfox"`

`ghci>`

"jumps over the lazy dog"`unwords ["jumps", "over", "the", "lazy", "dog"]`

^{[8] }Unfortunately, we do not have room to address
that challenge in this book.

Start Free Trial

No credit card required