I. Introduction to Haskell A. context B. advertisment C. History (omit) D. interaction (replaces Davie 2.1) ------------------------------------------ INTERACTING WITH THE INTERPRETER popeye 12% Hugs, The Haskell User's Gofer System ... Copyright (c) Mark P Jones, 1994. Reading script file "/usr/unsup/lib/...": Hugs session for: /usr/unsup/lib/Hugs/hugs.prelude Type :? for help ? [Leaving Hugs] popeye 13% ------------------------------------------ ------------------------------------------ MORE INTERACTION ? ? :type 1 1 :: Num a => a ? 3 + 4 7 ? (+) 3 4 7 ? 216 * 34 7344 ? 7344 / 34 216.0 ? 7 / 3 2.33333 ? div 7 3 2 ? 7 `div` 3 2 ? 7 `rem` 3 1 ? 7 `divRem` 3 ERROR: Undefined variable "divRem" ? 7 `quotRem` 3 (2,1) ? :type 7 `quotRem` 3 quotRem 7 3 :: Integral a => (a,a) ------------------------------------------ ------------------------------------------ WORKING WITH FILES ? :load fact.hs Reading script file "fact.hs": Hugs session for: /usr/unsup/lib/Hugs/hugs.prelude fact.hs ? fact fact {dict} ? :type fact fact :: Integral a => a -> a ? fact 4 24 ? fact 100 0 ? :edit fact.hs Reading script file "fact.hs": Hugs session for: /usr/unsup/lib/Hugs/hugs.prelude fact.hs ? :type fact fact :: Integer -> Integer ? fact 100 9332621544394415268169923885626670049... ? ? :q [Leaving Hugs] ------------------------------------------ ------------------------------------------ popeye 15% hugs fact.hs Hugs, The Haskell User's Gofer System... Copyright (c) Mark P Jones, 1994. Reading script file "/usr/unsup/lib/...": Reading script file "fact.hs": Hugs session for: /usr/unsup/lib/Hugs/hugs.prelude fact.hs Type :? for help ? fact 8 40320 ? :q [Leaving Hugs] ------------------------------------------ ------------------------------------------ LITERATE SCRIPTS file foo.lhs: ============================== A TITLE Some text, whatever you want.. > -- part of a Haskell prog > hd (x:_) = x The blank lines surrounding the program are mandatory. This file should have a .lhs suffix, or use the +l argument to the interpreter. ============================== ? :load foo.lhs Reading script file "foo.lhs": Hugs session for: /usr/unsup/lib/Hugs/hugs.prelude foo.lhs ? hd (3 : (4 : [])) 3 ------------------------------------------ II. Built-in types of Haskell A. Fundamental classification of objects 1. simple (atomic) types (Davie 2.7) ------------------------------------------ HASKELL BOOLEANS Bool Values: + abstract values: true and false + printed: True, False Operations: + literals: True, False + functions: &&, ||, not, ==, /= HASKELL CHARACTERS Char Values: + abstract values: a, b, c, d, ... + printed: 'a', 'b', 'c', ... Operations: + literals: 'a', 'b', .., '\n', .. + functions: ord, chr, isSpace, .. ==, /=, <, <=, ... ------------------------------------------ ------------------------------------------ HASKELL INTEGERS Integer Values: + abstract values: 0, 1, -1, ... + printed: 0, 1, -1, ... Operations: + literals: 0, 1, 2, 3, ... + functions: +, -, *, negate, abs, signum, quot, rem, div, mod, ==, /=, <, <=, ... ------------------------------------------ 2. structured types (Davie 2.8, 3.11, 2.10) a. lists (Davie 2.8, 3.11) ------------------------------------------ LISTS IN HASKELL [a] -- homogeneous lists of a Values: + abstract values: sequences of a's + printed: [], [0], [1,2,3,...] Operations: + literals: [], [True], [1,2,3], [1 ..], ['a' ..], [1,3 ..], [3, 12 ..], [1 .. 10], ['a'..'z'], [1,3 .. 8] [e | e <- [1 ..], even e] + functions: head, tail, last, init, null, ++, length, !!, map, take, ... ------------------------------------------ ------------------------------------------ SOME FUN WITH LISTS (Davie 3.11) LIST COMPREHENSIONS ? [1 ..] ? take 5 [1,2,3,4,5,6,7,8,9,10] ? take 5 [1, ..] ERROR: Syntax error in expression ? take 5 [1 ..] ? take 5 ['a' ..] abcde ? take 5 [1, 3 ..] ? take 5 [3, 1 ..] ? take 5 [1 .. 10] ? take 5 [1,3 .. 8] ------------------------------------------ So what's the type of take? ------------------------------------------ STANDARD LIST OPERATIONS CONSTRUCTION ? [] ? :type [] ? 9 : [] Assume the following definition > lst = ["a","b","c"] ? "hi" : lst; OBSERVATION ? head lst ? tail lst ? lst > (z:zs) = lst ? z ? zs ----------------------------------------- ------------------------------------------ FOR YOU TO DO Complete the following equations 1. head (x : lst) = 2. tail (y : lst) = 3. (head lst) : (tail lst) = 4. null [] = 5. null (x : lst) = Give 2 examples of the following types: 6. [Integer] 7. [Char] 8. [[Integer]] 9. [[[Bool]]] ------------------------------------------ b. String (Davie 2.8) ------------------------------------------ STRINGS IN HASKELL String -- same as [Char] Values: + abstract values: sequences of Chars + printed: a, hello, etc. Operations: + literals: "", "a", "abc", shorthand for: [], ['a'], ['a', 'b', 'c'] also all the list forms ['a' ..], etc. + functions: as for lists, <, <=, >, >=, ==, /=, ... ------------------------------------------ c. pairs, tuples, and unit (Davie 2.10) ------------------------------------------ TUPLES IN HASKELL (a,b), (a,b,c), ..., and () Values: + abstract values: pairs of a & b, triples of a & b & c, ... an empty tuple + printed: (1,True), (3, 4, 5), () Operations: + literals: (1, True), (3, 4, 5), () + no functions! ------------------------------------------ ------------------------------------------ CONSTRUCTING TUPLES ? (1,true) ? (1,2,3) ? (1,(2,3)) ? (1,(true,2.8)) ? ((1,true),2.8) ? (1) ? () ? ("zero tuple:",()) ------------------------------------------ What is the type of each? 3. binding, pattern matching, and simple functions (Davie 2.9, 3.5) ------------------------------------------ PATTERN MATCHING AND BINDING ? fst (1,2) 1 ? snd (1,2) 2 ? fst (1,2,3) ERROR: Type error in application 4. expression : fst (1,2,3) 5. term : (1,2,3) 6. type : (a,b,c) 7. does not match : (d,e) ? let (x,y,z) = (1,2,3) in x ? let (x,y,z) = (1,2,3) in z ? let (_,y,_) = (1,2,3) in y ------------------------------------------ What's the general rule for this kind of pattern matching? ------------------------------------------ PATTERNS IN FUNCTION DEFINITION Suppose we define > yodaize (subject, verb, adjective) = > (adjective, subject, verb) Then we have ? yodaize ("food", "is", "good") ? yodaize ("study", "you", "will") Another example: Problem: write a function to take max of 3 arguments ------------------------------------------ ------------------------------------------ FOR YOU TO DO 1. Define functions fst3 :: (a, b, c) -> a snd3 :: (a, b, c) -> b thd3 :: (a, b, c) -> c such that for all t :: (a, b, c) t = (fst3 t, snd3 t, thd3 t) 2. Define a function average :: (Float, Float) -> Float such that, for example average(1.0, 3.0) = 2.0 average(3.0, 50.0) = 26.5 average(x,y) is the mean of x and y ------------------------------------------ III. lexical matters in Haskell (Davie 2.14, appendix C.2-3) A. identifiers and operators (2.14.2) ------------------------------------------ IDENTIFIERS identifiers (non infix): examples pythag, fac, x, y notes 1. case matters 2. start with lower-case letter 3. must start with lower-case letter, unless constructor or a type identifier, Cons, Typ 4. can use letters, digits, primes and underscores (_) f', x_squared, x3'n_ ------------------------------------------ ------------------------------------------ OPERATORS operators (infix): examples +, -, !!, :, ++, == notes 1. Drawn from: !#$%&*+./<=>?@\^|: 2. A constructor if start with : 3. Any identifier can be made into an operator using backquotes 3 `div` 4 ------------------------------------------ B. layout (2.14.3) ------------------------------------------ LAYOUT MATTERS let x = 3 y = 4 in x + y ==> let {x = 3 ;y = 4 }in x + y ------------------------------------------ IV. data-driven recursion A. example: the natural numbers (Davie sections 3.2, 4.4) ------------------------------------------ DATA-DRIVEN RECURSION Definition of natural numbers: > data Nat = Zero | Succ Nat deriving Eq To define a function f :: Nat -> t define recursively by: f Zero = ... -- basis f (Succ n) = ... -- inductive case Examples: toInteger :: Nat -> Integer plus :: Nat -> Nat -> Nat ------------------------------------------ How does the structure of the program resemble the data declaration? How does the data declaration resemble a grammar? ------------------------------------------ FOR YOU TO DO -- data Nat = Zero | Succ Nat deriving Eq mult :: Nat -> Nat -> Nat equal :: Nat -> Nat -> Bool ------------------------------------------ What would isZero :: Nat -> Bool be like? B. lists 1. examples ------------------------------------------ FLAT RECURSION OVER LISTS data [a] = [] | a : [a] Example: len :: [a] -> Integer ------------------------------------------ So what will the cases be? how do we get 3 from 2? 2. practice ------------------------------------------ FOR YOU TO DO Write a function append :: ([a], [a]) -> [a] so that: append([1,2,3], [4,5]) = [1,2,3,4,5] append([], [7,8]) = [7,8] Write a function equal :: Eq t => [t] -> ([t] -> Bool) so that: equal [] [] = True equal [5,6,7] [5,6,7] = True equal [5,6,7] [5,6,6,7] = False equal [5,6,7] [5,7,7] = False ------------------------------------------ what is the base case? take the above example for the inductive case. what do we want? what are we given? how do you get that? so what are the equations? C. structure of data determines structure of code ------------------------------------------ GENERALIZING HOW TO WRITE RECUSIONS data NonEmptyList a = Write maxl :: (Ord a) => NonEmptyList a -> a such that Write nth :: NonEmptyList a -> Nat -> a such that ------------------------------------------ How would you define a non-empty list in English? can you write this? ------------------------------------------ RECURSION OVER GRAMMARS > data Exp = BoolLit Bool | IntLit Integer > | Sub Exp Exp > | Equal Exp Exp > | If Exp Exp Exp Write the following eval :: Exp -> Exp such that eval (Sub (IntLit 5) (IntLit 4)) = (IntLit 1) ------------------------------------------ What are the base cases? Where should there be a recursion? Examples for each recursive case? D. tail recursion: no pending computation on recursive calls (Davie 3.9) 1. example ------------------------------------------ FULL vs. TAIL RECURSION Fully recursive > len [] = 0 > len (x:xs) = 1 + (len xs) len [5,7,9] = 1 + (len [7,9]) = 1 + (1 + (len [9])) = 1 + (1 + (1 + (len []))) = 1 + (1 + (1 + (0))) = 1 + 1 + 1 = 1 + 2 = 3 ------------------------------------------ ------------------------------------------ TAIL RECURSIVE VERSION ------------------------------------------ 2. practice ------------------------------------------ FOR YOU TO DO Write > reverse :: [a] -> [a] > reverse [] = [] > reverse (x:xs) = (reverse xs) ++ [x] tail recursively. ------------------------------------------ so what is reverse_iter(x:xs,y)? V. types in Haskell (Ch 4 in Davie) A. type operators (Davie 4.1) ------------------------------------------ TYPE NOTATION Type declarations x :: Integer f :: Integer -> Integer Type operators operator meaning ============================= _ -> _ function type (_ , _) product type [ _ ] list type Associativity b f g x means (((b f) g) x) a -> b -> c means a -> (b -> c) ------------------------------------------ Why do you think the associtivity is different for applications and for function types? B. polymorphic types (Davie 4.2) ------------------------------------------ POLYMORPHIC TYPES Monomorphic examples: Integer [Bool] -> Bool [(Integer, Integer) -> Bool] Polymorphic examples: [a] [b] -> b [(c,c) -> Bool] ------------------------------------------ What are some expressions that have these types? What are some instances of these types? C. type synonyms (Davie 4.3.1) ------------------------------------------ TYPE SYNONYMS Examples > type Font = Int > type TextString = [(Font, String)] > type Stack a = [a] > type Queue a = [a] > type Predicate a = (a -> Bool) ------------------------------------------ Does this allow us to pass a (Stack Int) to a function of type [Int] -> Int? D. algebraic types (Davie 4.4) ------------------------------------------ ALGEBRAIC TYPES Can simulate enumerations data Font = Roman | Italic | Bold data Color = data Boolean = Can also be used to define recursive types, including data HaskellType = ------------------------------------------ E. abstract data types (Davie 4.5, 4.9) ------------------------------------------ ABSTRACT DATA TYPES -- file Fraction.hs module Fraction (Fraction, mkFraction, num, denom, add, sub) where data Fraction = Integer :/ Integer mkFraction _ 0 = error "undefined" mkFraction n d = n :/ d num (n :/ d) = n denom (n :/ d) = d add (n1 :/ d1) (n2 :/ d2) = sub (n1 :/ d1) (n2 :/ d2) = ------------------------------------------ ------------------------------------------ FREE TYPES VS. TYPES MODULO LAWS def: a data type is *free* if Examples: def: a data type is *not free* if Examples: ------------------------------------------ Is it ever worthwhile to hide the representation of a free type? F. overview of type inference (Davie 4.7) ------------------------------------------ OVERVIEW OF TYPE INFERENCE Type checking: you declare type, compiler infers type, compiler compares Type inference: compiler infers type In Haskell don't need to declare types (usually) Example > mymap f [] = [] > mymap f (x:xs) = (f x):(mymap f xs) ------------------------------------------ G. ad hoc polymorphism (Davie 4.8) ------------------------------------------ AD HOC POLYMORPHISM parametric polymorphism: map :: (a -> b) -> [a] -> [b] ad hoc polymorphism > square :: Num a => a -> a > square x = x * x ------------------------------------------ Why not require that you actually pass the multiplication yourself? What's done in OO programming? ------------------------------------------ CLASSES IN HASKELL -- standard Eq class class Eq a where (==), (/=) :: a -> a -> Bool x /= y = not (x==y) -- abbreviated Ord class class (Eq a) => Ord a where ordcmp :: a -> a -> Bool -> Bool (<), (<=), (>=), (>) :: a -> a -> Bool max, min :: a -> a -> a ------------------------------------------ ------------------------------------------ DECLARING CLASS INSTANCES > data Prod a b = a :* b > instance (Eq a, Eq b) > => Eq (Prod a b) where > (x :* y) == (x' :* y') = > (x == x' && y == y') or you can write: > data Cartesian a b = a :** b deriving Eq ------------------------------------------ VI. Name binding and scope A. pattern matching in function defs is sugar for case (pp. 29 and 190) How could one define the semantics of Haskell function defs with complex features like guards and pattern matching? ------------------------------------------ FUNCTION DEFINITION SEMANTICS The problem: function defs can be complex > fact 0 = 1 > fact n | n > 0 = n * fact(n-1) > while test f x > | test x = while test f (f x) > | otherwise = x > quotient(i,j) = lastq > where (lasti,lastq) = > (while notdone xform (i,0)) > notdone (i,q) = (i >= j) > xform (i,q) = (i-j,q+1) what does this all mean? ------------------------------------------ What features are being used? ------------------------------------------ SYNTACTIC SUGARS AN EXPLANATORY DEVICE def: a feature of a language is a *syntactic sugar* if Examples: let pi = 3.14159 in pi / 4.0 ==> fact 0 = 1 fact n | n > 0 = n * fact(n-1) ==> ------------------------------------------ ------------------------------------------ FUNCTION BINDING IS SUGAR FOR CASE Function binding form:

