# How to work on lists

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

## How do I…?

Given any list `xs`, how do I...?

### Basics

• Get the size of the list.
`length xs`
• Turn a list backwards.
`reverse xs`

### Finding / searching

• Get the Nth element out of a list.
`xs !! n`
Indexes are zero based, so `[1,2,3] !! 0` will result in `1`.
(Related: `head xs` returns the first element of the list.)
(Related: `last xs` returns the last element of the list.)
• Get a list of all elements that match some condition.
`filter my_test xs`
(Returns everything that passes the test.)
• Find the highest/lowest element of a list.
`minimum xs`
`maximum xs`
(Works not just for numbers but anything that is a member of the `Ord` class. In particular, that includes characters and strings.)

• Add an element to the start of a list.
`new_element : xs`
• Add an element to the end of a list.
`xs ++ [new_element]`
• Insert an element into the middle of a list.
Generally, you will have to split the list into two smaller lists, put the new element to in the middle, and then join everything back together. For example:
`let (ys,zs) = splitAt n xs in ys ++ [new_element] ++ zs`
• Join two lists together.
`list1 ++ list2`

### Deleting

• Delete the first N elements from a list.
`drop n xs`
(Related: `tail xs` removes just one element.)
(Related: `init xs` removes just the last element.)
• Make a new list containing just the first N elements from an existing list.
`take n xs`
• Split a list into two smaller lists (at the Nth position).
`splitAt n xs`
(Returns a tuple of two lists.)
• Delete the just Nth element of a list.
This is tricky. AFAIK, there is no built-in function that does this. You have to split the list in two, remove the element from one list, and then join them back together, like this:
`let (ys,zs) = splitAt n xs in ys ++ (tail zs)`
(Related: `tail xs` removes the first element.)
(Related: `init xs` removes the last element. Slow if the list is big.)
• Delete elements that meet some condition.
Haskell has a function called `filter` which will do this for you. Beware though: it should really be named 'select' instead. For example, `filter odd xs` returns a list of odd numbers. That is, it deletes everything that is not odd.

### Testing various conditions

• Check if a list is empty.
`null xs`
• Find out whether any list element passes a given test.
`any my_test xs`
• Check whether all list elements pass a given test.
`all my_test xs`

### Modifying the list or its elements

• Apply a function to all list elements.
`map my_function xs`
• Apply a function to just some elements of a list.
Assuming you only want to apply function `f` to elements for which function `p` returns true, you can do this:
`map (\x -> if p x then f x else x) xs`
• Convert a list of foos into a list of bars.
Find or write a function to convert foo into bar, and then apply it to the whole list using `map`.
• Number the elements of a list (so I can process each one differently according to its position).
`zip xs [0..]`
(For example, `zip ['a','b','c'] [0..]` gives `[('a',0),('b',1),('c',2)]`.)
• Apply a list of functions to a single element to get a list of results.
It's not in the book, but it's easy when you know how:
`map (\$ my_element) xs`
• Total up a list of numbers.
`sum xs`
(Related: `product xs` will multiply all the elements together instead of adding them.)
• Sort a list.
You'll need to import `Data.List` first, but then you can just do `sort xs`.
• Find out if some item is in a list.
`my_element `elem` xs`

### Lists and IO

• Execute a list of IO actions.
Turn a list of IO actions into one IO action that returns a list of results: `sequence xs`
`Prelude> sequence [putStr "hello ", putStrLn "world"]`
`hello world`
`[(),()]`
(Note: you might want to use `sequence_` instead, like in the above case, if your actions only return `()`)
• Execute an IO action on each element of a list.
You could map the IO function over your list (resulting in a list of actions) and then perform them using the trick above. But it's much simpler to do this:
`mapM my_action xs`
or
`mapM_ my_action xs`
where
`mapM f xs = sequence (map f xs)` and similarly for `sequence_`.

Haskell lists are ordinary single-linked lists. (Look up the term in any book on data structures.) This gives them certain speed properties which are well worth knowing.

### Fast operations

The following operations are always 'fast':

• Prepend 1 element (the `:` operator)
• `head` (get first element)
• `tail` (remove first element)

### Slower operations

Any function that does something with the Nth element or the first N elements generally gets slower as N increases. The following all slow down as `n` gets larger:

• `xs !! n`
• `take n xs`
• `drop n xs`
• `splitAt n xs`

Any function which needs to process the entire list obviously gets slower as the list gets bigger. The following all slow down as the list `xs` gets larger:

• `length xs`
• `list1 ++ list2` (speed depends only on the size of `list1`)
• `last xs`
• `map my_fn xs`
• `filter my_test xs`
• `zip my_fn list1 list2` (speed depends on the smallest of the two lists - as does the size of the result list!)
• `x `elem` xs`
• `sum xs`
• `minimum xs`
• `maximum xs`

## GHC `Data.List` functions

The `Data.List` module has many functions for sorting, modifying and building lists.