# How to work on lists

### From HaskellWiki

(Difference between revisions)

(Added a section on speed considerations.) |
(Split stuff up into sections. Added monad-related stuff.) |
||

Line 2: | Line 2: | ||

Given any list <hask>xs</hask>, how do I...? |
Given any list <hask>xs</hask>, how do I...? |
||

+ | |||

+ | === Basic stuff === |
||

*''Get the size of the list.'' |
*''Get the size of the list.'' |
||

Line 10: | Line 12: | ||

:<hask>reverse xs</hask> |
:<hask>reverse xs</hask> |
||

+ | |||

+ | === Finding stuff === |
||

*''Get the Nth element out of a list.'' |
*''Get the Nth element out of a list.'' |
||

Line 17: | Line 21: | ||

:(Related: <hask>head xs</hask> returns the ''first'' element of the list.) |
:(Related: <hask>head xs</hask> returns the ''first'' element of the list.) |
||

:(Related: <hask>last xs</hask> returns the ''last'' element of the list.) |
:(Related: <hask>last xs</hask> returns the ''last'' element of the list.) |
||

+ | |||

+ | *''Get a list of all elements that match some condition.'' |
||

+ | |||

+ | :<hask>filter my_test xs</hask> |
||

+ | :(Returns everything that ''passes'' the test.) |
||

+ | |||

+ | *''Find the highest/lowest element of a list.'' |
||

+ | |||

+ | :<hask>minimum xs</hask> |
||

+ | :<hask>maximum xs</hask> |
||

+ | |||

+ | :(Works not just for numbers but ''anything'' that is a member of the <hask>Ord</hask> class. In particular, that includes characters and strings.) |
||

+ | |||

+ | === Adding stuff === |
||

*''Add an element to the start of a list.'' |
*''Add an element to the start of a list.'' |
||

Line 34: | Line 52: | ||

:<hask>list1 ++ list2</hask> |
:<hask>list1 ++ list2</hask> |
||

+ | |||

+ | === Deleting stuff === |
||

*''Delete the first N elements from a list.'' |
*''Delete the first N elements from a list.'' |
||

Line 63: | Line 83: | ||

:Haskell has a function called <hask>filter</hask> which will do this for you. Beware though: it should really be named 'select' instead. For example, <hask>filter odd xs</hask> returns a list of ''odd'' numbers. That is, it deletes everything that is ''not'' odd. |
:Haskell has a function called <hask>filter</hask> which will do this for you. Beware though: it should really be named 'select' instead. For example, <hask>filter odd xs</hask> returns a list of ''odd'' numbers. That is, it deletes everything that is ''not'' odd. |
||

+ | |||

+ | === Testing stuff === |
||

+ | |||

+ | *''Check if a list is empty.'' |
||

+ | |||

+ | :<hask>null xs</hask> |
||

+ | |||

+ | *''Find out whether any list element passes a given test.'' |
||

+ | |||

+ | :<hask>any my_test xs</hask> |
||

+ | |||

+ | *''Check whether all list elements pass a given test.'' |
||

+ | |||

+ | :<hask>all my_test xs</hask> |
||

+ | |||

+ | == Processing stuff === |
||

*''Apply a function to all list elements.'' |
*''Apply a function to all list elements.'' |
||

:<hask>map my_function xs</hask> |
:<hask>map my_function xs</hask> |
||

+ | |||

+ | *''Apply a function to just some elements of a list.'' |
||

+ | |||

+ | :Assuming you only want to apply function <hask>f</hask> to elements for which function <hask>p</hask> returns true, you can do this: |
||

+ | :<hask>map (\x -> if p x then f x else x) xs</hask> |
||

*''Convert a list of foos into a list of bars.'' |
*''Convert a list of foos into a list of bars.'' |
||

Line 76: | Line 117: | ||

:<hask>zip xs [0..]</hask> |
:<hask>zip xs [0..]</hask> |
||

:(For example, <hask>zip ['a','b','c'] [0..]</hask> gives <hask>[('a',0),('b',1),('c',2)]</hask>.) |
:(For example, <hask>zip ['a','b','c'] [0..]</hask> gives <hask>[('a',0),('b',1),('c',2)]</hask>.) |
||

