Copyright c 2006 Zhenjiang Hu, All Right Reserved.

2 ( )

3 (T 1, T 2 ) T 1 T 2 (17.3, 3) :: (Float, Int) (3, 6) :: (Int, Int) (True, (+)) :: (Bool, Int Int Int)

4 (, ) (, ) :: a b (a, b) (,) x y = (x, y) fst, snd: fst :: (a, b) a fst (x, y) = x snd :: (a, b) b snd (x, y) = y

5 (T 1,..., T n ) 1 T 1 n T n (17.3, 3, True) :: (Float, Int, Bool) (3, 6, 7, 8, 9) :: (Int, Int, Int, Int, Int)

6 n (,..., ) (,..., ) :: a 1 a n (a 1,..., a n ) (,..., ) x 1 x n = (x 1,..., x n ) sel n i : sel n i sel n i :: (a 1,..., a i,..., a n ) a i (x 1,..., x i,..., x n ) = x i

7 ax 2 + bx + c = 0 (a, b, c) (r 1, r 2 ) roots :: (Float, Float, Float) (Float, Float) roots (a, b, c) d 0 = (r 1, r 2 ) where r 1 = ( b + r)/(2 a) r 2 = ( b r)/(2 a) r = sqrt d d = b 2 4 a c

8 x/y (x, y) norm (8, 6) (4, 3) norm :: (Int, Int) (Int, Int) norm (x, y) y 0 = (div u d, div v d) where u = (sign y) x v = abs y d = gcd (abs u) v

9 radd :: (Int, Int) (Int, Int) (Int, Int) radd (x, y) (u, v) = norm (x v + u y, y v) rsub :: (Int, Int) (Int, Int) (Int, Int) rsub (x, y) (u, v) = norm (x v u y, y v) rmul :: (Int, Int) (Int, Int) (Int, Int) rmul (x, y) (u, v) = norm (x u, y v) rdiv :: (Int, Int) (Int, Int) (Int, Int) rdiv (x, y) (u, v) = norm (x v, y u)

10 requals :: (Int, Int) (Int, Int) Bool requals (x, y) (u, v) = x v == y u rless :: (Int, Int) (Int, Int) Bool rless (x, y) (u, v) = x v < y u rgreater :: (Int, Int) (Int, Int) Bool rgreater (x, y) (u, v) = x v > y u

11 showrat :: (Int, Int) String showrat (x, y) = let (u, v) = norm (x, y) in if v == 1 then show u else show u ++ / ++ show v

12 ( ) +,,, /, square, ( ), ord, until,... : d dx ::

13 ( ): ( ) :: (β γ) (α β) (α γ) (f g) x = f (g x) (f g) h = f (g h)

14 equality f = g iff x.f x = g x.

15 f :: A B A x g (f x) = x g f f 1 f :: Int (Int, Int) f x = (sign x, abs x) f 1 :: (Int, int) Int f 1 (s, a) = s a

16 f = f (strict function) square(1/0) = three :: Int Int three x = 3 three (1/0) = 3

17 [α] α [1, 2, 3] :: [Int] [ h, e, l, l, o ] :: [Char] [[1, 2], [3]] :: [[Int]] [(+), ( )] :: [Int Int Int] [ ] :: [a] [1, fine day ]

18 [α] 1. [ ] [α] [ ] [α]. 2. x [α] a α a : x [α] 3. [α] a 0 : (a 1 : ( (a n 1 : [ ]))) [a 0, a 1,..., a n 1 ]

19 [ ] : [ ] :: [α] (:) : (:) :: α [α] [α]

20 head :: [α] α head (a : x) = a tail :: [α] [α] tail (a : x) = x

21 null :: [α] Bool null [ ] = True null (a : x) = False

22 length :: [a] Int length [ ] = 0 length (a : x) = 1 + length x length [1, 2, 4, 3, 3] 5

23 sum :: Num a [a] a sum [ ] = 0 sum (a : x) = a + sum x sum [1, 2, 3, 4, 5] 15

24 ( + ) :: [a] [a] [a] ( + ) [ ] y = y ( + ) (a : x) y = a : (( + ) x y) [1, 2, 3] ++ [4, 5, 6, 7] [1, 2, 3, 4, 5, 6, 7] ( + ) :: [a] [a] [a] [ ] ++ y = y (a : x) ++ y = a : (x ++ y)

25 zip :: [a] [b] [(a, b)] zip [ ] [ ] = [ ] zip (a : x) (b : y) = (a, b) : zip x y : zip [1, 2, 3, 4] [11, 12, 13, 14] [(1, 11), (2, 12), (3, 13), (4, 14)]

26 take :: Int [a] [a] take 0 x = [ ] take (n + 1) [ ] = [ ] take (n + 1) (a : x) = a : take n x : take 3 [1, 2, 3, 4] [1, 2, 3]

27 drop :: Int [a] [a] drop 0 x = x drop (n + 1) [ ] = [ ] drop (n + 1) (a : x) = drop n x : drop 3 [1, 2, 3, 4] [4]

28 map :: (α β) [α] [β] map f [ ] = [ ] map f (a : x) = f a : map f x map square [1, 2, 3, 4] [1, 4, 9, 16]

29 filter :: (α Bool) [α] [α] filter p [ ] = [ ] filter (a : x) = if p a then a : filter p x else filter p x filter even [1, 2, 3, 4] [2, 4]

30 foldr :: (a b b) b [a] b foldr ( ) e [ ] = e foldr ( ) e (a : x) = a foldr ( ) e x foldr ( ) e [a 1, a 1, a 3 ] a 1 (a 2 (a 3 e))

31 foldr sum :: [Int] [Int] sum = foldr (+) 0 produt :: [Int] [Int] product = foldr ( ) 1 and :: [Bool] Bool and = foldr ( ) True or :: [Bool] Bool or = foldr ( ) False

32 concat :: [[a]] [a] concat = foldr ( + ) [ ] reverse :: [a] [a] reverse = foldr postfix [ ] where postfix a r = r ++ [a]

33 foldl :: (b a b) b [a] b foldl ( ) e [ ] = e foldl ( ) e (x ++ [a]) = (foldl ( ) e x) a foldl ( ) e [a 1, a 1, a 3 ] ((e a 1 ) a 2 ) a 3 pack foldl pack [x n, x n 1,..., x 0 ] = x n 10 n + x n 1 10 n 1 + + x 0

34 2.4, 2.5, 2.6, 5.1, 5.2, 5.3