Personal tools

How to work on lists

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(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 list
xs
, how do I...?
  • 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:
head xs
returns the first element of the list.)
(Related:
last xs
returns the 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:
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.
  • 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,
zip ['a','b','c'] [0..]
gives
[('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 the
Ord
class. In particular, that includes characters and strings.)
  • 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

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)
  • head
    (get first element)
  • tail
    (remove first element)

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!)