FUNCTIONAL PROGRAMMING IN HASKELL full report
project topics Active In SP Posts: 2,492 Joined: Mar 2010 
13042010, 06:52 PM
Functional Programming in Haskell.Pdf (Size: 960.59 KB / Downloads: 107) Seminar Report On FUNCTIONAL PROGRAMMING IN HASKELL ABSTRACT As software becomes more and more complex, it is more and more important to structure it well. Wellstructured software is easy to write, easy to debug, and provides a collection of modules that can be reused to reduce future programming costs. Conventional languages place conceptual limits on the way problems can be modularized. Functional languages push those limits back. Writing large software systems that work is difficult and expensive. Maintaining those systems is even more difficult and expensive. Functional programming languages, such as Haskell, can make it easier and cheaper. Haskell is an advanced purely functional programming language. The product of more than twenty years of cutting edge research, it allows rapid development of robust, concise, correct software. With strong support for integration with other languages, builtin concurrency and parallelism, debuggers, profilers, rich libraries and an active community, Haskell makes it easier to produce flexible, maintainable highquality software. KEY WORDS: lambda calculus, pure, currying , lazy evaluation, higher order functions, Lolita, house, list comprehension, tail recursion, adhoc polymorphism. Presented By: SITHARA A DEPARTMENT OF COMPUTER SCIENCE COCHIN UNIVERSITY OF SCIENCE AND TECHNOLOGY CONTENTS 1. INTRODUCTION 5 2. FUNCTIONAL vs. IMPERATIVE PROGRAMMING 6 3. FEATURES OF HASKELL 7 3.1 PURE 7 3.2 STRONGLY TYPED 7 3.3 STATICALLY TYPED 8 3.4 FUNCTIONAL 8 3.5 CURRYING 10 3.6 LIST COMPREHENSIONS 10 3.7 LAZY EVALUATION 12 3.8 RECURSION 14 3.9 HIGHER ORDER FUNCTIONS 15 3.10 POLYMORPHISM 16 4.APPLICATION AREAS 18 4.1 NATURAL LANGUAGE INTERFACES 22 4.2 PARALLEL PROGRAMMING 23 5. HASKELL IN PRACTICE 24 6. CONCLUSION 25 7. REFERENCES 26 1. INTRODUCTION Haskell is a computer programming language. In particular, it is a polymorphically statically typed, lazy, purely functional language, quite different from most other programming languages. The language is named for Haskell Brooks Curry, whose work in mathematical logic serves as a foundation for functional languages. Haskell is based on the lambda calculus; hence the lambda is used as logo. Haskell offers: Â¢ Substantially increased programmer productivity. Â¢ Shorter, clearer, and more maintainable code. Â¢ Fewer errors, higher reliability. Â¢ A smaller "semantic gap" between the programmer and the language. Â¢ Shorter lead times. Haskell is a widespectrum language, suitable for a variety of applications. It is particularly suitable for programs which need to be highly modifiable and maintainable. Much of a software product's life is spent in specification, design and maintenance, and not in programming. Functional languages are superb for writing specifications which can actually be executed and hence tested and debugged. Such a specification then is the first prototype of the final program. Functional programs are also relatively easy to maintain, because the code is shorter, clearer, and the rigorous control of side effects eliminates a huge class of unforeseen interactions. 2. FUNCTIONAL vs. IMPERATIVE PROGRAMMING The functional programming paradigm was explicitly created to support a pure functional approach to problem solving. Functional programming is a form of declarative programming. In contrast, most mainstream languages; including objectoriented programming (OOP) languages such as C#, Visual Basic, C++, and Java were designed to primarily support imperative (procedural) programming. With an imperative approach, a developer writes code that describes in exacting detail the steps that the computer must take to accomplish the goal. This is sometimes referred to as algorithmic programming. In contrast, a functional approach involves composing the problem as a set of functions to be executed. We define carefully the input to each function, and what each function returns. The following table describes some of the general differences between these two approaches. Characteristic Imperative approach Functional approach Programmer focus How to perform tasks (algorithms) and how to track changes in state. What information is desired and what transformations are required. State changes Order of execution Important. Important. Nonexistent. Low importance. Loops, conditionals, and Primary flow control Function calls, including recursion. function (method) calls. Primary manipulation Instances of structures or Functions as firstclass objects and data unit classes. collections. 3. FEATURES OF HASKELL 3.1 PURE Haskell is called pure because it does not allow side effects .A side effect is something that affects the "state" of the world. For instance, a function that prints something to the screen is said to be sideeffecting, as is a function which affects the value of a global variable. Of course, a programming language without side effects would be horribly useless; Haskell uses a system of monads to isolate all impure computations from the rest of the program and perform them in the safe way. Purely functional programs operate only on immutable data. This is possible because on each modification a new version of a data structure is created and the old one is preserved. Therefore, data structures are persistent as it is possible to refer also to old versions of them. If there are no more references to the old version the unrefered data can be collected by automatic memory management, such as a garbage collector. Often, bigger data structures share their parts between versions and do not consume as much memory as all versions separately. Pure computations yield the same value each time they are invoked. This property is called referential transparency and makes possible to conduct equational reasoning on the code. For instance if y = f x and g = h y y then we should be able to replace the definition of g with g = h (f x) (f x) and get the same result, only the efficiency might change. 3.2 STRONGLY TYPED Haskell has the following buildin basic data types: Â¢ Bool : False or True Â¢ Char : the set of Unicode characters Â¢ Integer : arbitraryprecision integer numbers Â¢ Int : fixedprecision integer, at least [229, 2291] Â¢ Float : real floatingpoint number, single precision Â¢ Double : double precision We can use the following ways to define complex data types out of other data types using data constructors : Â¢ Enumeration Â¢ Lists Â¢ Tuples Â¢ Recursion Â¢ List comprehension Enumeration is similar to the code types of Pascal,i.e. we define directly all elements of a data type by explicitly mentioning them. Example: data Weekday = Mo  Tu  We  Th  Fr  Sa  Su Mo, Tu, We, Th, Fr, Sa, Su are the data elements of the type Weekday.They are also socalled constructors (they can be used to construct the data type). Haskell treats lists somewhere between primitive and complex data types, since it already provides list constructors and does not require to explicitly define lists If a denotes a data type, then [a] denotes lists over this data type. [Integer] denotes list containing integers .[] denotes the empty list . The : constructor can also be used to produce lists. Tuples are very similar to the record construct in Pascal. Tuples can either use the tuple constructors (,...,) (with n1 commas, if we define an ntuple) or, for parameterized tuple types, we can define our own constructors. data Date = (Day,Month,Year) data CartProduct a = Prod a a a is here a type variable indicating the parameter of the parameterized type. Haskell allows a programmer to define complex data types using the data statement: data Mybool = MyFalse  MyTrue 3.3 STATICALLY TYPED Haskell's static type system defines the formal relationship between types and values .The static type system ensures that Haskell programs are type safe; that is, that the programmer has not mismatched types in some way. For example, we cannot generally add together two characters, so the expression 'a'+'b' is illtyped. The main advantage of statically typed languages is wellknown: All type errors are detected at compiletime. Not all errors are caught by the type system; an expression such as 1/0 is typable but its evaluation will result in an error at execution time. Still, the type system finds many program errors at compile time, aids the user in reasoning about programs, and also permits a compiler to generate more efficient code (for example, no runtime type tags or tests are required). The type system also ensures that usersupplied type signatures are correct. In fact, Haskell's type system is powerful enough to allow us to avoid writing any type signatures at all; we say that the type system infers the correct types for us. Nevertheless, judicious placement of type signatures is a good idea, since type signatures are a very effective form of documentation and help bring programming errors to light. Haskell automatically infers the most general type. For example, the type of foldr is inferred to be: (a>b>b)>b>[a]> b, which can be read as follows: foldr takes as argument a binary operator, whose input values can be of any types a and b and whose output value is of type b, and returns as its result a function f' which takes a value of type b as input and which returns as its result a function f'' which takes a list of values of type a as input, and which returns as its result a value of type b. The inferred type of foldr shows that it can also be used to define functions where the input types of its first operator argument are different. 3.4 FUNCTIONAL In a functional language, everything (even a program) is a function. Thus, writing a program is actually writing a function. We can write many functions in a single file; that is, we can have many programs in a single file. Each function then may use other functions to calculate its result. There are many predefined functions available like in other programming languages. These functions are included in the Haskell Prelude and in the Haskell Libraries. Writing a function consists of two parts. First, we have to define the types for the arguments and the result. e.g.: doubleIt :: Integer > Integer The name of our new function is doubleIt. The separates the name of the function from the type definition. The parameter types are separated from each other and from the return type by >. Therefore, the declaration above reads "doubleIt is a function with one Integer parameter, returning Integer." The second part of writing a function is the concrete implementation, e.g.: doubleIt x = 2 * x The different methods for defining functions are Pattern matching fac :: Int > Int fac 0 = 1 fac n = n * fac (n1) Conditional expression sign1 Int > String sign1 x = if x < 0 then "negative" else if x > 0 then "positive" else "zero" Guards ab :: Int > Int ab n  (n>=0) = n  otherwise = (n) Case statement cas Int > Int cas x = case x of 0 > 1 1 > 5 2 > 2 "where" clause to hold local definitions sumSq Int > Int > Int sumSq x y = sqX + sqY where sqX = x * x sqY = y * y 3.5 CURRYING Currying is the process of transforming a function that takes multiple arguments into a function that takes just a single argument and returns another function if any arguments are still needed. f a > b > c is the curried form of g (a, b) > c We can convert these two types in either directions with the Prelude functions curry and uncurry. f = curry g g = uncurry f Both forms are equally expressive. It holds f x y = g (x,y) , however the curried form is usually more convenient because it allows partial application. add Int > Int > Int add x y = x + y addOne = add 1 In this example, addOne is the result of partially applying add. It is a new function that takes an integer, adds 1 to it and returns that as the result. The important property here is that the > operator is right associative, and function application is left associative, meaning the type signature of add actually looks like this: add :: Int > (Int > Int) This means that add actually takes one argument and returns a function that takes another argument and returns an Int. In Haskell, all functions are considered curried: That is, all functions in Haskell take just single arguments. This is mostly hidden in notation, and so may not be apparent. Let's take the function div Int > Int > Int which performs integer division. The expression div 11 2 unsurprisingly evaluates to 5. But there's more that's going on than immediately meets the untrained eye. It's a twopart process. First, div 11 is evaluated and returns a function of type Int > Int Then that resulting function is applied to the value 2, and yields 5. We'll notice that the notation for types reflects this: we can read Int > Int > Int incorrectly as "takes two Ints and returns an Int", but what it's really saying is "takes an Int and returns something of the type Int > Int"  that is, it returns a function that takes an Int and returns an Int. (One can write the type as Int x Int > Int if we really mean the former  but since all functions in Haskell are curried, that's not legal Haskell. Alternatively, using tuples, we can write (Int, Int) > Int, but keep in mind that the tuple constructor (,) itself can be curried.Much of the time, currying can be ignored. The major advantage of considering all functions as curried is theoretical: formal proofs are easier when all functions are treated uniformly (one argument in, one result out). 3.6 LIST COMPREHENSIONS List comprehension is a syntactic construct available in some programming languages for creating a list based on existing lists. It follows the form of the mathematical setbuilder notation (set comprehension.) as distinct from the use of map and filter functions.Consider the following example in set builder notation. 5={2IIGM, x1 > 3 } This can be read, "S is the set of all 2*x where x is an item in the set of natural numbers, for which x squared is greater than 3." In the example: Â¢ x is the variable representing members of an input set. Â¢ The input set is N. Â¢ x2 > 3 is a predicate function acting as a filter on members of the input set. Â¢ And 2  Xis an output function producing members of the new set from members of the input set that satisfy the predicate function. The brackets contain the expression and the vertical bar and comma are separators. A list comprehension has the same syntactic components to represent generation of a list in order from an input list or iterator: Â¢ A variable representing members of an input list. Â¢ An input list (or iterator). Â¢ An optional predicate expression. Â¢ And an output expression producing members of the output list from members of the input iterable that satisfy the predicate. Lists are to declarative languages what arrays are to imperative languages. Becuase lists are so widely used, a special notation has been introduced in Haskell for constructing lists. This notation is called list comprehension (in analogy with set comprehension in set theory). In Haskell's list comprehension syntax, this setbuilder construct would be written similarly, as: s = [ 2*x I x < [0..], xA2 > 3 ] Here, the list [0..] represents N, xA2>3 represents the predicate, and 2*x represents the output expression. Suppose xs is the list [1,2,3,4,5,6], then the set comprehension [ 2*x  x < xs ] denotes the list [2,4,6,8,10,12], obtained by multiplying each list in xs by 2. In a list comprehension [ E I P < LExp ], we refer to E as the body and P < lExp as the selector; note that LExp can be any expression of a list type, P can be a pattern, and E any expression containing the variables in P.The order of generation of members of the output list is based on the order of items in the input. List comprehensions give results in a defined order, (unlike the members of sets); and list comprehensions may generate the members of a list in order, rather than produce the entirety of the list thus allowing, for example, the previous Haskell definition of the members of an infinite list. 3.7 LAZY EVALUATION Lazy evaluation (or delayed evaluation) is the technique of delaying a computation until such time as the result of the computation is known to be needed. The actions of lazy evaluation include: performance increases due to avoiding unnecessary calculations, avoiding error conditions in the evaluation of compound expressions, the ability to construct infinite data structures, and the ability to define control structures as regular functions rather than builtin primitives. Languages that use lazy actions can be further subdivided into those that use a callbyname evaluation strategy and those that use callbyneed. Most realistic lazy languages, such as Haskell, use callbyneed for performance reasons, but theoretical presentations of lazy evaluation often use callbyname for simplicity. The opposite of lazy actions is eager evaluation, also known as strict evaluation. Eager evaluation is the evaluation behavior used in most programming languages. Haskell evaluates expressions using lazy evaluation: 1. No expression is evaluated until its value is needed. 2. No shared expression is evaluated more than once; if the expression is ever evaluated then the result is shared between all those places in which it is used. Lazy functions are also called nonstrict and evaluate their arguments lazily or by need. 3.8 RECURSION In imperative languages to perform repeated operations we make use of loops.This isn't directly possible in Haskell, since changing the value of the would not be allowed. However, we can always translate a loop into an equivalent recursive form. The idea is to make each loop variable in need of updating into a parameter of a recursive function.But recursion is expensive in terms of both time and space. When a function is called, the computer must "remember" the place it was called from, the return address, so that it can return to that location with the result once the call is complete. Typically, this information is saved on the stack, a simple list of return locations in order of the times that the call locations they describe were reached. Sometimes, the last thing that a function does after completing all other operations is to simply call a function, possibly itself, and return its result. But in this case, there is no need to remember the place we are calling from â€ instead, we can leave the stack alone, and the newly called function will return its result directly to the original caller. Converting a call to a branch or jump in such a case is called a tail call optimization. Note that the tail call doesn't have to appear lexically after all other statements in the source code; it is only important that its result be immediately returned, since the calling function will never get a chance to do anything after the call if the optimization is performed. Tail recursion (or tailend recursion) is a special case of recursion in which the last operation of the function is a recursive call. Such recursions can be easily transformed to iterations. Replacing recursion with iteration, manually or automatically, can drastically decrease the amount of stack space used and improve efficiency. This technique is commonly used with functional programming languages, where the declarative approach and explicit handling of state promote the use of recursive functions that would otherwise rapidly fill the call stack. 3.9 HIGHER ORDER FUNCTIONS A higher order function is a function that takes other functions as arguments or returns a function as result.The three most useful higher order functions are map, fold and filter. map : It takes in two inputs  a function, and a list. It then applies this function to every element in the list. map (a > b) > [a] > [b] map f xs = [ f x  x < xs ] Main> map (+1) [1..5] [2, 3, 4, 5, 6] fold : fold takes in a function and folds it in between the elements of a list. fo foldl :: (a > b > a) > a > [b] > a foldl f z [] = z foldl f z (x:xs) = foldl f (f z x) xs The command to add the first 5 numbers with fold. foldl (+) 0 [1..5] Fold take the elements of the list and write them out separately with a space between each. 1 2 3 4 5 And now we fold the function into the elements. To do this, we write the function in the empty spaces between the elements. 1 + 2 + 3 + 4 + 5 Note that there's nothing before the first (+). That's because we can specify a starting point. So that's the second input foldl asks for  a starting point. In this case, we said zero, so we'll put it in there. 0 + 1 + 2 + 3 + 4 + 5 And all this gives us the final result Main> foldl (+) 0 [1..5] 15 And if we change the starting point, we get the corresponding answer. Main> foldl (+) 1 [1..5] 16 Main> foldl (+) 10 [1..5] 25 We can also go through the list from right to left, rather than left to right. That's why we use foldl and foldr. There are cases where folding from the left gives us different results to folding from the right. It all depends on what function we're folding. For example, Main> foldr (div) 7 [34,56,12,4,23] 8 Main> foldl (div) 7 [34,56,12,4,23] 0 filter : It takes in a 'test' and a list, and it chucks out any elements of the list which don't satisfy that test. filter :: (a > Bool) > [a] > [a] filter p xs = [ x I x < xs, p x ] Main> filter (even) [1..10] [2, 4, 6, 8, 10] Main> filter (>5) [1..10] [6, 7, 8, 9, 10] 3.10 POLYMORPHISM Polymorphism is a programming language feature that allows values of different data types to be handled using a uniform interface. The concept of parametric polymorphism applies to both data types and functions. A function that can evaluate to or be applied to values of different types is known as a polymorphic function. A data type that can appear to be of a generalized type (e.g., a list with elements of arbitrary type) is designated polymorphic data type like the generalized type from which such specializations are made. There are two fundamentally different kinds of polymorphism. If the range of actual types that can be used is finite and the combinations must be specified individually prior to use, it is called Adhoc polymorphism. If all code is written without mention of any specific type and thus can be used transparently with any number of new types, it is called parametric polymorphism. Haskell is a strongly typed language, which means that every expression has a type, and that the interpreter can infer the type of an expression from the types of its subexpressions. All the list operators, functions and expressions have types.Let's look at the length function. Clearly, length returns a number of some kind; in fact, it returns a 32bit integer, i.e., an Int. And clearly it takes a list as argument, but what kind of list? The answer is that it takes any kind of list as argument: length :: [a] > Int The type of length's argument is [a], which means a list whose elements are of any type a. This a is simply a name standing for any Haskell type; when we evaluate length "word", for example, the a stands for (or more precisely, is instantiated to) Char, and when we evaluate length [(1,2)], the a stands for (is instantiated to) (Int,Int). This is an example of parametric polymorphism, In Haskell, type classes provide a structured way to control ad hoc polymorphism, or overloading.Let's start with a simple, but important, example: equality. There are many types for which we would like equality defined, but some for which we would not. For example, comparing the equality of functions is generally considered computationally intractable, whereas we often want to compare two lists for equality. To highlight the issue, consider this definition of the function elem which tests for membership in a list: x velerrT [] = False x velemv (y:ys) = x==y II (x velemv ys) Intuitively speaking, the type of elem "ought" to be: a>[a]>Bool. But this would imply that == has type a>a>Bool, even though we just said that we don't expect == to be defined for all types.Furthermore, even if == were defined on all types, comparing two lists for equality is very different from comparing two integers. In this sense, we expect == to be overloaded to carry on these various tasks. Type classes conveniently solve both of these problems. They allow us to declare which types are instances of which class, and to provide definitions of the overloaded operations associated with a class. Defining classes in Haskell class Eq a where (==), (/=) ::a>a>Bool Creating Instance of Class Eq instance Eq Integer where x == y = x vintegerEqv y instance Eq Float where x == y=x vfloatEqv y Class Extension classEq a) =>Orda where (<),(<=),(>=),(>)::a>a>Bool max,min:: a > a > a Type Classes in Haskell 4. APPLICATION AREAS 4.1 NATURAL LANGUAGE INTERFACES Parser combinators LFP has been used in a conventional way to implement a range of parsers that have already been implemented in other programming languages. parser combinators is an approach to parser construction which is unique to functional programming. The use of parser combinators was first proposed by Burge in 1975, The idea is to construct more complex language processors from simpler processors by combining them using higherorder functions (the parser combinators). This approach was developed further by Wadler [1985] who suggested that recognizers and parsers should return a list of results. Multiple entries in the list are returned for ambiguous input, and an empty list of successes denotes failure to recognize the input. Fairburn promoted combinator parsing by using it as an example of a programming style in which form follows function: a language processor that is constructed using parser combinators has a structure which is very similar to the grammar defining the language to be processed. Construction of Morphologies A morphology is a system which explains the internal structure of words. Regular nouns have relatively simple morphological structure. For example, "cat", "cat"++"s", and "cat"++"'"++"s", whereas irregular nouns and verbs have more complex morphology. The morphology of a particular language can be defined using a set of inflection tables. The conventional approach to morphological recognition is to compile the tables into finite state automata, and then to parse words as regular expressions.As an alternative, Pembeci [1995] has built a morphological analyzer for Turkish using parser combinators implemented in Miranda and claims that the analyzer can parse approximately 99% of all word forms in Turkish. Pembeci also claims that all morphological processes have been implemented, and that a number of advantages result from use of parser combinators, including clarity and modifiability of the code. Forsberg [2004], and Forsberg and Ranta [2004] have developed an alternative approach, called Functional Morphology which is implemented in Haskell. It is based on Huet's toolkit, Zen, [Huet 2003, 2004] which Huet used to build a morphology for Sanskrit. In this approach, inflection parameters are defined using algebraic data types,and paradigm tables are implemented as finite functions defined over these types. Semantic analysis Computationallytractable versions of Montaguelike semantic theories can be implemented in LFP by the direct encoding of the higherorder functional semantics. 4.2 PARALLEL PROGRAMMING Nested Data Parallelism Nested DP is great for programmers due to its modularity. It opens up a much wider range of applications: Â¢ Sparse arrays, variable grid adaptive methods (e.g. BarnesHut) Â¢ Divide and conquer algorithms (e.g. sort) Â¢ Graph algorithms (e.g. shortest path, spanning trees) Â¢ Physics engines for games, computational graphics (e.g. Delauny triangulation) Machine learning, optimisation, constraint solving. 5. HASKELL IN PRACTICE LOLITA : LOLITA is a natural language processing (NLP) system providing both core NLP capabilities and a number of prototype applications. The core of the system is based on three main capabilities: 1. conversion of English language text to an internal (semantic network based) representation of the text's meaning 2. inferences in the semantic network 3. conversion of portions of the semantic network to English Linkchk : Linkchk is a network interface link ping monitor. It supports both IPv4 and IPv6. It works by monitoring the routing table and pinging the gateway (next hop) of a network interface. When the link is up and functioning the ping time is displayed in a small gtk window, otherwise the link status is displayed. linkchk can also run in a tty. HWSWP : The Haskell WebServer With Plugins (HWSWP) is a. simple HTTP server written in Haskell, originally implemented by Simon Marlow and updated by Martin Sjogren. Hoogle : Hoogle is a Haskell API search engine. It allows us to search by either name, or by approximate type signature. The standard web interface to Hoogle is available at http://haskell.org/hoogle/. House : Haskell User's Operating System and Environment./Zowse is a demo of software written in Haskell, running in a standalone environment. It is a system than can serve as a platform for exploring various ideas relating to lowlevel and systemlevel programming in a highlevel functional language. 6. CONCLUSION Haskell 98 is complete and is the current official definition of Haskell. We expect that this language will be supported in the long term even as new extensions are added to Haskell; compilers will continue to support Haskell 98 (via a special flag). The language evolves and numerous extensions have been proposed and many of them have been implemented in some Haskell systems; for example pattern guards, scoped type variables, multiparameter type classes, local universal and existential quantification. The Haskell mailing lists are a forum for discussing new language features. Haskell' is the next official version. REFERENCES [1] http://www.haskell.org [2] http://haskell.org/ghc/docs/latest/html/...elude.html [3] www.c s .utah.edu/~hal/doc s/daume02yaht.pdf [4] http://www.iceteks.com/articles.php/haskell [5] Introduction to functional programming Richard Bird ;Philip Walder Use Search at http://topicideas.net/search.php wisely To Get Information About Project Topic and Seminar ideas with report/source code along pdf and ppt presenaion



seminar class Active In SP Posts: 5,361 Joined: Feb 2011 
28032011, 09:39 AM
presented by:
Graham Hutton functional.ppt (Size: 1.23 MB / Downloads: 70) What is Functional Programming? z Functional programming is style of programming in which the basic method of computation is the application of functions to arguments; z A functional language is one that supports and encourages the functional style. Example Why is it Useful? z This Course What is Hugs? z An interpreter for Haskell, and the most widely used implementation of the language; z An interactive system, which is wellsuited for teaching and prototyping purposes; Hugs is freely available from: z The Standard Prelude z Function Application Examples z My First Script z Exercises z What is a Type? z Types in Haskell z Basic Types z List Types z Tuple Types z Function Types z Exercises z Curried Functions z Curry Conventions z The arrow ® associates to the right. z Polymorphic Types z Overloaded Types z Classes in Haskell z Exercises z Conditional Expressions z Guarded Equations z Pattern Matching z List Patterns z Lambda Expressions z Why Are Lambda's Useful? z Exercises z Set Comprehensions z Lists Comprehensions z Dependant Generators z Guards z Exercises z Introduction z Recursive Functions Why is Recursion Useful? z Some functions, such as factorial, are simpler to define in terms of other functions; z In practice, however, most functions can naturally be defined in terms of themselves; z Properties of functions defined using recursion can be proved using the simple but powerful mathematical technique of induction. 


