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 meansnegate x
- even for literals unary
-
is translated into negate, so-3.14
meansnegate 3.14
f -x
means subtraction (f
minusx
) rather thanf
applied tonegate 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 typeTree
is the type we are defining. It must begin with a capital letterelt
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 theLeaf
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 theBranch
data constructorderiving ...
well, just trust me, and we'll get back to whatderiving
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])