30 Jul 2013

As of March 2020, School of Haskell has been switched to read-only mode.

# 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)``````

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 :+ 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
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 :+ 0) 0 (1 :+ 0))
print (quadraticSolve (1 :+ 0) (1 :+ 0) (6 :+ 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:

### 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:

A bit better:

# 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:

### 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:

## 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)
• `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 letter

• What 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)

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)

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)

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)

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 = ???``