Transcript ppt - Huji cse Moodle 2014/15

haskell-1 ‫תרגיל‬
Catriel beeri
Haskell-1
1
Haskell – a lazy functional language
Haskell is a pure functional language with
 Lazy evaluation
 A sophisticated type system:
 Strong, static (compile time) type checking
 Type inference
 Parametric polymorphism (aka genericity)
 Advanced ad-hoc polymorphism (aka overloading)
Catriel beeri
Haskell-1
2
What is functional programming?
A programming paradigm, very different from
imperative/OO
Characterized by:
 What is does not use
 What is does use
For 1st aspect, we compare to imperative/oo
Catriel beeri
Haskell-1
3
Imperative/OO programming
Main idea:
A program has a state
A computation – evolution of the state towards a
desirable state, where
 The solution to the problem is known
 A task was completed
….
A state – a collection of variables & their values
Catriel beeri
Haskell-1
4
An (assignable) variable – abstraction of a memory cell:
 Contains a value
 Contents can be read
 Contents can be changed by assignment
X=2*y+3


Location managed by system
Size typically determined by system (based on type)
Catriel beeri
Haskell-1
5
Programming constructs:

If/loop statements – control state evolution

Procedures – abstract computations, offer
modularity of state (local variables)

Objects – encapsulate (small) state with operations

Linked data structures are constructed and
manipulated by assigning pointers/references
The assignment statement is the basis
of imperative/oo programming
Catriel beeri
Haskell-1
6
Functional programming
A functional program has no state



No assignable variables (including references)
No assignment statement
No if/loop statements,
Imagine programming in a language
w/o assignment!
Catriel beeri
Haskell-1
7
The main construct of functional programming:
function
Pure, as a mathematical function, w/o side effects
Side effect: a change to the environment
besides the function return value
Functions are first class citizens:


Can be passed as parameters, return values
Can be stored in data structures
Catriel beeri
Haskell-1
8
Functional languages offer:
 Powerful means to
 Define functions
 Combine functions into other functions
 High level declarative, built-in & user-defined, data
structures
The functional paradigm is high-level
Further removed from the hardware
than the imperative/OO paradigms
Catriel beeri
Haskell-1
9
Benefits of functional programming
It is easier to prove properties of pure functions
than of procedures (functions with side effects)
 easier to prove properties of programs
 Functional languages support powerful type
systems (parametric polymorphism, type inference)

(these are difficult in imperative/OO)

Functions with the same in-out relation are
equivalent – can replace each other
referential transparency
 easier to optimize functional programs

Easier to parallelize functional programs
Catriel beeri
Haskell-1
10
Two notes about Haskell

To be practical, Haskell has I/O commands
(procedures with side-effect). These are cleanly
separated from pure functions

Haskell is based on a small set of general ideas; it
will take us some time to see the full picture
Catriel beeri
Haskell-1
11
Our Haskell System
Will use GHC:
 ghc –a compiler
 ghci – for interactive use
(for directives, see the file ghci-directives)

runghc – compile and run
We typically use ghci:
 Write an Haskell file (a script) : name.hs
 Load into ghci using :load name.hs
 Test by writing expressions
Catriel beeri
Haskell-1
12
Sources:
www.haskell.org
Docs:
Hasekll98 report (abbr. HR) – defines the standard
Haskell98 tutorial -- short, but readable, to the point
(both also available from the course home page).
Standard libraries – describes the Haskell libraries
Hoogle and hayoo may be useful later
Catriel beeri
Haskell-1
13
Books:
 www.haskell.org/haskellwiki/Books_and_tutorials
 Programming in Haskell (Hutton) – small, too simple
 Real world Haskell (O’Reilly) – serious, not easy to read
 Introduction to functional programming using
Haskell (2nd ed.) R. Bird) – CS library
Catriel beeri
Haskell-1
14
Basic types, expressions
Type names, some constants (will be explained) begin
with upper; variables with lower
 Bool: True, False, &&, ||, not
 Int8, Int16, Int32, Int (typically 32), Integer (unbounded
size) : +, -, *, `div`, `mod`, …
 Float (don’t use), Double:
