# Syntax elements

(Just so I don't forget: This web system sometimes hangs on perfectly correct Haskell and I'm still working out why...)

## Basic data types

Haskell has the basic components you'd expect:

```
-- one-line comments begin with --
{- area comments are enclosed in {- -},
which can be nested -}
-- integers
n = 10
-- floating point numbers
x = 2.718281828459045
-- Unicode strings
s = "Where is task force thirty four?"
-- tuples: fixed number of items, any types
t = (n, s, x)
-- lists: any number of items, same type
zs = [1, 2, 3, 4]
-- lists can also be constructed using the : operator and the empty list []
ws = 1 : 2 : 3 : 4 : []
-- lists as ranges
zRange = [0, 2 .. 10]
-- and getting stuff done:
main = do
putStrLn s -- Output s with a new line at the end
print s -- Show s as a string literal with a new line
print x
print zs
print ws
print zRange
```

## Function definitions and application

Function application is by juxtaposition or infix operators. (Note: The compiler on this site is oddly picky.
You need spaces around `*`

etc. for some reason, probably to do with markdown.)

```
-- define a function f that takes one number and returns one number
f x = x ^ 2 + 3 * x + 1
x0 = 2.5
y0 = f 2.5
-- define a function g that takes two numbers and returns one number
g a b = a ^ 2 + b ^ 2
c = g 3 4
main = do
print (x0, y0)
print (3, 4, g 3 4)
```

You can also use the `\ ... -> ...`

notation to create an anonymous function, also known as a lambda expression:

```
-- define a function f that takes one number and returns one number
f = \x -> x ^ 2 + 3 * x + 1
x0 = 2.5
y0 = f 2.5
-- define a function g that takes two numbers and returns one number
g = \a b -> a ^ 2 + b ^ 2
c = g 3 4
main = do
print (x0, y0)
print (3, 4, g 3 4)
```

## Conditioning via if-then-else

The easiest conditioning is done with `if`

-`then`

-`else`

:

```
absoluteValue x =
if x < 0 then -x else x
main = do
print (absoluteValue 10)
print (absoluteValue (-6.5)) -- unary minus is tricky :-(
print (absoluteValue 0)
```

## Instead of loops

There are no looping constructions (`while`

, `for`

). Instead, you use recursion and write looping functions:

```
collatz n =
if n == 1
then 1 -- base case
else
if n `mod` 2 == 0 -- same as: mod n 2 == 0
then collatz (n `div` 2)
else collatz (3 * n + 1)
main = do
print (collatz 1)
print (collatz 2)
print (collatz 3)
print (collatz 4)
print (collatz 5)
```

And you can do list comprehensions:

```
f x = x ^ 2 + 3 * x + 1
points = [(x, f x) | x <- [-5 .. 5] ]
main = do
print points
```

which can include a condition to filter the results:

```
f x = x ^ 2 + 3 * x + 1
points =
[(x, f x)
| x <- [-10 .. 10],
x `mod` 3 == 0 ]
main = do
print points
```

You can also do Cartesian products of lists in comprehensions:

```
square n =
[(i, j)
| i <- [0 .. n],
j <- [0 .. n] ]
upperTriangle n =
[(i, j)
| i <- [0 .. n],
j <- [i .. n] ]
evenSumSquare n =
[(i, j)
| i <- [0 .. n],
j <- [0 .. n],
0 == mod (i + j) 2]
main = do
print (square 3)
print (upperTriangle 3)
print (evenSumSquare 3)
```

## Local definitions

Local definitions are built using `let`

-`in`

and `where`

. All definition groups are mutually recursive and can shadow symbols defined in a surrounding scope. With `where`

, the definitions come after the expression in which they are used:

```
import Data.Complex
-- Solutions to a * x^2 + b * x + c == 0
quadraticSolve a b c = (rPlus, rMinus)
where
discriminant = sqrt (b ^ 2 - 4 * a * c)
rPlus = ((-b) + discriminant) / (2 * a)
rMinus = ((-b) - discriminant) / (2 * a)
main = do
print (quadraticSolve 1 1 (-6))
print (quadraticSolve 1 0 1)
print (quadraticSolve (1 :+ 0) 0 (1 :+ 0))
print (quadraticSolve (1 :+ 0) (1 :+ 0) (6 :+ 0))
```

The syntax for `let`

is `let`

followed by definitions, then `in`

