CSc 372 - Comparative Programming Languages
8 : Haskell -- Function Examples

Christian Collberg

Department of Computer Science

University of Arizona

Functions over Lists

1 Breaking Lists -- `ctake`

ctake n xs (from the standard prelude) takes a number and a list of characters, and returns the first elements of the list.

Examples:
$\begin{gprogram} ctake 3 ['a','b','c','d','e'] $\Rightarrow$\ ['a','b','c'] \\ ctake 3 ['a','b'] $\Rightarrow$\ ['a','b'] \end{gprogram}$
Haskell:
$\begin{gprogram} ctake :: Int -> [Char] -> [Char] \\ ctake 0 \_ \xxxxxxx = [\ ]... ... \xxxxxxx = [\ ] \\ ctake (n+1) (x:xs) \xxxxxxx = x : ctake n xs \end{gprogram}$

2 Don't Get Confused!

What do the two arrows in the signature of ctake mean?
$\begin{gprogram} ctake :: Int -> [Char] -> [Char] \end{gprogram}$
This is something called Currying, which we will talk about in the next lecture.
For now, think ``two arrows in the function signature means the function takes two arguments.''
This is a lie, but I'll be more truthful later.
ctake takes an Int and a list of Chars as input, and returns a list of Chars.

3 Breaking Lists -- `drop`

drop n xs (from the standard prelude) takes a number and a list, and returns the remaining elements when the first have been removed.

Examples:
$\begin{gprogram} drop 3 ['a','b','c','d','e'] $\Rightarrow$\ ['d','e'] \\ drop ... ...Rightarrow$\ [\ ] \\ drop 3 [1,2,3,4,5] $\Rightarrow$\ [4,5] \\ \end{gprogram}$
Haskell:
$\begin{gprogram} drop :: Int -> [a] -> [a] \\ drop 0 xs \xxxxxxx = xs \\ drop \_ [\ ] \xxxxxxx = [\ ] \\ drop (n+1) (x:xs) \xxxxxxx = drop n xs \end{gprogram}$

4 Don't Get Confused (take 2)!

What do the two [a]s in the signature of drop mean?
$\begin{gprogram} drop :: Int -> [a] -> [a] \end{gprogram}$
drop is what's called a Polymorphic Function, which we will talk more about soon.
The idea is that a is a type variable, that can take on any type we want.
So, drop can work on lists of Ints, lists of Chars, etc.

5 List Element Selection

The operator !! in the standard prelude returns an element of a list. Lists are indexed starting at 0.

Examples:
$\begin{gprogram} \mbox{[2,5,8,3,9,5,7]} !!3 \xxxxxxxx $\Rightarrow$\ 3 \\ \mbox... ... \\ \mbox{[[1],[2,3],[4]]} !!1!!0 \xxxxxxxx $\Rightarrow$\ 2 \\ \end{gprogram}$

We can write our own list element selector function:

$\begin{gprogram} elmt :: [Int] -> Int -> Int\\ elmt (x:\_) 0 \xxxxxx = x\\ elmt (\_:xs) (n+1) \xxxxxx = elmt xs n \end{gprogram}$

6 Don't Get Confused (take 3)!

We can actually define elmt to be an operator, just like in the standard prelude:

$\begin{gprogram} infixl 9 !! \\ \\ (!!) :: [a] -> Int -> a \\ (x:\_) !! 0 \xxxxxx = x \\ (\_:xs) !! (n+1) \xxxxxx = xs !! n \end{gprogram}$

infixl 9 declares !! to be a left-associative operator with precedence 9.
We'll talk more about this later...

7 The `zip` Function

zip takes two lists xs and ys and returns a list zs of pairs drawn from xs and ys. xs and ys are combined like the two parts of a zipper.
Extra elements from different length lists are discarded.

Examples:
$\begin{gprogram} zip [1,2] ['a','b'] $\Rightarrow$\ [(1,'a'),(2,'b')] \\ zip [1,2,3] ['a','b'] $\Rightarrow$\ [(1,'a'),(2,'b')] \end{gprogram}$
Haskell:
$\begin{gprogram} zip :: [a] -> [b] -> [(a,b)] \\ zip (x:xs) (y:ys) = (x,y) : zip xs ys \\ zip \_ \_ = [\ ] \end{gprogram}$

8 The `remdups` Function