+, -, *, /, …
 Char, String, ()
Note: All ops are binary, in infix position
unary minus, -, is the only unary op; wrap in
parentheses! (or write negate)
Catriel beeri
Haskell-1
15
Definitions
A definition associates a variable (an identifier) with an
expression, of any type, including a function
It may be (and should) preceded by a type signature
 Once a variable is bound, this cannot be changed –
no assignment – a new binding means a new scope
Variable as in logic not as in C, C++, Java, …


Top definitions in a file (script) are mutually recursive
Note: in ghci, defs begin with let; in a script, no let
see script1.hs
Catriel beeri
Haskell-1
16
A function definition has the form
f x y z … = expr(x, y, z…)
 Function parameters are not enclosed in ‘(‘ ‘)’
 Functions can be recursive – need an if expression
(for now!)
if e1 then e2 else e3
condition
1st branch
2nd branch
All three must appear
 There is no return statement – a function body is a
single expression, whose value is the result
see script2.hs
Catriel beeri
Haskell-1
17
In Haskell
All functions are unary!
Q: How is that, given g?
A: g applied to the 1st returns a function that accepts the 2nd -see script3.hs
Functions are legal result values!
f 2 5 means (f 2) 5 (application is left associative)
Can apply a function to only some args – the result is a function
Partial application
Catriel beeri
Haskell-1
18
Function application has highest priority
(Don’t write f 2 + 3 if you mean f (2 + 3))
Consequently, very often expressions contain very
few parentheses – need to get used to reading
Catriel beeri
Haskell-1
19
Functions can be arguments to other functions:
> square x = x * x
> apply f x = f (2 * x)
> apply square 3  36
> squareDouble = apply square
> squareDouble 3  36
see script4.hs
Catriel beeri
Haskell-1
20
Operations and functions


Each operation is actually a function, can appear in
prefix position (wrapped in parentheses):
(+) 2 3
A function with >= 2 args can be written in infix
position (after 1st arg) with back quotes:
2 `g` 4, 7 `div` 4, 7 `mod` 4
The only difference between functions and ops is
the syntax – function names are identifiers, op
names are made of symbols -- see HR, p. 10
Catriel beeri
Haskell-1
21
Sections
An operation can be partially applied:
 x^y is ‘x to the power y’ (y integral)
 (^ 2) is the function of x : x^2
 (2 ^) is the function of x :
2^x
 (`div` 3) is the function of x: ?
The function squareDouble can also be defined by
> squareDouble x = square ((2 *) x)
Catriel beeri
Haskell-1
22
Point-free style
The function can also be defined by:
> squareDouble = square . (2 *)
Here, . is the function composition operation
This is called point-free style, meaning:


The parameters are not included
The definition combines functions
Catriel beeri
Haskell-1
23
Function types
e :: t – expression e has type t
A function type is written A  B, where
 A is the in (param) type
 B is the result type
Type signature
Example: (in a script)
> square :: Int  Int
> square x = x * x
Catriel beeri
Haskell-1
24
But, if we just write (w/o a type)
> square x = x * x
The compiler will infer its type:
square :: (Num t) => t  t
Read: For each numeric t it has type t  t
Num is a type class ~ a collection of types
t is a type variable (lower case, typically single letter)
Catriel beeri
Haskell-1
25
Function application is left associative:
f x y ≡ (f x) y
Hence  (in types) is right associative
t1  t2  t3 ≡ t1  (t2  t3)
Catriel beeri
Haskell-1
26


Preferred: write definitions in a file (script) and load
let in front is ghci-unique, not used in scripts!

A variable cannot be define twice in a script

All top defs should be preceded by the type
signature

All top-levels defs should start at same indentation!!