, and the expression in which those definitions are used:

```
import Data.Complex
-- Solutions to a * x^2 + b * x + c == 0
quadraticSolve a b c =
if a == 0
then error "Leading coefficient can't be zero"
else
let
discriminant = sqrt (b ^ 2 - 4 * a * c)
rPlus = ((-b) + discriminant) / (2 * a)
rMinus = ((-b) - discriminant) / (2 * a)
in
(rPlus, rMinus)
main = do
print (quadraticSolve 1 1 (-6))
print (quadraticSolve 1 0 1)
print (quadraticSolve (1 :+ 0) 0 (1 :+ 0))
print (quadraticSolve (1 :+ 0) (1 :+ 0) (6 :+ 0))
print (quadraticSolve 0 0 0)
```

You can put `let`

in list comprehensions, and those symbols are available in the generator expression:

```
f x = x ^ 2 + 3 * x - 20
points =
[(x, y)
| x <- [-10 .. 10],
let y = f x,
y >= 0 ]
main = do
print points
```

## Exercises

### List of squares

Complete this program so it prints out a list of the first n square numbers

```
listOfSquares n = ???
main = do
print (listOfSquares 10)
print (listOfSquares 20)
```

Solution:

```
listOfSquares n =
[k^2 | k <- [1 .. n] ]
main = do
print (listOfSquares 10)
print (listOfSquares 20)
```

### Pythagorean triples

Complete this program to print out a list of Pythagorean triples with numbers between 3 and 50.

A Pythagorean triple is three integers `(a,b,c)`

such that `a^2 + b^2 == c^2`

.

```
pythagoreanTriples = ???
main =
print pythagoreanTriples
```

Easiest solution:

```
pythagoreanTriples =
[(a, b, c)
| a <- [3 .. 50],
b <- [3 .. 50],
c <- [3 .. 50],
c^2 == a^2 + b^2]
main =
print pythagoreanTriples
```

A bit better:

```
pythagoreanTriples =
[(a, b, c)
| a <- [3 .. 50],
b <- [a .. 50],
c <- [b .. 50],
c^2 == a^2 + b^2]
main =
print pythagoreanTriples
```

# The list data type and pattern matching

## Definition and deconstruction of a list

A list of items of type t is either an empty list or a value of type t followed by a list of items of type t. You could define your own list type as follows:

`data List t = Null | Cons t (List t)`

But Haskell has lists built in, and special notation to make them easier to use. The definition is roughly as follows:

`data [t] = [] | t : [t]`

Here's how to determine the length of a list (a standard library function):

```
length [] = 0
length (x:xs) = 1 + length xs
```

The `map`

function (or combinator) takes a function and a list of items and returns a list built by applying the function to each item. Here are two implementations of `map`

:

`map f xs = [f x | x <- xs]`

```
map f [] = []
map f (x:xs) = f x : map f xs
```

You can also use the `case`

syntax instead of multiple equations:

```
map f xs =
case xs of
[] -> []
x:xs -> f x : map f xs
```

Lists can be concatenated. The `++`

operator does this. Here is an implementation:

```
-- this is how to declare a right-associative binary operator with precedence level 5
infixr 5 ++
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)
```

## Exercises

### Sum of items

Haskell has a built-in function `sum`

that returns the sum of all items in a list of numbers. Write an implementation:

```
mySum = ???
main = do
print (sum [1,4,7,20]) -- built in library function
print (mySum [1,4,7,20])
```

Solution:

```
mySum [] = 0
mySum (x:xs) = x + mySum xs
main = do
print (sum [1,4,7,20]) -- built in library function
print (mySum [1,4,7,20])
```

### Reverse a list

Haskell has a built-in function `reverse`

that takes a list and returns a list of the same items in reverse order. Write an implementation:

```
myReverse = ???
main = do
print (reverse [1,4,7,20]) -- built in library function
print (myReverse [1,4,7,20])
```

Solutions:

Using `++`

:

```
myReverse [] = []
myReverse (x:xs) = myReverse xs ++ [x]
main = do
print (reverse [1,4,7,20]) -- built in library function
print (myReverse [1,4,7,20])
```

but that's not so good, because it ends up traversing the list multiple times

Using an accumulator:

```
myReverse xs = loop xs []
where
loop [] ys = ys
loop (x:xs) ys = loop xs (x:ys)
main = do
print (reverse [1,4,7,20]) -- built in library function
print (myReverse [1,4,7,20])
```

