Difference between revisions of "How to work on lists"
From HaskellWiki
(Added a section on speed considerations.) 
(Mention 0 based indexing) 

(4 intermediate revisions by 3 users not shown)  
Line 1:  Line 1:  
⚫  
+  [[Category:How to]] 

⚫  
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 10:  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 20:  
:<hask>xs !! n</hask> 
:<hask>xs !! n</hask> 

+  :Indexes are zero based, so <hask>[1,2,3] !! 0</hask> will result in <hask>1</hask>. 

:(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.'' 

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

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

⚫  
+  
⚫  
+  
+  === Adding === 

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

Line 34:  Line 54:  
:<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 63:  Line 85:  
: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 76:  Line 119:  
:<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 129:  
:<hask>sum xs</hask> 
:<hask>sum xs</hask> 

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

−  
⚫  
⚫  
−  
⚫  
*''Sort a list.'' 
*''Sort a list.'' 

Line 96:  Line 139:  
:<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 singlelinked lists. (Look up the term in any book on data structures.) This gives them certain speed properties which are well worth knowing. 
Haskell lists are ordinary singlelinked lists. (Look up the term in any book on data structures.) This gives them certain speed properties which are well worth knowing. 

Line 125:  Line 168:  
* <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> 

+  
+  
+  ==[[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 12:32, 15 November 2019
Contents
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 in1
.  (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.)
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
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 builtin 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 functionp
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 dosort 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 forsequence_
.
Notes about speed
Haskell lists are ordinary singlelinked 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 oflist1
) 
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.