1 Introduction
Book: Programming in Haskell 2ndEdition
1.1 Functional Programming
What is functional programming?
 Functional programming is style of programming in which the basic method of computation is the application of functions to arguments;
 A functional language is one that supports and encourages the functional style.
1.2 Features of Haskell
 Concise programs (ch2 & ch4)
 Powerful type system (ch3 & ch8)
 List comprehensions (ch5)
 Recursive functions (ch6)
 Higherorder functions (ch7)
 Effectful functions (ch10 & ch12)
 Generic functions (ch12 & ch14)
 Lazy evaluation (ch15)
 Equational reasoning (ch16 & ch17)
1.3 A Taste of Haskell
1  sum [] = 0 
1  sum [1,2,3] 
2 First Steps
2.1 Installation
1  $ ghci 
2.2 Standard Prelude
1  > head [1,2,3,4,5] 
More most commonly used definitions see appendix B.
2.3 Function Application
In mathematics:
f(a, b) + c d
means apply the function f to a and b, and add the result to the product of c and d.
In Haskell, function application is denoted using space. Multiplication is denoted using *
.
1  f a b + c * d 
Priority: function application is the highest.
f a + b
means(f a) + b
rather thanf (a + b)
.
Mathematics  Haskell 

f(x)  f x 
f(x, y)  f x y 
f(g(x))  f (g x) 
f(x, g(y))  f x (g y) 
f(x)g(y)  f x * g y 
Note that in the 2rd and 4th cases. Without parentheses,
f g x
andf x g y
means apply the function f to g and x ( x, g and y).
2.4 Haskell Scripts
1   test.hs 
1  ❯ ghci test.hs 
1   test.hs 
1  *Main> factorial 10 
Useful GHCi Commands
Command Meaning :load name load script name :relaod reload current script :set editor name set editor to name :edit name edit script name :edit edit current script :type expr show type of expr :? show all commands :quit quit GHCi
2.5 Naming Requirements
 Function and argument names must begin with a lowercase letter.
myFun
fun1
arg_2
x'
 By convention, list arguments usually have an