## Partial applications and combinators

Since Haskell allows you to build partially applied functions and pass them around, you can do things like this:

```
add x y = x + y
numbers = [6, 5, 0, 2]
-- Partial evaluation means that (add 1) is the same as (\y -> 1 + y)
-- so we can do this:
biggerNumbers = map (add 1) numbers
main = do
print numbers
print biggerNumbers
```

Infix operators also have a special partial application syntax, and that lets us abbreviate the previous example into :

```
numbers = [6, 5, 0, 2]
-- Partial evaluation means that (1 +) is the same as (\y -> 1 + y)
-- so we can do this:
biggerNumbers1 = map (1 +) numbers
-- and you can go the other way:
biggerNumbers2 = map (+ 1) numbers
main = do
print numbers
print biggerNumbers1
print biggerNumbers2
```

By the way, this is why the `-`

operator is sort of funky. The notation `(-2)`

could either mean `\x -> x - 2`

or negative two. The standard defines a special syntactic rules that

`(x-)`

means`\y -> x - y`

as expected`(-x)`

always means`negate x`

- even for literals unary
`-`

is translated into negate, so`-3.14`

means`negate 3.14`

`f -x`

means subtraction (`f`

minus`x`

) rather than`f`

applied to`negate x`

- A
`subtract`

function is available,`subtract 2 = \x -> x - 2`

, to make up for the missing meaning of`(-2)`

.

```
numbers = [6, 5, 0, 2]
smallerNumbers = map (subtract 1) numbers
reflectedNumbers = map (10 -) numbers
main = do
print numbers
print smallerNumbers
print reflectedNumbers
```

Also, Haskell has special backtick notation for using a function named by letters as an infix operator:

```
r = 10 `div` 3
-- same as:
r = div 10 3
```

and special parentheses notation for using an infix operator named by symbols as a function in prefix form:

```
x = (+) 1 2
-- same as
x = 1 + 2
```

## Storing a set of numbers in a tree

Here's how to define a binary tree data structure inductively much like a list. A tree is either an empty leaf node, or a branch with two subtrees and a value. Values in the left subtree must be less than the branch's value, and values in the right subtree must be greater.

```
data Tree elt =
Leaf
| Branch elt (Tree elt) (Tree elt)
deriving (Read, Show, Eq, Ord)
```

`data`

is a key word defining an algebraic data type`Tree`

is the type we are defining. It must begin with a capital letter`elt`

is a type variable. It must begin with a lower case letterWhat follows the = is a list of alternatives separated by

`|`

`Leaf`

means that a tree can be an empty object, marked by the`Leaf`

data constructor. Data constructors must begin with a capital letter.`Branch ...`

means that a tree can also be a triple of an element and two trees, marked by the`Branch`

data constructor`deriving ...`

well, just trust me, and we'll get back to what`deriving`

means later

Let's create some test trees and search them:

```
data Tree elt =
Leaf
| Branch elt (Tree elt) (Tree elt)
deriving (Read, Show, Eq, Ord)
singleton elt = Branch elt Leaf Leaf
-- pretty printing
prettyPrint Leaf = ""
prettyPrint (Branch v left right) =
"(" ++ prettyPrint left ++ ") < " ++ show v ++ " < (" ++ prettyPrint right ++ ")"
-- Nothing is included in an empty leaf.
treeIncludes x Leaf = False
-- If a tree is a branch, it might contain the element.
-- If the value we're looking for is greater than that,
-- it certainly isn't in the tree.
-- Otherwise, it might be in one of the subtrees.
treeIncludes x (Branch y left right) =
if x == y then True
else if x > y then treeIncludes x right
else treeIncludes x left
exTree = Branch 2 (singleton 1) (singleton 3)
main = do
print exTree
putStrLn (prettyPrint exTree)
print (treeIncludes 2 exTree)
print (treeIncludes 10 exTree)
```

To add an item to a tree, we have to create a new tree with the item in it.