Define a function to remove duplicate adjacent elements from a list:
$\begin{gprogram} remdups [1] \xxxxxxx $\Rightarrow$\ [1] \\ remdups [1,2,1] \... ...\ [1,2,2] \\ remdups [1,1,1,2] \xxxxxxx $\Rightarrow$\ [1,2,1] \end{gprogram}$
We have to consider three cases:
1. The first two elements of the list are identical. Remove one of them, then remove duplicates from the rest of the list.
2. The first two elements are different. Keep them and remove duplicates from the rest of the list.
3. There are fewer that two elements in the list. Keep them.

9 The `remdups` Function...

Algorithm in English:

Case 1:: Let the first two elements of the list be x and y. Let x==y. Example: L==[1,1,2,3], x==y==1. Discard x. Recursively remove duplicates from the remaining list L=[1,2,3].
Case 2:: The first two elements of the list (x,y) are different (x/=y). Example: L==[1,2,2,3], x==1, y==2. Append x onto the result of removing duplicates from the list L'=[2,2,3] from which x has been removed.
Case 3:: The list has 0 or 1 element. Return it.

10 The `remdups` Function...

Simulation:
$\begin{gprogram} remdups [1,2,2] $\Rightarrow$\ \\ \x 1:(remdups 2:[2]) $\equiv... ...Rightarrow$\ \xxxxxx $\Leftarrow$ case 3,xs=[2] \\ \xxx [1,2] \end{gprogram}$

11 The `remdups` Function...

Algorithm in Haskell:
$\begin{gprogram} remdups :: [Int] -> [Int] \\ remdups x:y:xs = \\ \x if x == y... ...arrow$\ case 2 \\ remdups xs = xs \xxxxxxxx $\Leftarrow$\ case 3 \end{gprogram}$

case 1:: First two elements identical.
case 2:: First two elements different.
case 3:: Less than 2 elements left.

x:y:xs matches any list with 2 or more elements.

12 Haskell Guards

Remember the guard syntax in Haskell:
$\begin{gprogram} fun\_name fun\_args \\ \x \vert $\tc{guard}_1$\ \xxxxx = $\t... ... \xxx $\cdots$\ \\ \x \vert otherwise \xxxxx = $\tc{expr}_n$ \end{gprogram}$
This is equivalent to:
$\begin{gprogram} fun\_name fun\_args \\ \x if $\tc{guard}_1$\ then \\ \xx $... ...{expr}_2$\ \\ \x else if $\cdots$\ \\ \x else $\tc{expr}_n$ \end{gprogram}$

13 Haskell Guards...

Many functions become more succinct using guards:

fact with guards:
$\begin{gprogram} fact :: Int -> Int \\ fact n \\ \x \vert n==0 \xxxx = 1 \\ \x \vert otherwise \xxxx = n * fact (n-1) \end{gprogram}$

remdups with guards:
$\begin{gprogram} remdups :: Eq [a] => [a] -> [a] \\ remdups (x:y:xs) \\ \x \ve... ...\ \x \vert x /= y \xxxx = x : remdups (y:xs) \\ remdups xs = xs \end{gprogram}$

14 Don't Get Confused (take 4)!

What does the Eq [a] => mean in the signature of remdups?
$\begin{gprogram} remdups :: Eq [a] => [a] -> [a] \end{gprogram}$
Again, remdups is defined as a polymorphic function, and should therefore work on lists of any element type.
However, it will only work on elements for which == is defined, because, without an equality test available we can't test if two adjacent elements are the same!
Eq [a] => means that remdups can only be applied to elements that can be compared with ==.
We'll talk more about this later....

15 The `append` Function

We want to define a function that appends two lists together:
$\begin{gprogram} append [1,2] [3,4] \xxxxxx $\Rightarrow$\ [1,2,3,4] \\ append [\ ] [1,2] \xxxxxx $\Rightarrow$\ [1,2] \end{gprogram}$
Only use cons (":") and recursion.
Remember that cons creates a new list from an element x and a list xs, such that x is the first element and xs the last elements of the list:
$\begin{gprogram} 5 : [1,2] \xxxxxx $\Rightarrow$\ [5,1,2] \end{gprogram}$

16 The `append` Function...

``Algorithm'' for append xs ys:

Take xs apart and use cons to put the elements together to make a new list.
Again use cons to make ys the tail of this new list.

17 The `append` Function...