11 ...

1n = 1 ...

m1 ...

mn = m ==> FOR YOU TO DO desugar the following > name 0 = "zero" > name 1 = "one" > name n = "many" ------------------------------------------ ------------------------------------------ PATTERN GUARDS SUGAR FOR IF (D 2.7.1) Guard desugaring:

| 1 = 1 | 2 = 2 ... | n = n where { } ==> FOR YOU TO DO Desugar: while test f x | test x = while test f (f x) | otherwise = x ------------------------------------------ ------------------------------------------ SYNTACTIC SUGAR FOR IF if 1 then 2 else 3 ==> case 1 of True -> 2 False -> 3 ------------------------------------------ B. simultaneous binding, lexical scope (D 2.4) ------------------------------------------ SCOPE FOR DECLARATIONS AND LET > x = u + v > y = u - v > (u,v) = (4,5) :: (Integer, Integer) let x1 = u1 + v y1 = u1 - v u1 = 4 :: Integer in [x1,y1,u1,v] ------------------------------------------ What's this like in Scheme? What will that expression's value be? ------------------------------------------ SYNTACTIC SUGAR FOR LET (dynamic behavior, not typing) let

1 = 1 ...

n = n in 0 ==> let (~

1, ..., ~

n) = (1, ..., n) in 0 let

