Collections of things: Tuples and Lists

A first taste!

Tuples

examplePair :: (Double, Bool)
examplePair = (3.14, False)

exampleTriple :: (Bool, Int, String)
exampleTriple = (False, 42, "Answer")

exampleFunction :: (Bool, Int, String) -> Bool
exampleFunction (b,n,s) = not b && length s < n

Lists

• Also collections of things
  • All elements have the same type
  • The number of elements can vary
• If Â

  AÂ

  is a type, then Â

  [A]Â

  is the type of lists with elements of type Â

  AÂ

  .
  • For example Â

    [Integer]Â

    is a list of numbers of type Â

    IntegerÂ

    .

Lists

• The values in Â

  [A]Â

  are in either of the form
  • ‹[]›, the empty list (also called nil)
  • ‹x:xs›, where ‹x› is of type Â

    AÂ

    , and ‹xs› is of type Â

    [A]Â

    • ‹x› is the head of the list
    • ‹xs› is the tail of the list
• Which of these are in Â

  [Integer]Â

  ?
  • ‹42 : []›
  • ‹42 : 9›
  • ‹1 : (2 : [])›

List notation

• The following are different ways of writing the same list
  • ‹1:(2:(3:[]))›
  • ‹1:2:3:[]›
  • ‹[1,2,3]›
  • ‹[1,2] ++ [3]›
  • ‹[1..3]›
• The last example is special. It generates a sequence of values and only works for enumeration types. Another example is ‹['a'..'z']›.

Functions over lists 1

• Functions over lists can be defined by using pattern matching, e.g.

  • summary :: [String] -> String
    summary []    = "Nothing"
    summary [x]   = "Just "++x
    summary [x,y] = x++" and "++y
    summary _     = "Several things"

• The last equation uses the wild card pattern ‹_›

Functions over lists

Primitive recursion is the mosts common form when defining list functions from scratch

 -- doubles [3,6,10] = [6,12,20]
doubles :: [Integer] -> [Integer]
doubles [] = (...)
doubles (x:xs) = (...)

Functions over lists

• Primitive recursion is the mosts common form when defining list functions from scratch

  •  -- doubles [3,6,10] = [6,12,20]
    doubles :: [Integer] -> [Integer]
    doubles [] = []
    doubles (x:xs) = 2*x : doubles xs

• But this is a common pattern and there is a more general function that captures it.

map

 -- map f [x1,x2,...,xn] = [f x1,f x2,...,f cn]
map f [] = ...
map f (x:xs) = ...

map

•  -- map f [x1,x2,...,xn] = [f x1,f x2,...,f cn]
  map f [] = []
  map f (x:xs) = f x : map f xs

• Note: map is a predefined function

filter

Another predefined list function

• Selects elements that have a certain property:
  • Example: ‹filter even [1..9] == [2,4,6,8]›

• filter :: (a -> Bool) -> [a] -> [a]
  filter p [] = []
  filter p (x:xs) | p x       = x : filter p xs
                  | otherwise = filter p xs

List comprehensions

• An alternative notation that combines the power of map and filter
• [2*n | n <- [10..12]] [20,22,24]
• Based on notation from set theory. Also found in earlier functional languages (Hope, KRC). Also found in Python.

List comprehensions

• [3*n | n<- [10..12], even n]
  

• The list of all ‹3*n›, where n comes from ‹[10..12]› and ‹n› is even.
• Same as

• map (3*) (filter even [10..12])
  

Further example

• 

• pythag n = [(x,y,z) | x <- [1..n],
                        y <- [x..n],
                        z <- [y..n],
                        x^2 + y^2 == z^2]