| Home / lib / Cs_Computer science / CsPl_Programming languages / | ||
Hutton A. Programming in Haskell (draft, CUP, 2005)(200s)_CsPl_.pdf |
|
Size 0.9Mb Date Dec 28, 2005 |
What is functional programming? Opinions differ, and it is difficult to give a precise definition. Generally sp eaking, however, functional programming can b e viewed as a style of programming in which the basic method of computation is the application of functions to arguments. In turn, a functional programming language is one that supports and encourages the functional style. To illustrate these ideas, let us consider the task of computing the sum of the integers (whole numb ers) b etween one and some larger numb er n . In most current programming languages, this would normally b e achieved using two variables that store values that can b e changed over time, one such variable used to count up to n , and the other used to accumulate the total....
2.2. THE STANDARD PRELUDE • Remove the first n elements from a list: > drop 3 [ 1, 2, 3, 4, 5 ] [ 4, 5 ] • Calculate the length of a list: > length [ 1, 2, 3, 4, 5 ] 5 • Calculate the sum of a list of numb ers: > sum [ 1, 2, 3, 4, 5 ] 15 • Calculate the product of a list of numb ers: > product [ 1, 2, 3, 4, 5 ] 120 • App end two lists: > [ 1, 2, 3 ] + [ 4, 5 ] + [ 1, 2, 3, 4, 5 ] • Reverse a list: > reverse [ 1, 2, 3, 4, 5 ] [ 5, 4, 3, 2, 1 ]...
My first script
When developing a Haskell script, it is useful to keep two windows op en, one running an editor for the script, and the other running Hugs. As an example,...
4. Show how the library function last that selects the last element of a nonempty list could b e defined in terms of the library functions introduced in this chapter. Can you think of another p ossible definition? 5. Show how the library function init that removes the last element from a non-empty list could similarly b e defined in two different ways....
String - strings of characters
This typ e contains all sequences of characters, such as "abc", "1+2=3", and the empty string "". Again, as is standard in most programming languages, strings of characters must b e enclosed in double quotes " "....
All the basic typ es Bool , Char , String , Int , Integer , and Float are instances of the Show class, as are list typ es and tuple typ es, provided that their element and comp onent typ es are instances of the class. For example: > show False "False" > show ’a’ "’a’" > show 123 "123" > show [ 1, 2, 3 ] "[1,2,3]" > show (’a’, False ) "(’a’,False)"...
Hint: take care to include the necessary class constraints if the functions are defined using overloaded op erators. 3. Check your answers to the preceding two questions using Hugs. 4. Why is it not feasible in general for function typ es to b e instances of the Eq class? When is it feasible? Hint: two functions of the same typ e are equal if they always return equal results for equal arguments....
The symb ol | is read as “such that”, and the guard otherwise is defined in the standard prelude simply by otherwise = True . Ending a sequence of guards with otherwise is not necessary, but provides a convenient way of handling “all other cases”, as well as clearly avoiding the p ossibility that none of the guards in the sequence are True , which would result in an error. The main b enefit of guarded equations over conditional expressions is that definitions with multiple guards are easier to read. For example, the library...
Similarly, the library functions nul l , head and tail that decide if a list is empty, select the first element of a non-empty list, and remove the first element of a non-empty list are defined as follows: nul l nul l [ ] nul l ( : ) :: = = [ a ] → Bool True False [a ] → a x [a ] → [a ] xs...
The wildcard pattern is sometimes useful in generators to discard certain elements from a list. For example, a function that selects all the first comp onents from a list of pairs can b e defined as follows: firsts :: firsts ps = [ (a , b ) ] → [ a ] [ x | (x , ) ← ps ]...
For example, the letter ’e’ occurs most often, with a frequency of 12.7%, while ’q’ and ’z’ occur least often, with a frequency of just 0.1%. It is also useful to produce frequency tables for individual strings. To this end, we first define a function that calculates the p ercentage of one integer with resp ect to another, returning the result as a floating-p oint numb er: percent :: Int → Int → Float percent n m = (fromInt n / fromInt m ) ∗ 100...
64 { applying factorial } 3 ∗ (2 ∗ (1 ∗ factorial 0)) = { applying factorial } 3 ∗ (2 ∗ (1 ∗ 1)) = { applying ∗ } 6 =...
that states that product takes a list of integers and produces a single integer. As in this example, it is often useful to b egin with a simple typ e, which can b e refined or generalised later on as appropriate....
Step 3: define the simple cases By definition, removing zero elements from the start of any list gives the same list, so it is straightforward to define the first two cases: drop drop drop drop 0 [] 0 (x : xs ) (n + 1) [ ] (n + 1) (x : xs ) = [] = x : xs = =...
Example - init
As a final example, let us consider how the definition for library function init that removes the last element from a non-empty list can b e constructed. Step 1: define the typ e We b egin with a typ e that states that init takes a list of values of some typ e a , and produces another list of such values: init Step 2: enumerate the cases As the empty list is not a valid argument for init , writing down a skeleton definition using pattern matching requires just one case: init (x : xs ) = Step 3: define the simple cases Whereas in the previous two examples this step was straightforward, a little more thought is required for the function init . By definition, however, removing the last element from a list with one element gives the empty list, so we can introduce a guard to handle this simple case: init (x : xs ) | nul l xs | otherwise = [] = :: [a ] → [a ]...
That is, 1101 represents the sum of the products of the weights 8,4,2,1 with the bits 1,1,0,1, which evaluates to the integer 13. To simplify the definition of certain functions, we assume for the remainder of this example that binary numb ers are written in reverse order to normal. For example, 1101 would now b e written as 1011, with successive bits as we move to the right increasing in weight by a factor of two: 1011 = (1 ∗ 1) + (2 ∗ 0) + (4 ∗ 1) + (8 ∗ 1)...
| © 2007 eKnigu | ||