All components (e.g., then, else of an if expression,
if not on same line then same indentation)
Catriel beeri
Haskell-1
27
Definitions with pattern match, guards
pattern
A function can be defined by several equations
fact 0 = 1
pattern
fact n = n * fact (n-1)
Constants and variables are patterns (there are more!)
For a given arg, the patterns are matched in order of
definitions (hence, for the arg 0, only 1st is used)
The above will loop forever on negative arguments
How to prevent?
Catriel beeri
Haskell-1
28
fact 0 = 1
guards
fact n
|n>0
= n * fact (n-1)
| otherwise = error “factorial undefined for …”
A guard is a Bool valued expression
A function can be defined by several equations, each
with a guard
Indentation is important (as usual)
The single guard
| True = exp
is written simply as
= exp
Catriel beeri
Haskell-1
29
Laziness – a peep
Laziness: a variable is bound to an expression, not to
its value; this will be computed if/when needed
This holds also for function arguments
>undef1 = undef1
-- ok, no problem
>undef1
-- Will loop forever
>undef2 = 1 `div` 0
-- ok, no problem
>undef2
-- Will interrupt execution
Haskell contains a constant undefined
Useful for program development
Catriel beeri
Haskell-1
30
In underlying theory, both are the same:  (bottom)
(not a Haskell value)
A function f is strict if
f=
(loops or interrupted on evaluation of the argument)
A language is strict, if all functions in it are strict
(arguments are evaluated before body is entered)
All languages you know are strict, Haskell is not – it is
lazy:
>f x y = 2 * x
>f 3 undef1  6
>f 3 undef2  6
That is just the tip of the iceberg; more later
Catriel beeri
Haskell-1
31
Lists
Powerhorse of functional programming since ~1960
[ ] (nil) – the empty list
[1, 2, 3] :: [Int]
[‘h’,’e’,’l’,’l’,’o’] :: [Char]
[[1,2], [3,4], [7,6]] :: [[Int]]
All elements of a list must be of same type
What is the type of [ ] ?
Catriel beeri
Haskell-1
32
[a, b, c] – external syntax
The true story:
[ ] (nil) – the empty list
(:) (cons) – a binary list constructor
1:[ ] ≡ [1]
3:[2,5,7] ≡ [2,3,5,7] ≡ 1:(2:(:5(:7:[ ])))
Each (finite) list is obtained from [ ] by consing elements
[ ] and (:) are (value) constructors
[ ] – nullary (a constant)
(:) - binary
Discussion – why lists in functional programming
Catriel beeri
Haskell-1
33
Properties of : :
(:) :: a  [a]  [a] (≡ a  ([a]  [a]) )
(:) is right asociative
3:5:7:[ ] ≡ 3(:5:(7: [])))
Internally:
:
Each use of : allocates
3
:
a new cons cell
5
> x = [3,5,7]
7
> y = 2:x
> z = 4:x
y and z share the tail of 3 elements
Catriel beeri
Haskell-1
cons cell
:
[]
34
A string is a list of Chars, shown in a special syntax
> [‘h’,’e’,’l’,’l’,’o’]
“hello” -- :: [Char]
All generic list operations can be used on strings!
A useful function:
show :: a  String (a is a type variable)
Available for many types
Catriel beeri
Haskell-1
35
Basic list functions
In Hasekll, one typically programs on lists by pattern
match (not so in Lisp/Scheme)
null :: [a]  Bool
null [ ] = True
null _ = False
Parentheses are needed
head :: [a]  a
head (x:xs) = x
Note the new patterns
tail :: [a]  [a]
tail (x:xs) = xs
head and tail are partial (non-exhaustive patterns):
head/tail [ ]  Error
Catriel beeri
Haskell-1
36
[a] – the generic list type; can also be written [ ] a
([ ] here is a type constructor)
length :: [a]  Int
length [ ] = 0
length (x:xs) = 1 + length xs
a generic function – works on all lists
> length “hello”  5
so are null, head, tail, and many others
Catriel beeri
Haskell-1
37
Here is a non-generic function
sum [ ] = 0
sum (x:xs) = x + sum xs
> type sum
sum :: (Num a) => [a] -> a
Num a is a context – a constraint on the type variable
a
Catriel beeri
Haskell-1
38
List functions may accept additional params
One may use p.m. on the list param(s), or on others,
or on all
take n xs -- returns a list of first n elems of xs
drop n xs -See ex1 and its solution
Catriel beeri
Haskell-1
39