```
data Tree elt =
Leaf
| Branch elt (Tree elt) (Tree elt)
deriving (Read, Show, Eq, Ord)
singleton elt = Branch elt Leaf Leaf
-- pretty printing
prettyPrint Leaf = ""
prettyPrint (Branch v left right) =
"(" ++ prettyPrint left ++ ") < " ++ show v ++ " < (" ++ prettyPrint right ++ ")"
-- Nothing is included in an empty leaf.
treeIncludes x Leaf = False
-- If a tree is a branch, it might contain the element.
-- If the value we're looking for is greater than that,
-- it certainly isn't in the tree.
-- Otherwise, it might be in one of the subtrees.
treeIncludes x (Branch y left right) =
if x == y then True
else if x > y then treeIncludes x right
else treeIncludes x left
-- show
-- If the tree is empty, insertion is easy: just create a singleton.
treeInsert x Leaf = singleton x
-- If the tree is a branch:
treeInsert x t@(Branch y left right) =
-- If x is already in the tree, then no need to insert it again
if x == y then t
-- If x is greater than y, insert it to the right
else if x > y then Branch y left (treeInsert x right)
-- Else x < y, so insert it to the left
else Branch y (treeInsert x left) right
exTree = Branch 20 (singleton 10) (singleton 30)
main = do
putStrLn (prettyPrint exTree)
putStrLn (prettyPrint (treeInsert 5 exTree))
putStrLn (prettyPrint (treeInsert 15 exTree))
putStrLn (prettyPrint (treeInsert 25 exTree))
putStrLn (prettyPrint (treeInsert 35 exTree))
-- /show
```

Deleting from a tree is the same kind of thing.

```
data Tree elt =
Leaf
| Branch elt (Tree elt) (Tree elt)
deriving (Read, Show, Eq, Ord)
singleton elt = Branch elt Leaf Leaf
-- pretty printing
prettyPrint Leaf = ""
prettyPrint (Branch v left right) =
"(" ++ prettyPrint left ++ ") < " ++ show v ++ " < (" ++ prettyPrint right ++ ")"
-- Nothing is included in an empty leaf.
treeIncludes x Leaf = False
-- If a tree is a branch, it might contain the element.
-- If the value we're looking for is greater than that,
-- it certainly isn't in the tree.
-- Otherwise, it might be in one of the subtrees.
treeIncludes x (Branch y left right) =
if x == y then True
else if x > y then treeIncludes x right
else treeIncludes x left
-- If the tree is empty, insertion is easy: just create a singleton.
treeInsert x Leaf = singleton x
-- If the tree is a branch:
treeInsert x t@(Branch y left right) =
-- If x is already in the tree, then no need to insert it again
if x == y then t
-- If x is greater than y, insert it to the right
else if x > y then Branch y left (treeInsert x right)
-- Else x < y, so insert it to the left
else Branch y (treeInsert x left) right
--show
-- If the tree is empty, deletion is easy:
treeDelete x Leaf = Leaf
-- If there's a branch
treeDelete x (Branch y left right) =
-- maybe have to delete it from a subtree
if x < y then Branch y (treeDelete x left) right
else if x > y then Branch y left (treeDelete x right)
else -- x == y, have to delete it from this node in the middle, which is trickier
case left of
-- If the left subtree is empty, we're deleting the root
Leaf ->
right
branch ->
let
(m, newLeft) = treePop left
in
Branch m newLeft right
-- Delete the right-most (maximum element) from the tree, returning it and the new tree
treePop (Branch y left Leaf) =
(y, left)
treePop (Branch x left right) =
let
(z, newRight) = treePop right
in
(z, Branch x left newRight)
exTree = Branch 20 (singleton 10) (singleton 30)
main = do
putStrLn (prettyPrint exTree)
putStrLn (prettyPrint (treeDelete 10 exTree))
putStrLn (prettyPrint (treeDelete 20 exTree))
putStrLn (prettyPrint (treeDelete 30 exTree))
-- /show
```

## Exercises

Use this workspace:

