# How to work on lists

### From HaskellWiki

(Difference between revisions)

(I'm putting this here; feel free to move it somewhere else.) |
(fix the monad-related list function section) |
||

(4 intermediate revisions by 2 users not shown) | |||

Line 1: | Line 1: | ||

+ | [[Category:How to]] |
||

+ | == How do I…? == |
||

+ | |||

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

+ | |||

+ | === Basics === |
||

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

Line 8: | Line 13: | ||

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

+ | |||

+ | === Finding / searching === |
||

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

Line 15: | Line 22: | ||

:(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 === |
||

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

Line 32: | Line 53: | ||

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

+ | |||

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

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

Line 61: | Line 84: | ||

: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 various conditions === |
||

+ | |||

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

+ | |||

+ | === Modifying the list or its elements === |
||

*''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 74: | Line 118: | ||

:<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 79: | Line 128: | ||

:<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 88: | Line 137: | ||

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

+ | |||

+ | === 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: <hask>sequence xs</hask> |
||

+ | |||

+ | :<hask>Prelude> sequence [putStr "hello ", putStrLn "world"]</hask> |
||

+ | :<hask>hello world</hask> |
||

+ | :<hask>[(),()]</hask> |
||

+ | |||

+ | :(Note: you might want to use <hask>sequence_</hask> instead, like in the above case, if your actions only return <hask>()</hask>) |
||

+ | |||

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

+ | |||

+ | :or |
||

+ | |||

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

+ | |||

+ | :where |
||

+ | |||

+ | :<hask>mapM f xs = sequence (map f xs)</hask> and similarly for <hask>sequence_</hask>. |
||

+ | |||

+ | == Notes 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!) |
||

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

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

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

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

+ | |||

+ | |||

+ | ==[[GHC]] <hask>Data.List</hask> functions== |
||

+ | The <hask>Data.List</hask> module has many functions for sorting, modifying and building lists. |

## Latest revision as of 14:55, 1 August 2007

## Contents |

## [edit] 1 How do I…?

Given any listxs

### [edit] 1.1 Basics

*Get the size of the list.*

- length xs

*Turn a list backwards.*

- reverse xs

### [edit] 1.2 Finding / searching

*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

### [edit] 1.3 Adding

*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

### [edit] 1.4 Deleting

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

### [edit] 1.5 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

### [edit] 1.6 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 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

### [edit] 1.7 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 instead, like in the above case, if your actions only returnsequence_)()

*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

- and similarly formapM f xs = sequence (map f xs).sequence_

## [edit] 2 Notes 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.

### [edit] 2.1 Fast operations

The following operations are always 'fast':

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

### [edit] 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!) - x `elem` xs
- sum xs
- minimum xs
- maximum xs

## [edit] 3 GHC Data.List functions

The Data.List

Data.List