s
suffix on their name.xs
(a list of arbitrary values)ns
(a list of numbers)nss
(a list of lists of numbers)css
(a list of lists of characters)
2.6 The Layout Rule
1   In a sequence of definitions, each definition must begin in precisely the same column: 
1  { 
1   Explicit grouping 
1   Combined into a single line: 
3 Types and Classes
3.1 Types
 A type is a name for a collection of related values. Examples:
 the type
Bool
contains the two logical valuesFalse
andTrue
.  the type
Bool > Bool
contains all functions that map arguments fromBool
to results fromBool
(like the logical negation functionnot
)
 the type
v :: T
means thatv
is a value in the typeT
, and say thatv
has a typeT
. Examples:False :: Bool
True :: Bool
not :: Bool > Bool
 More generally,
e :: T
means that evaluation of the expressione
will produce a value of typeT
. Example:not False :: Bool
not Ture :: Bool
not (not False) :: Bool
Every well formed expression has a type, which can be automatically calculated at compile time using a process called type inference.
In GHCi, the :type command calculates the type of an expression, without evaluating it:
1
2
3
4
5
6 > :type not
not :: Bool > Bool
> :type False
False :: Bool
> :type not False
not False :: Bool
3.2 Basic Types
Type  Meaning 

Bool 
logical values 
Char 
single characters 
String 
strings of characters 
Int 
fixedprecision integers (2147483647 ~ 2147483647 for 32bit machine) 
Integer 
arbitraryprecision integers (no bound but with lower efficiency) 
Float 
singleprecision floatingpoint numbers 
Double 
doubleprecision floatingpoint numbers 
3.3 List Types
 A list is a sequence of elements of the same type.
[t]
is the type of lists with elements of typet
. Examples:[False, False, Ture] :: [Bool]
['a', 'b', 'c', 'd'] :: [Char]
[['a'], ['b', 'c']] :: [[Char]]
3.4 Tuple Types
 A tuple is a sequence of values of different types.
(t1,t2,...,tn)
is the type ofn
tuples whosei
th components have typeti
for anyi
in1
…n
. Examples:(False,True) :: (Bool,Bool)
(False,'a',True) :: (Bool,Char,Bool)
('a',(False,'b')) :: (Char,(Bool,Char))
(True,['a','b']) :: (Bool,[Char])
3.5 Function Types
 A function is a mapping from values of one type to values of another type.
t1 → t2
is the type of functions that map values of typet1
to values to typet2
. Examples:not :: Bool → Bool
even :: Int → Bool
add :: (Int,Int) → Int
add (x,y) = x+y
zeroto :: Int → [Int]
zeroto n = [0..n]
3.6 Curried Fucntions
Functions with multiple arguments are also possible by returning functions as results. Functions that take their arguments one at a time are called curried functions. Examples:
add' :: Int → (Int → Int)
add' x y = x + y
add'
takes an integerx
and returns a functionadd' x
. In turn, this function takesan integer
y
and returns the resultx+y
.Comparison:
add :: (Int, Int) > Int
mult :: Int > (Int > (Int > Int))
mult x y z = x * y * z
To avoid excess parentheses when working with curried functions, two conventions are adopted:
 The funciton arrow
>
in types is assumed to associate to the right.
Int > Int > Int > Int
meansInt > (Int > (Int > Int))
 Consequently, function application, which is denoted silently using spacing, is assumed to associated to the left.
mult x y z
means((mult x) y) z
Unless tupling is explicitly required, all functions in Haskell with multiple arguments are normally defined as curried functions.
3.7 Polymorphic Types
 A function is called polymorphic (“of many forms”) if its type contains one or more type variables. Examples:
length :: [a] → Int
fst :: (a,b) → a
head :: [a] → a
take :: Int → [a] → [a]
zip :: [a] → [b] → [(a,b)]
id::a → a
3.8 Overloaded Types
A polymorphic function is called overloaded if its type contains one or more class constraints. Examples:
(+) :: Num a ⇒ a > a > a
For any numeric type a, (+) takes two values of type a and returns a value of type a.
(==) :: Eq a ⇒ a → a → Bool
(<) :: Ord a ⇒ a → a → Bool
negate :: Num a => a > a
abs :: Num a => a > a
3 :: Num a => a
3.9 Classes
 A class is a collection of types that support certain overloaded operations called methods.
3.10 Basic Classes
Class  Meaning 

Eq 
equality types (/= , == ) 
Ord 
ordered types (< , > , <= , >= ) 
Show 
showable types 
Read 
readable types 
Num 
numeric types 
Integral  integral types 
Fractional 
fractional types 
4 Defining Functions
4.1 New from Old
The most straightforward way to define new functions is simply by combining one or more existing functions.
 Decide if an integer is even:
even :: Integral a => a > Bool
even n = n `mod` 2 == 0
 Split a list at the nth element:
splitAt :: Int > [a] > ([a], [a])
splitAt n xs = (take n xs, drop n xs)
 Reciprocation:
recip :: Fractional a => a > a
recip n = 1/n
4.2 Conditional Expressions
As in most programming languages, functions can be defined using conditional expressions.
The absolute value of an integer:
abs :: Int > Int
abs n = if n >= 0 then n else n
The sign of an integer:
signum :: Int > Int
```haskell signum n = if n < 0 then 1 else if n == 0 then 0 else 1
1
2
3
4
5
6
7
8
9
10
11
12
> In Haskell, conditional expressions must <u>always</u> have an <u>else</u> branch, which avoids any possible ambiguity problems with nested conditionals.
## 4.3 Guarded Equations
As an alternative to conditionals, functions can also be defined using <u>guarded equations</u>.
 The absolute value of an integer:
 ```haskell
abs n  n >= 0 = n
 otherwise = n
The sign of an integer:
 ```haskell signum n  n < 0 = n  n == 0 = 0  otherwise = 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 The BMI calculator:
 ```haskell
bmiTell :: (RealFloat a) => a > a > String
bmiTell weight height
 bmi <= skinny = "You're underweight, you emo, you!"
 bmi <= normal = "You're supposedly normal. Pffft, I bet you're ugly!"
 bmi <= fat = "You're fat! Lose some weight, fatty!"
 otherwise = "You're a whale, congratulations!"
where bmi = weight / height ^ 2
skinny = 18.5
normal = 25.0
fat = 30.0
 can also define functions in `where` statements
calcBmis :: (RealFloat a) => [(a, a)] > [a]
calcBmis xs = [bmi w h  (w, h) < xs]
where bmi weight height = weight / height ^ 2
 ```haskell signum n  n < 0 = n  n == 0 = 0  otherwise = 1
The names teller:
 ```haskell initials :: String > String > String initials firstname lastname = [f] ++ ". " ++ [l] ++ "." where (f:) = firstname (l:) = lastname
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

> The catch all condition <u>otherwise</u> is defined in the prelude by `otherwise = True`.
## 4.4 Pattern Matching
Many functions have a particularly clear definition using <u>pattern matching</u> on their arguments.
 The negation of a logical value:
 ```haskell
not :: Bool > Bool
not False = True
not True = False
 ```haskell initials :: String > String > String initials firstname lastname = [f] ++ ". " ++ [l] ++ "." where (f:) = firstname (l:) = lastname
The conjunction of two logical values:
```haskell (&&) :: Bool → Bool → Bool True && True = True True && False = False False && True = False False && False = False
1
2
3
4
5
 ```haskell
 can be defined more compactly by
True && True = True
_ && _ = False```haskell  can be defined more efficiently by Ture && b = b Flase && _ = False
> > Patterns may not repeat variables. For example, the following definition gives an error: > >1
2
3
4
5
6
7
8
> The underscore symbol _ is a wildcard pattern that matches any argument value.
> Patterns are matched in order. For example, the following definition always returns False:
>
> ```haskell
> _ && _ = False
> True && True = True1
2b && b = b
_ && _ = False
4.5 Tuple Patterns
A tuple of patterns is itself a pattern, which matches any tuple of the same arity whose components all match the corresponding patterns in order.
Select the first and second components of a pair:
 ```haskell fst :: (a, b) > a fst (x, _) = x
1
2
3
4
 ```haskell
snd :: (a, b) > a
snd (_, y) = y
 ```haskell fst :: (a, b) > a fst (x, _) = x
4.6 List Patterns
A list of patterns is itself a pattern, which matches any list of the same length whose elements all match the corresponding patterns in order.
Decide if a list contains precisely three characters beginning with the letter "a":
```haskell test :: [Char] > Bool test ['a', , ] = True test _ = False
 more generally: test :: [Char] > Bool test ['a':_] = True test _ = False
1
2
3
4
5
6
7
8
9
10
11
12
 Internally, every nonempty list is constructed by repeated use of an operator (:) called “cons” that adds an element to the start of a list:
 `[1,2,3,4]` means `1:(2:(3:(4:[])))`
 Functions on lists can be defined using x:xs patterns:
 ```haskell
head :: [a] > a
head (x:_) = x
tail :: [a] > [a]
tail (_:xs) = xs
```haskell capital :: String > String capital "" = "Empty string, whoops!" capital all@(x:xs) = "The first letter of " ++ all ++ " is " ++ [x]
1
2
3
4
```bash
> capital "Dracula"
"The first letter of Dracula is D"
x:xs
patterns only match nonempty lists
x:xs
patterns must be parenthesised, because application has priority over (:). For example, the following definition gives an error:
1 head x:_ = x
4.7 Lambda Expressions
Functions can be constructed without naming the functions by using lambda expressions.
The nameless function that takes a number x and returns the result x + x:
λx → x + x
```haskell  typed version > x + x
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 Lambda expressions can be used to give a formal meaning to functions defined using currying:
 `add x y = x + y` means `add = λx → (λy → x + y)`
 Lambda expressions are also useful when defining functions that return functions as results:
 ```haskell
const :: a > b > a
const x _ = x
 more natrually defined by
const :: a > (b > a)
const x = \_ > x
Lambda expressions can be used to avoid naming functions that are only referenced once:
```haskell odds n = map f [0..n1] where f x = x*2 + 1
 can be simplified to
odds n = map (> x*2 + 1) [0..n1]
1
2
3
4
5
6
7
8
9
10
11
12
## 4.8 Operator Sections
An operator written <u>between</u> its two arguments can be converted into a <u>curried function</u> written <u>before</u> its two arguments by using parentheses.
 Addition:
 ```bash
> 1+2
3
> (+) 1 2
3
This convention also allows one of the arguments of the operator to be included in the parentheses:
 ```bash > (1+) 2 3 > (+2) 1 3
1
2
3
4
5
6
7
8
9
10
> In general, if ⊕ is an <u>operator</u> then functions of the form (⊕), (x⊕) and (⊕y) are called <u>sections</u>.
 Useful functions can sometimes be constructed in a simple way using sections:
 ```haskell
(1+)  successor function
(1/)  reciprocation function
(*2)  doubling function
(/2)  halving function
 ```bash > (1+) 2 3 > (+2) 1 3
5 List Comprehensions
5.1 Set Comprehensions
In mathematics, the comprehension notation can be used to construct new sets from old sets:
{x^{2}  x ∈ {1..5}}
The set {1,4,9,16,25} of all numbers x^{2} such that x is an element of the set {1...5}.
5.2 List Comprehensions
In Haskell, a similiar comprehension notation can be used to construct new lists from existing lists:
1  > [x^2  x < [1..5]] 

is read as such that<
is read as is drawn fromx < [1..5]
is called a generator
1
2
3
4
5
6
7
8
9 > let nouns = ["hobo","frog","pope"]
> let adjectives = ["lazy","grouchy","scheming"]
> [adjective ++ " " ++ noun  adjective < adjectives, noun < nouns]
["lazy hobo","lazy frog","lazy pope","grouchy hobo","grouchy frog", "grouchy pope","scheming hobo",
"scheming frog","scheming pope"]
5.3 Dependant Generators
Later generators can depend on the variables that are introduced by earlier generators:
1  > [(x,y)  x < [1..3], y < [x..3]] 
Using a dependant generator we can define the library function that concatenates a list of lists:
1  concat :: [[a]] > [a] 
1  > concat [[1,2,3],[4,5],[6]] 
5.4 Wildcard Generators
The wildcard pattern _
is sometimes useful in generators to discard certain elements from a list:
1  firsts :: [(a,b)] > [a] 
Similarly, the library function that calculates the length of a list:
1  length :: [a] > Int 
5.5 Guards
List comprehensions can use guards to restrict the values produced by earlier generators:
1  > [x  x < [1..10], even x] 
Using a guard we can define a function that maps a positive integer to its list of factors:
1  factors :: Int > [Int] 
1  > factors 15 
A positive integer is prime if its only factors are 1 and itself. Hence, using factors we can define a function that decides if a number is prime:
1  prime :: Int > Bool 
Using a guard we can now define a function that returns the list of all primes up to a given limit:
1  primes :: Int > [Int] 
Suppose we represent a lookup table by a list of pairs of keys and values. Then for any type of keys that supports equality, a function find
that returns the list of all values that are associated with a given key in a table can be defined as:
1  find :: Eq a => a > [(a, b)] > [b] 
1  > find 'b' [('a',1),('b',2),('c',3),('b',4)] 
5.6 The zip
Function
A useful library function is zip, which maps two lists to a list of pairs of their corresponding elements:
1  zip :: [a] > [b] > [(a,b)] 
1  > zip [’a’,’b’,’c’] [1,2,3,4] 
Using zip we can define a function returns the list of all pairs of adjacent elements from a list:
1  pairs :: [a] > [(a,a)] 
1  > pairs [1,2,3,4] 
Using pairs we can define a function that decides if the elements in a list are sorted:
1  sorted :: Ord a => [a] > Bool 
1  > sorted [1,2,3,4] 
Using zip we can define a function that returns the list of all positions of a value in a list:
1  positions::Eqa => a > [a] > [Int] 
1  > positions 0 [1,0,0,1,0,1,1,0] 
5.7 String Comprehensions
A string is a sequence of characters enclosed in double quotes. Internally, however, strings are represented as lists of characters:
"abc" :: String
means ['a', 'b', 'c'] :: [Char]
Because strings are just special kinds of lists, any polymorphic function that operates on lists can also be applied to strings:
1  > length "abcde" 
Similarly, list comprehensions can also be used to define functions on strings, such counting how many times a character occurs in a string:
1  count :: Char > String > Int 
1  > count 's' "Mississippi" 
5.8 Some Notes
[1,2,3]
is the syntax sugar for1:2:3:[]
```bash # Compare the first elements in two lists, if equals, compare next one, so on and so forth > [3,2,1] > [2,1,0] True > [3,2,1] > [2,10,100] True > [3,4,2] > [3,4] True > [3,4,2] > [2,4] True > [3,4,2] == [3,4,2] True
1
2
3
4
5
6
7
8
 ![](https://i.loli.net/2018/05/21/5b020f6672a28.png)
 Avoid using `xs == []` but using `null a_list` to check if a list is empty
 ```bash
> 4 `elem` [3,4,5,6]
True```bash > [1,20] [1,20] > [2,4..20] [2,4,6,8,10,12,14,16,18,20] > [20,19..1] [20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1] > take 24 [13,26..] [13,26,39,52,65,78,91,104,117,130,143,156,169,182,195,208,221,234,247,260,273,286,299,312] # No floating numbers when using range > [0.1,0.3..1] [0.1,0.3,0.5,0.7,0.8999999999999999,1.0999999999999999] > take 10 (cycle [1,2,3]) [1,2,3,1,2,3,1,2,3,1] > take 10 (repeat 5) [5,5,5,5,5,5,5,5,5,5] > replicate 10 3 [3,3,3,3,3,3,3,3,3,3]
1
2
3
4
5
6
7
8
9
10
11
12

# 6 Recursive Functions
## 6.1 Basic Concepts
In Haskell, functions can also be defined in terms of themselves. Such functions are called <u>recursive</u>:
```haskell
fac 0 = 1
fac n = n * fac (n1)
The recursive definition diverges on integers < 0 because the base case is never reached:
1
2 > fac (1)
*** Exception: stack overflow
6.2 Recursion on Lists
Recursion is not restricted to numbers, but can also be used to define functions on lists:
1  product :: Num a => [a] > a 
1  > product [2,3,4] 
Using the same pattern of recursion as in product we can define the length function on lists:
1  length :: [a] > Int 
Using a similar pattern of recursion we can define the reverse function on lists:
1  reverse :: [a] > [a] 
In turn, the append operator ++
can itself be defined using recursion on its first argument:
1  (++) :: [a] > [a] > [a] 
More examples:
1  maximum' :: (Ord a) => [a] > a 
6.3 Multiple Arguments
Functions with more than one argument can also be defined using recursion:
Zipping the elements of two lists:
1  zip :: [a] > [b] > [(a,b)] 
Remove the first n elements from a list:
1  drop :: Int > [a] > [a] 
Appending two lists:
1  (++) :: [a] > [a] > [a] 
6.4 Multiple Recursion
Functions can also be defined using multiple recursions:
1  fib :: Int > Int 
The quicksort algorithm for sorting a list of values can be specified by the following two rules:
 The empty list is already sorted;
 Nonempty lists can be sorted by sorting the tail values ≤ the head, sorting the tail values > the head, and then appending the resulting lists on either side of the head value.
Using recursion, this specification can be translated directly into an implementation:
1  qsort :: Ord a => [a] > [a] 
6.5 Mutual Recursion
Functions can also be defined using mutual recursion, in which two or more functions are all defined recursively in terms of each other:
1  even :: Int > Bool 
Similarly, functions that select the elements from a list at all even and odd positions (counting from zero) can be defined as:
1  evens :: [a] > [a] 
7 HigherOrder Functions
7.1 Basic Concepts
A function is called higherorder if it takes a function as an argument or returns a function as a result:
1  twice :: (a > a) > a > a 
1  > twice (*2) 3 
Why Are They Useful?
 Common programming idioms can be encoded as functions within the language itself.
 Domain specific languages can be defined as collections of higherorder functions.
 Algebraic properties of higherorder functions can be used to reason about programs.
7.2 Processing Lists
7.2.1 The map
Function
The higherorder library function called map applies a function to every element of a list:
1  map :: (a > b) > [a] > [b] 
1  > map (+1) [1,3,5,7] 
7.2.2 The filter
Function
The higherorder library function filter selects every element from a list that satisfies a predicate:
1  filter :: (a > Bool) > [a] > [a] 
1  > filter even [1..10] 
7.2.3 The foldr
Function
回到当初我们学习递归的情景。我们会发现处理 List 的许多函数都有固定的模式，通常我们会将边界条件设置为空 List，再 引入
(x:xs)
模式，对单个元素和余下的 List 做些事情。这一模式是如此常见，因此 Haskell 引入了一组函数来使之简化， 也就是fold
。它们与map
有点像，只是它们回传的是单个值。
A number of functions on lists can be defined using the following simple pattern of recursion:
1  f [] = v 
f maps the empty list to some value v, and any nonempty list to some function ⊕ applied to its head and f of its tail. Examples:
1
2
3
4
5
6
7
8 sum [] = 0
sum (x:xs) = x + sum xs
product [] = 1
product (x:xs) = x * product xs
and [] = True
and (x:xs) = x && and xs
The higherorder library function foldr (fold right) encapsulates this simple pattern of recursion, with the function ⊕ and the value v as arguments:
1  sum = foldr (+) 0 
Foldr itself can be defined using recursion:
1  foldr :: (a > b > b) > b > [a] > b 
However, it is best to think of foldr nonrecursively, as simultaneously replacing each (:) in a list by a given function, and [] by a given value. Example:
1   replace each (:) by (*) and [] by 1 
Other Foldr Examples
Even though foldr encapsulates a simple pattern of recursion, it can be used to define many more functions than might first be expected. Recall the length function:
1
2
3
4
5  Replace each (:) by λ_ n → 1+n and [] by 0.
length [1,2,3]
= length (1:(2:(3:[])))
= 1+(1+(1+0))
= 3Hence, we have:
1 length = foldr (\_ n > 1 + n) 0...
1 reverse = foldr (\x xs > xs ++ [x]) []Finally, we note that the append function (++) has a particularly compact definition using foldr:
1 (++ ys) = foldr (:) ys
Why Is Foldr Useful?
 Some recursive functions on lists, such as sum, are simpler to define using foldr.
 Properties of functions defined using foldr can be proved using algebraic properties of foldr, such as fusion and the banana split rule.
 Advanced program optimisations can be simpler if foldr is used in place of explicit recursion.
7.2.4 The foldl
Function
7.3 The Composition Operator
The library function .
returns the composition of two functions as a single function:
1  (.) :: (b > c) > (a > b) > (a > c) 
Example:
1  odd = not . even 
1 f . (g . h) == (f . g) . h
7.4 Some Other Library Functions
7.4.1 The all
Function
The library function all decides if every element of a list satisfies a given predicate:
1  all :: (a > Bool) > [a] > Bool 
1  > all even [2,4,6,8,10] 
7.4.2 The any
Function
Dually, the library function any decides if at least one element of a list satisfies a predicate:
1  any :: (a > Bool) > [a] > Bool 
1  > any (== ' ') "abc def" 
7.4.3 The takeWhile
Function
The library function takeWhile selects elements from a list while a predicate holds of all the elements:
1  takeWhile :: (a > Bool) > [a] > [a] 
1  > takeWhile (/= ' ') "abc def" 
7.4.4 The dropWhile
Function
Dually, the function dropWhile removes elements while a predicate holds of all the elements:
1  dropWhile :: (a > Bool) > [a] > [a] 
1  > dropWhile (== ' ') " abc" 
8 Declaring Types and Classes
8.1 Type Declarations
A new name for an existing type can be defined using a type declaration:
1  type String = [Char]  String is a synonym for the type [Char]. 
Type declarations can be used to make other types easier to read. For example, given:
1  type Pos = (Int,Int) 
we can define:
1  origin :: Pos 
However, type declarations cannot be recursive.
1 type Tree = (Int, [Tree])  Wrong!
Like function definitions, type declarations can also have parameters. For example, given:
1  type Pair a = (a,a) 
we can define:
1  mult :: Pair Int > Int 
Example: a phone book type:
1  type PhoneNumber = String 
8.2 Data Declarations
A completely new type can be defined by specifying its values using a data declaration:
1  data Bool = False  True  Bool is a new type, with two new values False and True. 
 The two values False and True are called the value constructors for the type Bool.
 Type and constructor names must always begin with an uppercase letter.
 Data declarations are similar to context free grammars. The former specifies the values of a type, the latter the sentences of a language.
Values of new types can be used in the same ways as those of built in types. For example, given:
1  data Answer = Yes  No  Unknown 
we can define:
1  answers :: [Answer] 
The constructors in a data declaration can also have parameters. For example, given:
1  data Shape = Circle Float  Rect Float Float 
we can define:
1  square :: Float > Shape 
Shape has values of the form Circle r where r is a float, and Rect x y where x and y are floats.
Circle and Rect can be viewed as functions that construct values of type Shape:
1
2 Circle :: Float > Shape
Rect :: Float > Float > Shape
Data declarations themselves can also have parameters. For example, given:
1  data Maybe a = Nothing  Just a 
we can define:
1  safediv :: Int > Int > Maybe Int 
8.3 Newtype Declarations
If a new type has a single constructor witha single argument, then it can also be declared using the newtype
mechanism.
For example, a type of natural numbers:
1  newtype Nat = N Int  the single constructor N takes a single argument of type Int 
8.4 Recursive Types
Types can be recursive through data or newtype declarations:
1  data Nat = Zero  Succ Nat 
A value of type Nat is either Zero, or of the form Succ n where n :: Nat. That is, Nat contains the following infinite sequence of values:
1
2
3
4 Zero
Succ Zero
Succ (Succ Zero)
...We can think of values of type Nat as natural numbers, where Zero represents 0, and Succ represents the successor function 1+:
1
2
3 Succ (Succ (Succ Zero))
= 1+(1+(1+0))
= 3
Using recursion, it is easy to define functions that convert between values of type Nat and Int:
1  nat2int :: Nat > Int 
Two naturals can be added by converting them to integers, adding, and then converting back:
1  add::Nat > Nat > Nat 
However, using recursion the function add can be defined without the need for conversions:
1  add Zero n = n 
1  add (Succ (Succ Zero)) (Succ Zero) 
8.5 Arithmetic Expressions
Using recursion, a suitable new type to represent such expressions can be declared by:
1  data Expr = Val Int 
Example:
1  Add (Val 1) (Mul (Val 2) (Val 3)) 
Using recursion, it is now easy to define functions that process expressions. For example:
1  size :: Expr > Int 
The three constructors have types:
1
2
3 Val :: Int > Expr
Add :: Expr > Expr > Expr
Mul :: Expr > Expr > ExprMany functions on expressions can be defined by replacing the constructors by other functions using a suitable fold function. For example:
1 eval = folde id (+) (*)
8.6 Binary Trees
In computing, it is often useful to store data in a twoway branching structure or binary tree.
Using recursion, a suitable new type to represent such binary trees can be declared by:
1  data Tree a = Leaf a  Node (Tree a) a (Tree a) 
1  t :: Tree Int 
We can now define a function that decides if a given value occurs in a binary tree:
1  occurs :: Ord a => a > Tree a > Bool 
But... in the worst case, when the value does not occur, this function traverses the entire tree.
Now consider the function flatten that returns the list of all the values contained in a tree:
1  flatten :: Tree a > [a] 
A tree is a search tree if it flattens to a list that is ordered. Our example tree is a search tree, as it flattens to the ordered list [1,3,4,5,6,7,9].
Search trees have the important property that when trying to find a value in a tree we can always decide which of the two subtrees it may occur in:
1  occurs x (Leaf y) = x == y 
This new definition is more efficient, because it only traverses one path down the tree.
9 The Countdown Problem
9.1 Basic Concept
Given a sequence of numbers and a target number, attempt to construct an expression whose value is the target, by combining one or more numbers from the sequence using addition, subtraction, multiplication, division and parentheses.
More Rules:
 All the numbers, including intermediate results, must be positive naturals (1,2,3,...).
 Each of the source numbers can be used at most once when constructing the expression.
Example:
1
2
3
4
5
6
7 numbers: 1 3 7 10 25 50
arithemetic operators: +  * ÷
target value: 765
one possible solution: (25  10) * (50 + 1) = 765
9.2 Evaluating Expressions
Operators:
1  data Op = Add  Sub  Mul  Div 
Apply an operator:
1  apply :: Op > Int > Int > Int 
Decide if the result of applying an operator to two positive natural numbers is another such:
1  valid :: Op > Int > Int > Bool 
Expressions:
1  data Expr = Val Int  App Op Expr Expr 
Return the overall value of an expression, provided that it is a positive natural number:
1  eval :: Expr > [Int] 
9.3 Formalising The Problem
Return a list of all possible ways of choosing zero or more elements from a list:
1  choices :: [a] > [[a]] 
For example:
1  > choices [1,2] 
Return a list of all the values in an expression:
1  values :: Expr > [Int] 
Decide if an expression is a solution for a given list of source numbers and a target number:
1  solution :: Expr > [Int] > Int > Bool 
9.4 Brute Force Solution
Return a list of all possible ways of splitting a list into two nonempty parts:
1  split :: [a] > [([a],[a])] 
For example:
1  > split [1,2,3,4] 
Return a list of all possible expressions whose values are precisely a given list of numbers:
1  exprs :: [Int] > [Expr] 
Combine two expressions using each operator:
1  combine :: Expr > Expr > [Expr] 
Return a list of all possible expressions that solve an instance of the countdown problem:
1  solutions :: [Int] > Int > [Expr] 
How Fast Is It?
Can We Do Better?
 Many of the expressions that are considered will typically be invalid  fail to evaluate.
 For our example, only around 5 million of the 33 million possible expressions are valid.
 Combining generation with evaluation would allow earlier rejection of invalid expressions.
9.5 Fusing Two Functions
Valid expressions and their values:
1  type Result = (Expr,Int) 
We seek to define a function that fuses together the generation and evaluation of expressions:
1  results :: [Int] > [Result] 
This behaviour is achieved by defining:
1  results [] = [] 
where:
1  combine' :: Result → Result → [Result] 
Combining results:
1  combine' (l,x) (r,y) = [(App o l r, apply o x y) 
New function that solves countdown problems:
1  solutions' :: [Int] → Int → [Expr] 
How Fast Is It Now?
Can We Do Better?
 Many expressions will be essentially the same using simple arithmetic properties, such as:
x*y = y*x
x*1 = x
 Exploiting such properties would considerably reduce the search and solution spaces.
9.6 Exploiting Properties
Strengthening the valid predicate to take account of commutativity and identity properties:
1  valid :: Op > Int > Int > Bool 
How Fast Is It Now?
10 Interactive Programming
10.1 Basic Concepts
To date, we have seen how Haskell can be used to write batch programs that take all their inputs at the start and give all their outputs at the end.
However, we would also like to use Haskell to write interactive programs that read from the keyboard and write to the screen, as they are running.
10.2 The Problem
Haskell programs are pure mathematical functions:
 Haskell programs have no side effects.
However, reading from the keyboard and writing to the screen are side effects:
 Interactive programs have side effects.
10.3 The Solution
Interactive programs can be written in Haskell by using types to distinguish pure expressions from impure actions that may involve side effects.
1  IO a 
For example:
1  IO Char 
10.4 Basic Actions
The standard library provides a number of actions, including the following three primitives:
The action getChar reads a character from the keyboard, echoes it to the screen, and returns the character as its result value:
1
getChar :: IO Char
The action putChar c writes the character c to the screen, and returns no result value:
1
putChar :: Char > IO ()
The action return v simply returns the value v, without performing any interaction:
1
return :: a > IO a
10.5 Sequencing
A sequence of actions can be combined as a single composite action using the keyword do:
1  act :: IO (Char,Char) 
10.6 Derived Primitives
Reading a string from the keyboard:
1
2
3
4
5
6
7getLine :: IO String
getLine = do x < getChar
if x == '\n' then
return []
else
do xs < getLine
return (x:xs)Writing a string to the screen:
1
2
3
4putStr :: String > IO ()
putStr [] = return ()
putStr (x:xs) = do putChar x
putStr xsWriting a string and moving to a new line:
1
2
3putStrLn :: String > IO ()
putStrLn xs = do putStr xs
putChar '\n'
10.7 Example
We can now define an action that prompts for a string to be entered and displays its length:
1  strlen :: IO () 
For example:
1  > strlen 
Evaluating an action executes its side effects, with the final result value being discarded.
10.8 Hangman
Consider the following version of hangman:
 One player secretly types in a word.
 The other player tries to deduce the word, by entering a sequence of guesses.
 For each guess, the computer indicates which letters in the secret word occur in the guess.
 The game ends when the guess is correct.
We adopt a top down approach to implementing hangman in Haskell, starting as follows:
1  hangman :: IO () 
The action sgetLine reads a line of text from the keyboard, echoing each character as a dash:
1  sgetLine :: IO String 
The action getCh reads a single character from the keyboard, without echoing it to the screen:
1  import System.IO 
The function play is the main loop, which requests and processes guesses until the game ends.
1  play :: String > IO () 
The function match indicates which characters in one string occur in a second string:
1  match :: String > String > String 
For example:
1  > match "haskell" "pascal" 