{- VARIOUS EXAMPLES OF USING HASKELL FOR CSE 505, AUTUMN 2001 This file is on ceylon etc on ~borning/haskell/lecture.hs To load it into Haskell, copy it to your own directory. Start Haskell using hugs lecture.hs Alternatively you can just start Haskell using the command "hugs", then load the file from within Haskell using :load lecture.hs Another useful Haskell command is :set +t which causes Haskell to print type information after evaluation. See the online manuals for more info. This file doesn't include examples of I/O (monads) or read and show. ********************************* Haskell is an example of a pure functional programming language -- there are no side effects. Imperative languages have variables and assignment; they are in effect abstractions of the von Neumann machine. There is no referential transparency. In mathematics, we can substitute equals for equals: if x=y+z then you can substitute y+z for x Informally, in a referentially transparent language you can substitute equals for equals, just as in mathematics. Interesting features of Haskell: truly functional lazy evaluation -- can deal with infinite structures (semantically the same as call by name type system -- statically typed, no type declarations needed; polymorphic future of functional languages ... barriers to adoption: efficiency (a declining problem; also functional languages good candidates for parallel execution) programmer acceptance (a big problem) unnatural for some things, such as interactive I/O (a big problem) -} {- SOME BUILT-IN TYPES: 3 :: Integer 1.0 :: Double 'a' :: Char True :: Bool [1,2,3] :: [Integer] -- lists [1.3,2.8] :: [Double] [True,True,True,False] :: [Bool] "fred" :: String (which is an alias for [Char] [True,3] -- gives a type error -} -- SIMPLE USER-DEFINED TYPES data Color = Red | Green | Blue -- DEFINING A FUNCTION double :: Integer -> Integer double x = 2*x -- Haskell will infer the types of most things, but it's good form to -- declare them (gives machine-checkable documentation). Also the -- inferred type might surprise you by being more general than expected. -- here we haven't declare the type of the triple function -- the inferred type will allow this to work with floats as well as -- integers and uses the type class mechanism (to be discussed later) triple x = 3*x -- SIMPLE RECURSION EXAMPLES -- recursive factorial rec_factorial :: Integer -> Integer rec_factorial n | n==0 = 1 | n>0 = n * rec_factorial (n-1) | n<0 = error "factorial called with n<0" -- white space is significant in parsing Haskell! -- factorial using the built-in prod function -- note that this doesn't check for the case of n<0 factorial :: Integer -> Integer factorial n = product [1..n] -- POLYMORPHIC TYPES (also note use of pattern matching in function def) my_length :: [a] -> Integer my_length [] = 0 my_length (x:xs) = 1 + my_length xs -- CURRYING! plus :: Integer -> Integer -> Integer plus x y = x+y -- note that the type of plus is Integer -> Integer -> Integer, -- NOT (Integer * Integer) -> Integer -- we can apply plus to just one argument (check what the type is of incr) incr = plus 1 -- HIGHER-ORDER FUNCTIONS -- mapping function, like mapcar in Lisp my_map :: (a -> b) -> [a] -> [b] my_map f [] = [] my_map f (a:x) = f a : my_map f x -- try applying my_map to double, factorial, not, etc. -- the types of the argument list and result list can be different on_off :: Bool -> Integer on_off False = 0 on_off True = 1 -- now try my_map on_off [True,True,False] -- ANONYMOUS FUNCTIONS doubletrouble :: Integer -> Integer doubletrouble = \x -> 2*x -- try this: -- my_map (\x -> x+5) [1,2,3] {- STATIC SCOPING Illustrated with several versions of calculating the length of the hypotenuse of a triangle - these all do the same thing) -} hyp x y = let xsq = x*x ysq = y*y sum = xsq + ysq in sqrt sum hyp2 x y = let sum = xsq + ysq xsq = x*x ysq = y*y in sqrt sum hyp3 x y = sqrt sum where sum = x*x + y*y hyp4 x y = sqrt sum where sum = x2 + y2 where x2 = x*x y2= y*y {- LIST COMPREHENSIONS -} -- quicksort qsort [] = [] qsort (a:x) = qsort [ b | b <- x, b<=a ] ++ [a] ++ qsort [ b | b <- x, b>a ] -- all permutations of a list perms [] = [[]] perms x = [ a:y | a <- x, y <- perms (remove a x) ] remove a [] = [] remove a (x:y) | a==x = remove a y | otherwise = x : remove a y -- LAZY EVALUATION AND INFINITE LISTS my_if True x y = x my_if False x y = y -- this works fine: -- my_if (1==2) (1.0/0.0) 5.0 ones = 1 : ones ints n = n : ints (n+1) lets = "abc" ++ lets member x [] = False member x (y:z) | x==y = True | otherwise = member x z -- MEMBER FUNCTION FOR SORTED LISTS smember x [] = False smember x (y:z) | x==y = True | xy = member x z -- SQUARE ROOT sqt x = head (filter close_enough (approximations x)) where approximations a = a : approximations ((a + x/a)/2) close_enough root = abs (x-root*root) < 1.0e-6 -- to show the list of successive approximations: trial_roots x = approximations x where approximations a = a : approximations ((a + x/a)/2) -- lazy evaluation has the same semantics as call by name, but potentially -- better performance {- HIGHER-ORDER FUNCTIONS -} -- double = (*) 2 twice f x = f (f x) -- example: twice double 4 g = twice double my_member a x = or (map (==a) x) -- This version of length uses the built-in const function, -- which is defined as: -- const k x = k clever_length x = sum (map (const 1) x) {- TYPE CLASSES AND OVERLOADING -} {- parametric polymorphism vs overloading. In e.g. Pascal or Ada, + is overloaded. Type classes allow this to be handled cleanly in Haskell. The Prelude includes the following type class: class Eq a where (==) :: a -> a -> Bool This says that the Eq class has a == operation with the given type. Note that we don't want to be able to use the == operation on all types! (It's not decidable in general whether two functions are equal.) Type classes support this. Then the Prelude goes on to use this class: instance Eq Integer where x == y = primEqInteger x y instance Eq Float where x == y = primEqFloat x y == is overloaded. We can extend a type class (i.e. define a subclass): class (Eq a) => Ord a where compare :: a -> a -> Ordering (<), (<=), (>=), (>) :: a -> a -> Bool max, min :: a -> a -> a Multiple inheritance is allowed. The built-in numeric classes include: Int (fixed precision integers) Integer (infinite precision integers) Float Double Now try finding the types of: 3 3.5 triple -} {- TUPLES ('a',True) :: (Char,Bool) -- a tuple Tuples are like records. Tuples have fixed size but allow different types; lists have varying length but each element must be of the same type. -} {- POLYMORPHIC USER DEFINED TYPES -} -- this is similar to the Tree example in the Gentle Introduction, but for -- variety we'll have an EmptyTree constructor, and associate a value with -- each interior node data Tree a = EmptyTree | Node a (Tree a) (Tree a) small :: Tree Integer small = (Node 4 EmptyTree (Node 5 EmptyTree EmptyTree)) big :: Tree Integer big = (Node 10 small (Node 20 EmptyTree small)) -- do a preorder traversal and return the result as a list preorder :: Tree a -> [a] preorder EmptyTree = [] preorder (Node x left right) = [x] ++ preorder left ++ preorder right tree_sum :: Tree Integer -> Integer tree_sum EmptyTree = 0 tree_sum (Node x left right) = x + tree_sum left + tree_sum right -- let's try the same function, but let Haskell infer the type: tsum EmptyTree = 0 tsum (Node x left right) = x + tsum left + tsum right {- SOME MORE EXAMPLES OF USING INFINITE DATA STRUCTURES -} verylargetree :: Tree Integer verylargetree = Node 4 verylargetree verylargetree make_tree :: Integer -> Tree Integer make_tree n = Node n (make_tree (n+1)) (make_tree (2*n)) -- TWO PRIME NUMBER PROGRAMS: factors n = [k | k <- [1..n], n `mod` k == 0] dullprimes = filter isprime [2..] where isprime p = (factors p == [1,p]) interestingprimes = sieve [2..] where sieve (p:x) = p : sieve [n | n <- x, n `mod` p > 0] {- interestingprimes evaluates to [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, (keeps going until you hit control-c) or try take 20 interestingprimes to get the first 20 elements of the list -} {- HAMMING NUMBERS The Hamming numbers are defined as the list of all numbers of the form 2^a * 3^b * 5*c for non-negative integers a, b, and c; in other words, numbers whose only prime factors are 2, 3. and 5. -} my_merge (x:a) (y:b) | xy = y : my_merge (x:a) b ham = 1: my_merge ham2 (my_merge ham3 ham5) ham2 = map (*2) ham ham3 = map (*3) ham ham5 = map (*5) ham {- take 100 ham evaluates to: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80, 81, 90, 96, 100, 108, 120, 125, 128, 135, 144, 150, 160, 162, 180, 192, 200, 216, 225, 240, 243, 250, 256, 270, 288, 300, 320, 324, 360, 375, 384, 400, 405, 432, 450, 480, 486, 500, 512, 540, 576, 600, 625, 640, 648, 675, 720, 729, 750, 768, 800, 810, 864, 900, 960, 972, 1000, 1024, 1080, 1125, 1152, 1200, 1215, 1250, 1280, 1296, 1350, 1440, 1458, 1500, 1536] -}