= 1 in 0 ==> let

= fix (\ ~

-> 1) in 0 let

= 1 in 0 -- if no var in

occurs -- free in 1 ==> ------------------------------------------ C. Binding vs. assignment VII. Functions, a built-in, first-class type of Haskell (chapter 5, up to 5.11) A. \ makes functions 1. examples: ------------------------------------------ \ MAKES FUNCTIONS (CLOSURES) ? (\ x -> x) "y" ? ((\ x -> head x) [1,2,3]) -- a la Lisp ? ((\ (x,y) -> 0) (length [1 ..], "hmm")) ? ((\ () -> 5)) ? (\ () -> 5)() ------------------------------------------ 2. normal order evaluation rule ------------------------------------------ NORMAL ORDER EVALUATION ((\ x -> 1) 2) =def= [2/x]1 examples: ((\ z -> z * z + 1) 7) = ((\ (x,y) -> x*y + 3) (5,6)) = ------------------------------------------ How would you implement this kind of parameter passing? B. Functions first-class in Haskell 1. examples ------------------------------------------ SOME SYNTACTIC GAMES > identity :: a -> a > identity = (\ x -> x) > id2 :: a -> a > id2 x = x ? (identity 1) ? id2(1) ? id2 ? id2 id2 3 ------------------------------------------ how is the id2 id2 3 parsed? How to get it to go the other way? 2. functionals ------------------------------------------ FUNCTIONALS > hdtl = \ lst -> head (tail lst) > check x = x > 0 > left (x,y,z) = x > checkleft t = check (left t) ------------------------------------------ ------------------------------------------ USES OF COMPOSE compose(head,tail) [1,2,3] compose(hd,compose(tl,tl)) [1,2,3,4] FOR YOU TO DO (a) Write checkleft, using compose. -- checkleft t = check (left t) (b) define a function b such that b head tail = hdtl ------------------------------------------ ------------------------------------------ THE CURRY FUNCTIONAL > curry f h t = f(h,t) > add :: (Integer, Integer) -> Integer > add (x,y) = x + y > add2 = ((curry add) 2) ? (add2 3) ? (add2 7) ------------------------------------------ 3. closures can you write a function in C which is a curried addition? ------------------------------------------ CURRYING IN C? #include typedef int (*func)(int); int takes_y(int y) { return(x + y); } func cadd(int x) { return(&takes_y); } int main() { printf("%i\n", (cadd(2))(3)); } ------------------------------------------ does this work? ------------------------------------------ CORRECTED C PROGRAM #include typedef int (*func)(int, int); typedef struct { int x; func f; } closure; typedef closure *closurePtr; int add(int x, int y) { return x + y; } closurePtr cadd(int x) { closurePtr c; c = (closurePtr)malloc(sizeof(closure)); c->f = add; c->x = x; return c; } int call_closure(closurePtr c, int arg) { return (c->f)(c->x, arg); } int main() { printf("%i\n", call_closure(cadd(2), 3)); } ------------------------------------------ What in C++ is like a closure? 4. gravitational force example ------------------------------------------ PHYSICS FOR FUNCTIONAL PROGRAMMERS > grav_force_c :: Kg -> Meter -> Kg -> N > grav_force_c m1 r m2 = > if r == 0.0 > then 0.0 > else (big_G * m1 * m2) > / (square r) Type synonyms and other defs used above > type Kg = Float > type Meter = Float > type N = Float > type N_x_m2_per_kg2 = Float > big_G :: N_x_m2_per_kg2 > big_G = 6.670e-11 > square :: Float -> Float > square r = r * r ------------------------------------------ ------------------------------------------ TYPES OF CURRIED FUNCTION APPLICATIONS EXPRESSION TYPE grav_force_c :: Kg -> Meter -> Kg -> N 68.0 :: Kg grav_force_c 68.0 :: 6.0E6 :: Meter grav_force_c 68.0 6.0E6 :: 5.96E24 :: Kg grav_force_c 68.0 6.0E6 5.96E24 :: ------------------------------------------ 5. tool makers a. mapping ------------------------------------------ ABSTRACTING MAPPING PATTERN > add_all :: Num a => a -> [a] -> [a] > add_all s [] = [] > add_all s (x:xs) = (s+x):(add_all s xs) > subst_all new old [] = [] > subst_all new old (x:xs) = > (if x == old then new else x) > : (subst_all new old xs) Can we abstract out this pattern? ------------------------------------------ Can you use map2 to define add_all and subst_all? ------------------------------------------ FOR YOU TO DO > data Tree a = Lf > | Br (a, Tree a, Tree a) Generalize: > preorder Lf = [] > preorder (Br(v,t1,t2)) = > [v] ++ preorder t1 ++ preorder t2 > inc Lf = Lf > inc (Br(v,t1,t2)) = > Br(v+1, inc t1, inc t2) ------------------------------------------ b. combinators ------------------------------------------ COMBINATORS (WITH HISTORICAL NAMES) > b f g x = f(g x) > w f x = ((f x) x) > twice = (w b) > by2 x = 2 * x ? ((twice by2) 7) ------------------------------------------ ------------------------------------------ ENOUGH FOR COMPUTING! > i x = x > k c x = c > s f g x = ((f x) (g x)) FOR YOU TO DO What is: ((k 3) 5) (((s k) k) 3) ------------------------------------------ ------------------------------------------ FIXPOINT COMBINATOR > fix :: ((a -> b) -> (a -> b)) > -> (a -> b) > fix f x = f (fix f) x > fact :: (Integer -> Integer) > -> (Integer -> Integer) > fact f n = > if n == 0 then 1 else n * f(n-1) > factorial = fix fact ? factorial 3 ------------------------------------------ C. functions are the ultimate 1. can be used to implement "infinite" data strucutures 2. can be used to implement arbitrary control structures. D. closures ------------------------------------------ FUNCTION CLOSURES def: a *closure* for a \-expression is > inc1 = let one = 1::Integer > in (\ x -> x + one) ? let one = 2 in inc1(3) ------------------------------------------ 1. environment model 2. the point: static scoping VIII. quiz (just for fun, ah er -- education, not graded) A. Given the following B. Given the following. C. Given the following.