```
data Tree elt =
Leaf
| Branch elt (Tree elt) (Tree elt)
deriving (Read, Show, Eq, Ord)
singleton elt = Branch elt Leaf Leaf
-- pretty printing
prettyPrint Leaf = ""
prettyPrint (Branch v left right) =
"(" ++ prettyPrint left ++ ") < " ++ show v ++ " < (" ++ prettyPrint right ++ ")"
-- Nothing is included in an empty leaf.
treeIncludes x Leaf = False
-- If a tree is a branch, it might contain the element.
-- If the value we're looking for is greater than that,
-- it certainly isn't in the tree.
-- Otherwise, it might be in one of the subtrees.
treeIncludes x (Branch y left right) =
if x == y then True
else if x > y then treeIncludes x right
else treeIncludes x left
-- If the tree is empty, insertion is easy: just create a singleton.
treeInsert x Leaf = singleton x
-- If the tree is a branch:
treeInsert x t@(Branch y left right) =
-- If x is already in the tree, then no need to insert it again
if x == y then t
-- If x is greater than y, insert it to the right
else if x > y then Branch y left (treeInsert x right)
-- Else x < y, so insert it to the left
else Branch y (treeInsert x left) right
-- If the tree is empty, deletion is easy:
treeDelete x Leaf = Leaf
-- If there's a branch
treeDelete x (Branch y left right) =
-- maybe have to delete it from a subtree
if x < y then Branch y (treeDelete x left) right
else if x > y then Branch y left (treeDelete x right)
else -- x == y, have to delete it from this node in the middle, which is trickier
case left of
-- If the left subtree is empty, we're deleting the root
Leaf ->
right
branch ->
let
(m, newLeft) = treePop left
in
Branch m newLeft right
-- Delete the right-most (maximum element) from the tree, returning it and the new tree
treePop (Branch y left Leaf) =
(y, left)
treePop (Branch x left right) =
let
(z, newRight) = treePop right
in
(z, Branch x left newRight)
exTree = Branch 20 (singleton 10) (singleton 30)
main = do
putStrLn "Put some test cases here"
```

### From list

Write a function that takes a list of items (in no particular order) and builds a tree, with everything in the proper order:

`treeFromList xs = ???`

### To list

Write a function that builds a list of the elements of a tree in ascending order. Try to do this in a way that doesn't repeatedly traverse partial lists along the way...

`treeToList t = ???`

### Tree map

Write an equivalent of `map`

for trees:

`treeMap f t = ???`

### Solutions

```
data Tree elt =
Leaf
| Branch elt (Tree elt) (Tree elt)
deriving (Read, Show, Eq, Ord)
singleton elt = Branch elt Leaf Leaf
-- pretty printing
prettyPrint Leaf = ""
prettyPrint (Branch v left right) =
"(" ++ prettyPrint left ++ ") < " ++ show v ++ " < (" ++ prettyPrint right ++ ")"
-- Nothing is included in an empty leaf.
treeIncludes x Leaf = False
-- If a tree is a branch, it might contain the element.
-- If the value we're looking for is greater than that,
-- it certainly isn't in the tree.
-- Otherwise, it might be in one of the subtrees.
treeIncludes x (Branch y left right) =
if x == y then True
else if x > y then treeIncludes x right
else treeIncludes x left
-- If the tree is empty, insertion is easy: just create a singleton.
treeInsert x Leaf = singleton x
-- If the tree is a branch:
treeInsert x t@(Branch y left right) =
-- If x is already in the tree, then no need to insert it again
if x == y then t
-- If x is greater than y, insert it to the right
else if x > y then Branch y left (treeInsert x right)
-- Else x < y, so insert it to the left
else Branch y (treeInsert x left) right
-- If the tree is empty, deletion is easy:
treeDelete x Leaf = Leaf
-- If there's a branch
treeDelete x (Branch y left right) =
-- maybe have to delete it from a subtree
if x < y then Branch y (treeDelete x left) right
else if x > y then Branch y left (treeDelete x right)
else -- x == y, have to delete it from this node in the middle, which is trickier
case left of
-- If the left subtree is empty, we're deleting the root
Leaf ->
right
branch ->
let
(m, newLeft) = treePop left
in
Branch m newLeft right
-- Delete the right-most (maximum element) from the tree, returning it and the new tree
treePop (Branch y left Leaf) =
(y, left)
treePop (Branch x left right) =
let
(z, newRight) = treePop right
in
(z, Branch x left newRight)
treeToList t = loop t []
where
loop Leaf tailElts = tailElts
loop (Branch x left right) tailElts =
loop left (x : loop right tailElts)
treeFromList [] = Leaf
treeFromList (x:xs) = treeInsert x (treeFromList xs)
treeMap f t =
treeFromList (map f (treeToList t))
exTree1 = treeFromList [10, 30, 20]
exTree2 = treeFromList [-5 .. 5]
f x = x ^ 2 + 3 * x - 20
exTree3 = treeMap f exTree2
main = do
putStrLn (prettyPrint exTree1)
print (treeToList exTree1)
putStrLn (prettyPrint exTree3)
print (map f [-5 .. 5])
```