Functional Programming in Haskell Part 2 : Abstract dataypes and “infinite” structures Madhavan Mukund Chennai Mathematical Institute 92 G N Chetty Rd, Chennai 600 017, India [email protected] ~ http://www.cmi.ac.in/ madhavan MadrasChristianCollege,10December2003–p.1 (cid:17) (cid:4) Computation Rewriting using definitions (cid:4) Functions are associated with input and output types (cid:4) isDigit :: Char -> Bool isDigit ’0’ = True isDigit ’1’ = True ... isDigit ’9’ = True isDigit c = False (cid:4) isDigit c | (c >= ’0’ && c <= ’9’) = True | otherwise = False Haskell review (cid:17) (cid:4) Program Collection of function definitions MadrasChristianCollege,10December2003–p.2 (cid:4) Functions are associated with input and output types (cid:4) isDigit :: Char -> Bool isDigit ’0’ = True isDigit ’1’ = True ... isDigit ’9’ = True isDigit c = False (cid:4) isDigit c | (c >= ’0’ && c <= ’9’) = True | otherwise = False Haskell review (cid:17) (cid:4) Program Collection of function definitions (cid:17) (cid:4) Computation Rewriting using definitions MadrasChristianCollege,10December2003–p.2 (cid:4) isDigit :: Char -> Bool isDigit ’0’ = True isDigit ’1’ = True ... isDigit ’9’ = True isDigit c = False (cid:4) isDigit c | (c >= ’0’ && c <= ’9’) = True | otherwise = False Haskell review (cid:17) (cid:4) Program Collection of function definitions (cid:17) (cid:4) Computation Rewriting using definitions (cid:4) Functions are associated with input and output types MadrasChristianCollege,10December2003–p.2 isDigit ’0’ = True isDigit ’1’ = True ... isDigit ’9’ = True isDigit c = False (cid:4) isDigit c | (c >= ’0’ && c <= ’9’) = True | otherwise = False Haskell review (cid:17) (cid:4) Program Collection of function definitions (cid:17) (cid:4) Computation Rewriting using definitions (cid:4) Functions are associated with input and output types (cid:4) isDigit :: Char -> Bool MadrasChristianCollege,10December2003–p.2 (cid:4) isDigit c | (c >= ’0’ && c <= ’9’) = True | otherwise = False Haskell review (cid:17) (cid:4) Program Collection of function definitions (cid:17) (cid:4) Computation Rewriting using definitions (cid:4) Functions are associated with input and output types (cid:4) isDigit :: Char -> Bool isDigit ’0’ = True isDigit ’1’ = True ... isDigit ’9’ = True isDigit c = False MadrasChristianCollege,10December2003–p.2 Haskell review (cid:17) (cid:4) Program Collection of function definitions (cid:17) (cid:4) Computation Rewriting using definitions (cid:4) Functions are associated with input and output types (cid:4) isDigit :: Char -> Bool isDigit ’0’ = True isDigit ’1’ = True ... isDigit ’9’ = True isDigit c = False (cid:4) isDigit c | (c >= ’0’ && c <= ’9’) = True | otherwise = False MadrasChristianCollege,10December2003–p.2 (cid:4) Define list functions by induction on structure (cid:4) Example Adding up a list of integers sum :: [Int] -> Int sum [] = 0 sum (x:l) = x + (sum l) (cid:4) (Conditional) polymorphism Most general type of sum is sum :: (Num a) => [a] -> a where Num a is true for any type a that supports basic arithmetic operations +, -, . . . Haskell review . . . (cid:4) Basic collective type is a list MadrasChristianCollege,10December2003–p.3 (cid:4) Example Adding up a list of integers sum :: [Int] -> Int sum [] = 0 sum (x:l) = x + (sum l) (cid:4) (Conditional) polymorphism Most general type of sum is sum :: (Num a) => [a] -> a where Num a is true for any type a that supports basic arithmetic operations +, -, . . . Haskell review . . . (cid:4) Basic collective type is a list (cid:4) Define list functions by induction on structure MadrasChristianCollege,10December2003–p.3 sum :: [Int] -> Int sum [] = 0 sum (x:l) = x + (sum l) (cid:4) (Conditional) polymorphism Most general type of sum is sum :: (Num a) => [a] -> a where Num a is true for any type a that supports basic arithmetic operations +, -, . . . Haskell review . . . (cid:4) Basic collective type is a list (cid:4) Define list functions by induction on structure (cid:4) Example Adding up a list of integers MadrasChristianCollege,10December2003–p.3