Recursion and Induction: Tuples; Types; ListsGreg PlaxtonTheory in Programming Practice, Spring 2005Department of Computer ScienceUniversity of Texas at AustinTuples• The tuple is Haskell’s version of a record• Any nonnegative number of data items (possibly of different types) canbe combined together into a tuple• Syntax: A tuple is surrounded by parentheses; the data items withinthe tuple are separated by commas• Example: (3, 5, "foo", True)• Of course, a component of a tuple can itself be a tuple– Example: (3, (5, "bar", ()), "foo", (True))Theory in Programming Practice, Plaxton, Spring 2005Tuples: The Special Case of a Singleton• Note that Haskell uses parentheses for forming tuples and also forenforcing a particular order of evaluation within an expression• Any expression x is equivalent to the singleton tuple with first (andonly) component x– For example, the expressions "foo", ("foo"), and (("foo")) areall equivalent– Exception: Parentheses are required for writing the empty tuple; forexample, the pair (5, ()) is well-defined and has second componentequal to the empty tuple, while the expression (5, ) is not well-definedTheory in Programming Practice, Plaxton, Spring 2005Tuples: The Special Case of a Pair• A tuple with two components is called a pair• The predefined functions fst and snd are applicable to pairs, andreturn the first and second components of the pair, respectively– Example: fst ((1, 2, 3), True) evaluates to (1, 2, 3)Theory in Programming Practice, Plaxton, Spring 2005Tuples: Fibonacci Revisited• In an earlier lecture we presented the following highly inefficientrecursive program for computing the Fibonacci numbersfib 0 = 0fib 1 = 1fib (n + 2) = (fib n) + (fib (n + 1))Theory in Programming Practice, Plaxton, Spring 2005Tuples: A More Efficient Fibonacci Program• The following function fibpair provides the basis for a more efficientimplementation of fibfibpair 0 = (0,1)fibpair n = (y, x + y)where (x, y) = fibpair (n - 1)• We can then define fib as followsfib 0 = 0fib n = snd (fibpair (n - 1))Theory in Programming Practice, Plaxton, Spring 2005Tuples: A Fundamental Theorem of Number Theory• For any pair of positive integers m and n, there exist integers a and bsuch thata · m + b · n = gcd(m, n)• Exercises:– Prove the above result by induction on pairs of positive integers(m, n)– Prove the above result by induction on m + n– Write a Haskell program which, given a pair of positive integers(m, n), computes a pair (a, b) satisfying the above equationTheory in Programming Practice, Plaxton, Spring 2005Types• Every Haskell expression has a type– The expression ’a’ has type Char– The expression "foo" has type [Char], which denotes a list of Char;we’ll discuss lists in greater detail later– The expression "(’a’, True)" has type (Char, Bool)– The function chr has type Int -> Char; we’ll discuss functiontypes in greater detail on the next slide• For the most part the types are inferred by the type system, ratherthan being explicitly specified by the programmer• You can ask the hugs interpreter to specify the type of any expressionby typing :t followed by the expressionTheory in Programming Practice, Plaxton, Spring 2005Types: Functions• Each function has a type, namely, the types of its arguments in orderfollowed by the type of the result, all separated by ->• Example: Suppose we define the functionsimply p q = not p || qdigit c = (’0’ <= c) && (c <= ’9’)• We can then ask hugs to tell us the types of these functionsMain> :t implyimply :: Bool -> Bool -> BoolMain> :t digitdigit :: Char -> BoolTheory in Programming Practice, Plaxton, Spring 2005Types: Capitalization Rule• Type names are capitalized• The name of a function or parameter is not capitalizedTheory in Programming Practice, Plaxton, Spring 2005Types: Polymorphism• A polymorphic function can accept and produce data of many differenttypes• Haskell allows us to write functions whose arguments can be of anytype, or any type that satisfies some constraintsTheory in Programming Practice, Plaxton, Spring 2005Types: Polymorphism Examples• Consider the following functionsidentity x = xexch (x,y) = (y,x)eqpair (x,y) = x == y• Let’s ask hugs to tell us the type of each of these functions?Main> :t identityidentity :: a -> aMain> :t exchexch :: (a,b) -> (b,a)Main> :t eqpaireqpair :: Eq a => (a,a) -> BoolTheory in Programming Practice, Plaxton, Spring 2005Types: Another Polymorphism Example• Consider a function that sorts the two components of a pair.sortpair (x,y)| x <= y = (x,y)| x > y = (y,x)• The type of sortpair isMain> :t sortpairsortpair :: Ord a => (a,a) -> (a,a)Theory in Programming Practice, Plaxton, Spring 2005Type Classes• Haskell has an extensive type system which we only touch upon in thiscourse• A type class in Haskell represents a set of types, each of which has acertain function (or set of functions) defined on it– The Eq type class consists of all types on which an equality operationis defined– The Ord type class consists of all types on which an order operationis defined– The Num type class consists of all types on which typical arithmeticoperations (+, *, et cetera) are defined• Type classes in functional programming are analogous to classes in inobject-oriented programming, except that a type class does not haveany associated dataTheory in Programming Practice, Plaxton, Spring 2005Type Violations• Since the interpreter can infer the type of each expression, it canautomatically detect type errorsMain> digit "foo"ERROR - Type error in application*** Expression : digit "foo"*** Term : "foo"*** Type : String*** Does not match : CharMain> digit 9ERROR - Illegal Haskell 98 class constraint in inferred type*** Expression : digit 9*** Type : Num Char => BoolTheory in Programming Practice, Plaxton, Spring 2005Lists• A list is like a tuple but all of the elements of a list are required to beof the same type• Square brackets are used to denote a list (as opposed to parenthesesfor tuples)• Of course it is possible to have a list of lists, list of tuples, tuple oflists, list of lists of lists, et cetera• Example: The expression [(3, 5), (3,8), (3, 5)] denotes a listof pairs• Example: The expression [[2], 3, 5, 7] is invalid because theelements are not all of the same type• Example: The expression [] denotes the empty listTheory in Programming Practice, Plaxton, Spring 2005Lists: The Type