# How to work on lists

### From HaskellWiki

(Difference between revisions)

(I'm putting this here; feel free to move it somewhere else.) |
(Added a section on speed considerations.) |
||

Line 1: | Line 1: | ||

+ | == Do do I…? == | ||

+ | |||

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

Line 93: | Line 95: | ||

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

+ | |||

+ | == 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. | ||

+ | |||

+ | === Fast operations === | ||

+ | |||

+ | The following operations are always 'fast': | ||

+ | |||

+ | * Prepend 1 element (the <hask>:</hask> operator) | ||

+ | * <hask>head</hask> (get first element) | ||

+ | * <hask>tail</hask> (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 <hask>n</hask> gets larger: | ||

+ | |||

+ | * <hask>xs !! n</hask> | ||

+ | * <hask>take n xs</hask> | ||

+ | * <hask>drop n xs</hask> | ||

+ | * <hask>splitAt n xs</hask> | ||

+ | |||

+ | 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 <hask>xs</hask> gets larger: | ||

+ | |||

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

+ | * <hask>list1 ++ list2</hask> (speed depends ''only'' on the size of <hask>list1</hask>) | ||

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

+ | * <hask>map my_fn 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!) |

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

## Contents |

## 1 Do do I…?

Given any listxs

*Get the size of the list.*

- length xs

*Turn a list backwards.*

- reverse xs

*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.)

*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

*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.

*Apply a function to all list elements.*

- map my_function 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)]

*Total up a list of numbers.*

- sum xs

*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

*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 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.

### 2.1 Fast operations

The following operations are always 'fast':

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

### 2.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!)