+ | |||

+ | *''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: |
||

+ | :<hask>map ($ my_element) xs</hask> |
||

*''Total up a list of numbers.'' |
*''Total up a list of numbers.'' |
||

Line 81: | Line 127: | ||

:<hask>sum xs</hask> |
:<hask>sum xs</hask> |
||

− | *''Find the highest/lowest element of a list.'' |
+ | :(Related: <hask>product xs</hask> will ''multiply'' all the elements together instead of adding them.) |

− | |||

− | :<hask>minimum xs</hask> |
||

− | :<hask>maximum xs</hask> |
||

− | |||

− | :(Works not just for numbers but ''anything'' that is a member of the <hask>Ord</hask> class. In particular, that includes characters and strings.) |
||

*''Sort a list.'' |
*''Sort a list.'' |
||

Line 90: | Line 136: | ||

:<hask>my_element `elem` xs</hask> |
:<hask>my_element `elem` xs</hask> |
||

+ | |||

+ | === Lists and IO === |
||

+ | |||

+ | *''Execute a list of IO actions.'' |
||

+ | |||

+ | :If you're hard-core: <hask>map (>>=) xs</hask> |
||

+ | :If you're a normal human being: <hask>sequence xs</hask> |
||

+ | :(Note: you might need to use <hask>sequence_</hask> if the actions don't return any data.) |
||

+ | |||

+ | *''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: |
||

+ | :<hask>mapM my_action xs</hask> |
||

+ | :<hask>mapM_ my_action xs</hask> |
||

+ | :(Depending on whether you want the action to have access to the previous result or not.) |
||

== About speed == |
== About speed == |
||

Line 120: | Line 181: | ||

* <hask>filter my_test xs</hask> |
* <hask>filter my_test xs</hask> |
||

* <hask>zip my_fn list1 list2</hask> (speed depends on the ''smallest'' of the two lists - as does the size of the result list!) |
* <hask>zip my_fn list1 list2</hask> (speed depends on the ''smallest'' of the two lists - as does the size of the result list!) |
||

+ | * <hask>x `elem` xs</hask> |
||

+ | * <hask>sum xs</hask> |
||

+ | * <hask>minimum xs</hask> |
||

+ | * <hask>maximum xs</hask> |

## Revision as of 12:30, 21 January 2007

## Contents |

## 1 Do do I…?

Given any listxs

### 1.1 Basic stuff

*Get the size of the list.*

- length xs

*Turn a list backwards.*

- reverse xs

### 1.2 Finding stuff

*Get the Nth element out of a list.*

- xs !! n

- (Related: returns thehead xs
*first*element of the list.) - (Related: returns thelast xs
*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 theclass. In particular, that includes characters and strings.)Ord

### 1.3 Adding stuff

*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

### 1.4 Deleting stuff

*Delete the first N elements from a list.*

- drop n xs

- (Related: removes justtail xs
*one*element.) - (Related: removes just theinit xs
*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: removes thetail xs
*first*element.) - (Related: removes theinit xs
*last*element. Slow if the list is big.)

*Delete elements that meet some condition.*

- Haskell has a function called which will do this for you. Beware though: it should really be named 'select' instead. For example,filterreturns a list offilter odd xs
*odd*numbers. That is, it deletes everything that is*not*odd.

### 1.5 Testing stuff

*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

## 2 Processing stuff =

*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 to elements for which functionfreturns true, you can do this:p
- 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, giveszip ['a','b','c'] [0..].)[('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: willproduct xs
*multiply*all the elements together instead of adding them.)

*Sort a list.*

- You'll need to import first, but then you can just doData.List.sort xs

*Find out if some item is in a list.*

- my_element `elem` xs

### 2.1 Lists and IO

*Execute a list of IO actions.*

- If you're hard-core: map (>>=) xs
- If you're a normal human being: sequence xs
- (Note: you might need to use if the actions don't return any data.)sequence_

*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
- mapM_ my_action xs
- (Depending on whether you want the action to have access to the previous result or not.)

## 3 About speed

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.

### 3.1 Fast operations

The following operations are always 'fast':

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

### 3.2 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 asn

- xs !! n
- take n xs
- drop n xs
- splitAt n xs

xs

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