Basic Haskell Syntax

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:

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