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

− | + | :(Related: <hask>product xs</hask> will ''multiply'' all the elements together instead of adding them.) | |

− | + | ||

− | : | + | |

− | :<hask> | + | |

− | + | ||

− | + | ||

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

Line 95: | 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 125: | 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