Simulation:
$\begin{gprogram} append [1,2,3] [4,5] $\Rightarrow$\ \\ \x 1: (append [2,3] [4,... ...htarrow$\ \\ \xx 1: [2,3,4,5] $\Rightarrow$\ \\ \x [1,2,3,4,5] \end{gprogram}$

18 The `append` Function...

Note how we take the first argument apart when going into the recursion, and how it is put together when returning back up.
Notice also that the second argument to append is never traversed. It is simply ``tacked on'' (using cons) to the end of the new list when the bottom of the recursion has been reached.

19 The `append` Function...

Algorithm in Haskell:
$\begin{gprogram} append :: [a] -> [a] -> [a] \\ append [\ ] xs = xs \\ append (x:xs) ys = x : append xs ys \end{gprogram}$

++ as append:

It is more convenient to define append as an infix operator. ++ is predefined in the standard prelude.

$\begin{gprogram} infixr 5 ++ \\ (++) :: [a] -> [a] -> [a] \\ \mbox{[\ ]}++xs = xs \\ (x:xs) \verb!++! ys = x : (xs \verb!++! ys) \end{gprogram}$

Local Definitions

20 The `where` Clause

In some languages we can nest declarations, i.e. declarations can be made local to a particular procedure:
$\begin{gprogram} \redtxt{function} P ($\cdots$) : $\cdots$\ \\ \x \redtxt{fun... ...\x .... \\ \redtxt{begin} $\cdots$\ X($\cdots$) $\cdots$\ end. \end{gprogram}$
The local function X can only be accessed from within P. This is an important way to break a complicated routine into manageable chunks. We also hide the definition of X from routines other than P.
Haskell has a where-clause that works much the same way as a local function or variable.

21 The `where` Clause...

The where-clause follows after a function body:
$\begin{gprogram} fun\_name fun\_args = \\ \x <fun\_body> \\ \xxxxx where \\... ...\tc{decl}_2$\ \\ \xxxxxx $\cdots$\ \\ \xxxxxx $\tc{decl}_n$ \end{gprogram}$
A declaration $\tc{decl}_i$ is like any global function definition.
Note that a constant declaration id = expr is allowed since it is seen as a constant 0-argument function.

22 The `where` Clause...

$\begin{gprogram} deriv f x = \\ \x (f(x+dx) - f x)/dx \\ \xxx where dx = 0.0001 \\ \\ sqrt x = newton f x \\ \xxx where f y = y\verb+^+2 - x \end{gprogram}$

Note that the scope (area of visibility) of a where-clause is the entire right-hand side of the function definition.

23 The `where` Clause...

$\begin{gprogram} g :: Int -> Int \\ g n \xx \vert \xx (n \lq mod\lq 3) == x \xxxxxx ... ...here \xx x = 0 \\ \xx \xxxx \xx y = 1 \\ \xx \xxxx \xx z = 2 \end{gprogram}$

24 The `let` Clause

An other, less flexible way, of introducing a local definition, is the let-clause.
The syntax of a let-clause:
$\begin{gprogram} let \\ \x <local\_definitions> \\ in \\ \x <expression> \end{gprogram}$
Note that the scope of the let-clause is only one expression, whereas the where clause can span over several.

25 The `let` Clause...

$\begin{gprogram} f :: [Int] -> [Int] \\ f [\ ] = [\ ] \\ f xs = \\ \x let \\ ... ... 1 \\ \xx (y:ys) = xs \\ \x in \\ \xx (square y + one) : f ys \end{gprogram}$

26 The `let` Clause...

$\begin{gprogram} f [1,2] $\Rightarrow$\ \\ \x (square 1 + one) : f [2] $\Righta... ... : []) $\Rightarrow$\ \\ \xx 2 : [5] $\Rightarrow$\ \\ \x [2,5] \end{gprogram}$

Rational Arithmetic Package

27 Rational Arithmetic

Build a package implementing rational arithmetic.

Arithmetic Laws:

$\begin{eqnarray*} \frac{a}{b} + \frac{c}{d} & = & \frac{ad + bc}{bd} \\ \frac{a}{b} * \frac{c}{d} & = & \frac{ac}{bd} \end{eqnarray*}$

$\begin{eqnarray*} \frac{a}{b} - \frac{c}{d} & = & \frac{ad - bc}{bd} \\ \frac{a}{b} / \frac{c}{d} & = & \frac{ad}{bc} \end{eqnarray*}$

$\begin{eqnarray*} \frac{5}{4} + \frac{6}{7} & = & \frac{5*7 + 4*6}{4*7} = \frac{... ...\frac{5}{4} * \frac{6}{7} & = & \frac{5*6}{4*7} = \frac{15}{14} \end{eqnarray*}$

28 Rational Arithmetic...

There is more than one way to represent the same rational number:

$\begin{displaymath}\frac{1}{7}=\frac{-1}{-7}=\frac{3}{21}=\frac{168}{1176}\end{displaymath}$

We would like to represent each rational number $\frac{a}{b}$ in the simplest way, called the normal form, such that and are relatively prime. Hence, $\frac{168}{1176}$ would always be represented as $\frac{1}{7}$ .
Two numbers and are relatively prime if and have no common divisor. 9 and 16 are relatively prime, but 9 and 15 aren't (they both have the common divisor 3).
0 is always represented by $\frac{0}{1}$ .

29 Rational Arithmetic...

We represent a rational number as a tuple of the numerator and the denominator:
type Rat = (Int, Int)

We normalize a Rat by dividing the numerator and denominator by their greatest common divisor.

$\begin{gprogram} normRat :: Rat -> Rat \\ normRat (\_,0) = error(''Invalid!$\ba... ...xx \xxx b = gcd a b \\ normRat (-168,1176) $\Rightarrow$\ (-1,7) \end{gprogram}$

30 Rational Arithmetic...

The signum Function:

signum x (from the standard prelude) returns -1 if x is negative, 0 if x is 0, and 1 if x is positive.

$\begin{gprogram} signum :: (Num a, Ord a) => a -> Int \\ signum n \xxx \vert \x... ... \xxx \vert \x n > 0 \xxx = 1 \\ \xxx \vert \x n < 0 \xxx = -1 \end{gprogram}$

The gcd Function:
$\begin{gprogram} gcd :: Int -> Int -> Int \\ gcd x y = gcd' (abs x) (abs y) \\ ... ... \xxxx gcd' y (rem x y) \\ \\ gcd 78 42 \xxxxx $\Rightarrow$\ 6 \end{gprogram}$

31 Rational Arithmetic...

Arithmetic:
$\begin{gprogram} negRat :: Rat -> Rat \\ negRat (a,b) = normRat (-a,b) \\ \\ ... ...= normRat (a*c, b*d) \\ divRat (a,b) (c,d) = normRat (a*d, b*c) \end{gprogram}$
Examples:
$\begin{gprogram} \redtt{> addRat (4,5) (5,6)} \\ \x (49,30) \end{gprogram}$

32 Rational Arithmetic...

Relational Comparison:
$\begin{gprogram} eqRat :: Rat -> Rat -> Bool \\ eqRat (a,0) (c,d) = err \\ eqR... ...(a,b) (c,d) = (a*d == b*c) \\ \x where err = error ''Invalid!'' \end{gprogram}$

Examples:
$\begin{gprogram} \redtt{> eqRat (4, 0) (4, 1)} \\ \x Invalid! \\ \redtt{> eqRa... ..., 5)} \\ \x True \\ \redtt{> eqRat (4, 5) (4, 6)} \\ \x False \end{gprogram}$

Exercises

33 Homework

Define a function split xs that takes alist of pairs, makes two lists, one from the first elements of the pair and the other from the second pair elements, and returns the two lists as a pair.

Examples:
$\begin{gprogram} split [(1,''a''),(2,''b''),(3,''c'')] \\ \x $\Rightarrow$\ ([1... ...se),(3,False)] \\ \x $\Rightarrow$\ ([1,2,3],[True,False,False]) \end{gprogram}$

34 Homework

We model vectors as triples of floating point numbers:
$\begin{gprogram} type Vector = (Float, Float, Float) \end{gprogram}$
Define functions add'v, scale'v, dot'v (dot product), and cross'v (cross product) according to the definitions below:

$\begin{eqnarray*} (a_1,a_2,a_3)+(b_1,b_2,b_3) & = & (a_1+b_1,a_2+b_2,a_3+b_3) \\... ...(b_1,b_2,b_3) & = & (a_2b_3-b_2a_3,a_3b_1-a_1b_2,a_1b_2-a_2b_1) \end{eqnarray*}$

35 Homework...

Now model $3\times3$ matrices as triples of Vector.
Define a function scale'm that scales a matrix m by a float s, i.e. multiplies all elements by s.
Define a function add'm that adds two matrices a and b together to form a new matrix c, i.e. $c_{i,j} = a_{i,j}+b_{i,j}$ .
Define a function transpose'm m that turns the rows of a matrix m into columns, and vice versa, i.e. $t_{i,j} = m_{j,i}$ .

Christian S. Collberg
2005-09-07

CSc 372 - Comparative Programming Languages 8 : Haskell -- Function Examples

CSc 372 - Comparative Programming Languages
8 : Haskell -- Function Examples