Personal tools

How to work on lists

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(Added a section on speed considerations.)
(fix the monad-related list function section)
 
(3 intermediate revisions by 2 users not shown)
Line 1: Line 1:
== Do do I…? ==
+
[[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 10: Line 12:
   
 
:<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 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 ===
   
 
*''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 ===
   
 
*''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 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 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 91: Line 137:
 
:<hask>my_element `elem` xs</hask>
 
:<hask>my_element `elem` xs</hask>
   
== About speed ==
+
=== 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.
 
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.
Line 120: Line 166:
 
* <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 14:55, 1 August 2007

Contents

[edit] 1 How do I…?

Given any list
xs
, how do I...?

[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:
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.)

[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:
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 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:
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.

[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
f
to elements for which function
p
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 do
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
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 for
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)
  • head
    (get first element)
  • tail
    (remove first element)

[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 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 of
    list1
    )
  • 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


[edit] 3 GHC
Data.List
functions

The
Data.List
module has many functions for sorting, modifying and building lists.