% Notes week of 17 Sep
Assignment 1 tips
==================
I'll have the Assignment 1 solutions published in a few more days.
- Q1 volumeSphere, Q2 quadratic: should be straightforward.
- Q3 temperature conversion: you need an identifier for the function
parameter on the left side of the equals. Must start with a
lowercase letter. If you are getting failures, click through to
figure out why. There could be compiler errors that offer useful
hints.
- Q4 Cartesian: just formulas, but you need to find them.
- Q5 powerFast: you might get this to pass tests by defining square
and then renaming powerSlow. But I will deduct a couple of points
for that because it doesn't take advantage of even exponents to
speed up the calculation.
- Q6 primes: One issue I saw here, that's also common in C/C++
programs, is something like:
```hs
x /? y
| x `mod` y == 0 = True
| otherwise = False
```
This works, but it's much more verbose than needed. If you're
returning True if an expression is true, and False otherwise, then
you can just return the (Boolean) value of the expression:
```hs
x /? y = x `mod` y == 0
```
List constructors
===============
A single colon `(:)` is an operator for constructing a node in a
linked list. The other constructor is an empty list, which is just
designated as `[]`.
The list syntax with brackets and commas is really just a short-hand
for applying these constructors:
```
[1,2,3,4] ↪
(1:(2:(3:(4:[])))) ↪
1:2:3:4:[]
```
With or without the parentheses, those expressions are the same
because `(:)` is **right-associative.** Another way to think of this is
that it builds the list nodes from back to front.
![Each box is produced by one application of the list constructor `(:)`.](list1234.png)
- List append `(++)`
- `head`, `tail`
- `take`, `drop`
List patterns
===============
When defining a function, instead of just a plain parameter name we an
use a **pattern**. We saw this already for the simple case of pairs.
Instead of defining:
```hs
euclidean p1 p2 = ...
```
and using `fst p1` for the X value and `snd p1` for the Y, we can
replace each simple variable name with a pair:
```hs
euclidean (x1,y1) (x2,y2)
```
This syntax is normally used for *constructing* pairs, but here it is
for *destructing* (also known as *matching*) pairs.
We can use the list constructor similarly. Consider this definition:
> flarn (a:b:c) = a + b
Remember when we write `a:b:c`, it is grouped from the right
`(a:(b:c))`. This is a pattern composed of list constructors. Thus we
must call the function with a list argument. For example:
```
flarn [3,5,9,2]
```
To see how this argument will match the pattern, rewrite it using the
list constructor and compare to the structure of the pattern:
```
(3:(5:(9:(2:[]))))
(a:(b:c ))
```
So the pattern binds the parameter variables as follows:
- `a = 3`
- `b = 5`
- `c = 9:2:[] = [9,2]`
Perform those replacements in the right-hand side of `flarn` and
you can derive the result:
```
flarn [3,5,9,2] ↪ 3+5 ↪ 8
```
It may happen that the pattern *does not* match. Here's an example:
```
flarn [8] ↪
flarn (8:[])
```
Match that argument against the pattern:
```
(8:[] )
(a:(b:c))
```
and you realize that we're trying to match the empty list `[]` with a
list constructor `(b:c)`. These do not match, so the call produces an
error:
```
*** Exception: Non-exhaustive patterns in function flarn
```
You can define a function with multiple patterns (much like a function
with multiple guards) by specifying separate equations with the same
function name.
Here are some example functions, with derivations of function calls
beneath them.
> flub (a:b:c:d) = sum d + a - b + c
> flub (a:b) = sum b + a
> flub [] = 99
There are three clauses here, each with different patterns. The clause
pattern are tried in order, and the first to match is executed. If
none of the clauses match, then it throws the "Non-exhaustive
patterns" error.
```
flub [9,1,5,2] ↪
-- First clause matches with a=9, b=1, c=5, d=[2]
sum [2] + 9 - 1 + 5 ↪
2 + 9 - 1 + 5 ↪
11 - 1 + 5 ↪
10 + 5 ↪
15
```
```
flub [9,1,5] ↪
-- First clause still matches, with a=9, b=1 c=5, d=[]
-- (It's okay if a tail in a pattern is the empty list.)
sum [] + 9 - 1 + 5 ↪
-- Sum of an empty list is zero.
0 + 9 - 1 + 5 ↪
9 - 1 + 5 ↪
8 + 5 ↪
13
```
```
flub [9,1] ↪
-- This time, first clause doesn't match because c:d doesn't match []
-- Second clause matches with a=9, b=[1]
sum [1] + 9 ↪
1 + 9 ↪
10
```
```
flub [9] ↪
-- Again, second clause matches with a=9, b=[]
sum [] + 9 ↪
0 + 9 ↪
9
```
```
flub [] ↪
-- Now first and second clauses don't match, but
-- third clause does. No variables bound by that match.
99
```
Let's try another function. This one returns a list, and doesn't do
arithmetic so it can operate on list of any type (including strings).
> traal (x:xs) = x : x : traal xs
> traal [] = []
```
traal "cat" ↪
traal ('c':'a':'t':[]) ↪
-- First clause matches with x = 'c', xs = 'a':'t':[] = "at"
'c' : 'c' : traal "at" ↪
-- First clause matches with x = 'a', xs = 't':[] = "t"
'c' : 'c' : 'a' : 'a' : traal "t" ↪
-- First clause matches with x = 't', xs = [] = ""
'c' : 'c' : 'a' : 'a' : 't' : 't' : traal [] ↪
-- First clause doesn't match, but second does
'c' : 'c' : 'a' : 'a' : 't' : 't' : [] ↪
-- The rest builds up list from back to front
'c' : 'c' : 'a' : 'a' : 't' : "t" ↪
'c' : 'c' : 'a' : 'a' : "tt" ↪
'c' : 'c' : 'a' : "att" ↪
'c' : 'c' : "aatt" ↪
'c' : "caatt" ↪
"ccaatt"
```
> phaal (x:y:xs) = x+y : phaal xs
> phaal [x] = [1]
> phaal [] = []
Implementing basic list operations
========================
Many list operations, such as `map`, `filter`, and append (`++`) are
built-in to Haskell (provided by the standard 'prelude'), but it can
be instructive to try to implement those ourselves. So here are
versions of `++`, `map`, and `filter` along with derivations that trace
their behavior. They all work by recursively processing a list,
handling the head element and then using a recursive call to provide
the tail.
Append
------------
The append operator (`++`) just concatenates two lists. It can be
implemented like this:
> myAppend xs [] = []
> myAppend [] ys = ys
> myAppend (x:xs) ys = x : myAppend xs ys
```
myAppend [3,5] [2,7,9] ↪
-- Neither list empty, so matches last clause
-- with x=3, xs=[5], ys=[2,7,9]
3 : myAppend [5] [2,7,9] ↪
-- Last clause with x=5, xs=[], ys=[2,7,9]
3 : 5 : myAppend [] [2,7,9] ↪
-- Second clause, with ys=[2,7,9]
3 : 5 : [2,7,9] ↪
3 : [5,2,7,9] ↪
[3,5,2,7,9]
```
The first clause of `myAppend`, which requires that the right list is
empty, is not actually necessary. It's just an **optimization**. We'd get
the same result without it, but have to do a lot more work.
```
myAppend [3,5] [] ↪
-- Using first clause, this is finished immediately.
-- But if we didn't have that, it would match last clause
-- with x=3, xs=[5], ys=[]
3 : myAppend [5] [] ↪
-- Again, without first clause it would match last
-- with x=5, xs=[], ys=[]
3 : 5 : myAppend [] [] ↪
-- Now it matches second clause
3 : 5 : [] ↪
3 : [5] ↪
[3,5]
```
Map
------------
The `map` function applies a function to each element of a list, and
returns a list of the results.
> myMap f [] = []
> myMap f (x:xs) = f x : myMap f xs
> square x = x * x
```
myMap square [3,7,5] ↪
-- Matches second clause with f=square, x=3, xs=[7,5]
square 3 : myMap square [7,5] ↪
-- Matches second clause with f=square, x=7, xs=[5]
square 3 : square 7 : myMap square [5] ↪
-- Matches second clause with f=square, x=5, xs=[]
square 3 : square 7 : square 5 : myMap square [] ↪
-- Matches first clause
square 3 : square 7 : square 5 : [] ↪
square 3 : square 7 : [25] ↪
square 3 : [49,25] ↪
[9,49,25]
```
Filter
------------
The `filter` function applies a Boolean function to each element of a
list and keeps only those elements for which the function returned
`True`. We write this one with the usual two clauses for the empty and
non-empty list, but then the non-empty case uses guards to check the
Boolean result.
> myFilter f [] = []
> myFilter f (x:xs)
> | f x = x : myFilter f xs
> | otherwise = myFilter f xs
```
myFilter even [2,3,4] ↪
-- Matches second case with f=even, x=2, xs=[3,4]
-- so check guard expression: even 2 ↪ True
2 : myFilter even [3,4] ↪
-- Matches second case with f=even, x=3, xs=[4]
-- so check guard expression: even 3 ↪ False
-- thus it uses the otherwise case and ignores x.
2 : myFilter even [4] ↪
-- Matches second case with f=even, x=4, xs=[]
-- so check guard expression: even 4 ↪ True
2 : 4 : myFilter even [] ↪
-- Matches first case
2 : 4 : [] ↪
2 : [4] ↪
[2,4]
```
Structure sharing and garbage collection
========================
> ws = [3,8]
> xs = 7 : 5 : ws
> ys = 6 : tail xs
> zs = ws ++ ws
![Because each list node is immutable once created, multiple lists can have tails in common](list-share.png)
List comprehensions
========================
This is a syntax for creating, mapping, and filtering lists. Read the
following as "the list of squares of x, where x comes from `[2..5]`".
```
ghci> [square x | x <- [2..5]]
[4,9,16,25]
```
It is exactly equivalent to using `map` like this:
```
ghci> map square [2..5]
[4,9,16,25]
```
The expression with the left arrow (`x <- [2..5]`) is called a
**generator.** You can have multiple generators in this area, and also
Boolean expressions, all separated by commas. Here is an example with
one generator and one Boolean filter:
```
ghci> [square x | x <- [2..5], odd x]
[9,25]
```
It's the same as:
```
ghci> map square (filter odd [2..5])
[9,25]
```
It gets more interesting when you add multiple generators. Then it treats them like nested loops:
```
ghci> [x+y | x <- [1..3], y <- [4..6]]
[5,6,7,6,7,8,7,8,9]
```
The numbers it is generating can be explained as this iteration of `x` and `y`:
```
1+4 = 5
1+5 = 6
1+6 = 7
2+4 = 6
2+5 = 7
2+6 = 8
3+4 = 7
3+5 = 8
3+6 = 9
```
Here's a nice example of generating Pythagorean triples in a particular range:
```
ghci> range = [1..100]
ghci> [(a,b,c) | a<-range, b<-range, a** main = return ()
**