6: Yet More Haskell

CS 3040, Note 6: Yet More Haskell

Reading: Real Word Haskell, chapter 3 (section on "Pattern Matching")

List comprehensions are described in Real World Haskell, Ch. 12 (look for "List comprehensions"), noting that "generator" is essentially a way to define a value inside a list comprehension.

Pattern matching

Consider the mathematical definiton of factorial:

        fact(0) = 1
        fact(n) = n * fact(n - 1) if n > 0

Can write in Haskell using

        fact(n) = if n == 0 then 1 else n * (fact (n - 1))

More natural definition:

        :{
        fact 0 = 1
        fact n = n * fact(n - 1)
        :}

Note the :{ and }: give a block in GHCI - you wouldn't do this in a regular file
Trace fact(2)
Uses pattern matching - match value against first instance
What about fact (-1)?

More precise:

        fact 0 = 1
        fact n | n > 0 = n * fact(n - 1)

Using it on a programmer-defined type

        data AppearanceResult = HomeRun | Hit Integer | Walk | Out
        bases_reached HomeRun = 4
        bases_reached (Hit n) = n
        bases_reached Walk = 1
        bases_reached Out = 0

Using this:
```
          bases_reached (Hit 3)
  
```
- If this seems obvious, it should!
- This is the power of defining data types in Haskell - matching definitions to the real-world cases
- Close relationship between requirements and code!

Using pattern matching in a more interesting example:

map: apply operation to all elements in a list, returning list

Consider

        square x = x * x
        map square [10, 20, 30]

Can also map anonymous functions:

        add_one x = x + 1
        map add_one [1, 8, 22]
        -- but add_one is a silly function; another way to write it:
        add_one = (\x -> x + 1)
        -- test on values
        -- without defining a function:
        (\x -> x + 1)
        -- mapping:
        map (\x -> x + 1) [9, 10, 44, 12]

cubes:

        map (\num -> num * num * num) [5, 15, 25]

Lengths of strings in the list names:

        map length names

Computing the total length:

        sum (map length names)

Using map to compute total bases reached:

                map bases_reached [Hit 2, Walk, HomeRun, Out]

Adding them up and dividing by the number of at-bats:

                let tot = (sum (map bases_reached [Hit 2, Walk, HomeRun, Out]))
                   in (fromInteger tot) / 3

Related function: filter which takes a predicate and returns those items satisfying the predicate; for example, counting doubles:
```
       is_double (Hit 2) = True
       is_double _ = False

       length (filter is_double bases_reached)
```

Can also use data to create named values even when there's not an alternative:
```
        data TeamMember = Player String Double
```
representing a player with a name and some statistic such as their batting average.

There's also a newtype keyword for such type declarations, but we are not covering this; if you want to know more, see this stack overflow article.

How to represent binary search trees? Use recursion!

        data BST a = Node a (BST a) (BST a) | Tip

        inorder (Node x left right) = (inorder left) ++ [x] ++ (inorder right)
        inorder Tip = []

Use:

        Prelude> tree = Node 10 (Node 4 Tip Tip) (Node 20 (Node 15 Tip Tip) Tip)
        Prelude> inorder tree
        [4,10,15,20]

Processing lists
- Recall a list [4, 5] can be written 4 : 5 : []
- This means all lists come down to either the empty list [] or a list with at least one element: (x : rest)
- Writing sum (review sum):
```
        sum_list [] = 0
        sum_list (x : rest) = x + (sum_list rest)
```
- That is, summing an empty list gives 0, a non-empty list gives the sum of the first element plus the sum of the rest
- Note base case, recursive case very explicit!
- A definition of map:
```
        map fun [] = []
        map fun (value:rest) = (fun value):(map f rest)
```

singleton - check if a list has JUST one element:

        singleton [] = False
        singleton (x : []) = True
        singleton (y : x : rest) = False

What if leave off the [] case?

Why not use length?

        singleton xs = (length xs) == 1

How to reverse a list?
- reverse [3, 4, 8]
- reverse [4]
- reverse []
- Cases:
  - reverse of an empty list is the empty list
  - reverse of a non empty list is the reverse of the tail of the list appended with the first element
- Code:
```
        rev [] = []
        rev a:rest = (rev rest) ++ [a]
```
- Why not (rev rest): a ?
Review: pattern matching in Haskell
- Direct correspondence to algorithmic descriptions of problems
- Clear recursive list processing: [] and (x:y) cases
- Anonymous values: _

More Features

let
- Compute results: let x = a * a in x * x
- Pattern matching: let n:rest = [3, 4, 5] in n * n
where
- Like let, but after the expression:
```
        fourth x = a * a where a = x * x
```
- Useful in providing alternative ways to break down a function

List comprehensions: form new lists from existing ones:

A list of squares: [x * x | x <- nums]
square just the negatives: [x * x | x <- nums, x < 0]

Make a list of lists from a list:

        lst = [9, 10, 11, 12]
        [[x] | x <- lst]

In general, provides a good way to reorganize data

For example, processing names and ages:

        users = [("kelly", 8), ("john", 33), ("amy", 54), ("jane", 17),
                 ("zoe", 80), ("jolinda", 45)]
        -- total years:
        sum [yrs | (_, yrs) <- users]
        -- total years of those over 20:
        sum [yrs | (_, yrs) <- users, yrs > 20]
        -- items starting with 'j' and over 20:
        [(name, yrs) | (name, yrs) <- users, (head name) == 'j' && yrs > 20]

Comprehensions, let, where: additional tools to compute results