CSE 130 Lecture Notes

CSE130 LECTURE NOTES

January 31, 2001

MISCELLANEOUS

Remember to

check the Web board for FAQs and post questions there
study the lecture notes on the class page! (they may be updated to take into account questions that came up etc. and give additional explanations!)
ask when you have questions: e.g., there is the Web board, the office hours, the discussion sections, and the lecture!!
When you call the Hugs system you should do so with the option: "+t", so the system reports all types automatically:
```
        % hugs +t
	Hugs> length [2,2,1]
	3 :: Int
	Hugs> 1 + 3.4
	4.4 :: Double
```
If you add also the option "+s" some statistics on the number of reductions and memory cells are given, which can be useful to compare the efficiency of different implementations of the same function:
```
	Hugs> sum [1,2,3,4]
	10 :: Integer
	(33 reductions, 44 cells)
	Hugs> sum' [1,2,3,4]
	10 :: Integer
	(31 reductions, 37 cells)
```

PROGRAMMING WITH LISTS AND HIGER ORDER FUNCTIONS

Here are some typical "list processing" functions that give you some idea of how to write simple functional programs. When then type of a function is not given, try to infer the type; then double check with the Hugs systems (use the abovementioned options "+t" when calling Hugs or use the ":info" command).

In your assignments, you should always

declare the function type, i.e., give the signature
add "good" comments which capture the main points of the function


append	:: [a] -> [a] -> [a] 
-- takes two lists of the same input type [a] 
-- ... and returns the appended result
-- ... thus append xs ys = zs 
-- ...     iff zs is the concatenation of xs and ys
append [] ys		= ys
append (x:xs) ys	= x : append xs ys


member x []		= False
member x (y:ys)		= if x==y 
				then True
				else member x ys

length' []		= 0
length' (x:xs)		= 1 + length' xs


sum' []			= 0
sum' (x:xs)		= x + sum' xs


product' []		= 1
product' (x:xs)		= x * product' xs


concat' []		= []
concat' (x:xs)		= x ++ concat' xs

The last four functions all have a very similar "recursion pattern" although they define very different things. Let's look, for example, how "sum'" works:

sum' [1,2,3,4] 
==> 1 + sum' [2,3,4] 
==> 1 + (2 + sum' [3,4]) 
==> 1 + (2 + (3 + sum' [4]))
==> 1 + (2 + (3 + (4 + sum' [])))
==> 1 + (2 + (3 + (4 + 0)))
==> 10 
Hugs> 10 :: Integer 
(31 reductions, 37 cells)

Let's compare it to "product'":

product' [1,2,3,4] 
==> 1 * product' [2,3,4] 
==> 1 * (2 * product' [3,4]) 
==> 1 * (2 * (3 * product' [4]))
==> 1 * (2 * (3 * (4 * product' [])))
==> 1 * (2 * (3 * (4 * 1)))
==> 24 
Hugs> 24 :: Integer
(31 reductions, 41 cells)

So both functions can be seen as folding a list using a operation "o" (for sum' it is "+", for product' it is "*") and some "start element" e: 0 (for sum') or 1 (for product').

Let's abstract the sum' and product' to a function "fold_o_e", the operations "+" and "*" to some "o" and the start element to "e":

fold_o_e [x1,x2,x3,x4] 
==> x1 o fold_o_e [x2,x3,x4] 
==> x1 o (x2 o fold_o_e [x3,x4]) 
==> x1 o (x2 o (x3 o fold_o_e [x4]))
==> x1 o (x2 o (x3 o (x4 o fold_o_e [])))
==> x1 o (x2 o (x3 o (x4 o e)))

Indeed, we can define a higher-order function "foldr" (pronounced "fold right" because it folds by associating to the right) as follows:

foldr            :: (a -> b -> b) -> b -> [a] -> b
foldr f e []      = e
foldr f e (x:xs)  = f x (foldr f e xs)

Using this we can now simply define

sum''		= foldr (+)  0
product''	= foldr (*)  1
concat''	= foldr (++) []

Let's try to understand this:

sum'' [1,2,3,4] 
==> foldr (+) 0 [1,2,3,4] 
...
==> 10 :: Int
(25 reductions, 32 cells)

Comparing this to the signature of foldr we see:

foldr :: (a -> b -> b) -> b -> [a]         -> b
           
         (+)              0    [1,2,3,4]      10
         (*)              1    [1,2,3,4]      24

So the types are: a = b = Int:

foldr :: (Int -> Int -> Int) -> Int -> [Int]        -> Int
           
         (+)                    0      [1,2,3,4]       10
         (*)                    1      [1,2,3,4]       24

How does this look in the case of concat ["Joyce", "James"]? Let's first note that we can view "Joyce" and "James" as character arrays:

Hugs> "Joyce" :: [Char]		-- the usual syntax with double quotes
"Joyce" :: [Char]
(103 reductions, 138 cells) 

Hugs> ['J','o','y','c','e']	-- or as a character array (single quotes)
"Joyce" :: [Char]		-- ... is really the same thing!
(103 reductions, 133 cells)

So now we are less surprised to get results like the following:

Hugs> concat ["Joyce", "James"]
"JoyceJames" :: [Char]
(208 reductions, 292 cells)

Hugs> length (concat ["Joyce", "James"])
10 :: Int
(94 reductions, 134 cells)

The latter examples shows function composition, i.e., we are applying a function f (here: length) to the result of another function application g(...) (here: concat ["Joyce","James"]).
Note that the parentheses around concat ["Joyce","James"] are important! Otherwise the Hugs would assume that length is called with 2 arguments (the function "concat" and the list ["Joyce","James"]):

Hugs> length concat ["Joyce", "James"]
ERROR: Type error in application
*** Expression     : length concat ["Joyce","James"]
*** Term           : length
*** Type           : [a] -> Int
*** Does not match : b -> c -> d

Here is another example for composition: assume factors returns the list of factors of a number. Then we can define a test

    
perfect n	= sum (factors n) == n

Q:Can you infer the type of perfect? Let's look again how the folding works here:

foldr :: (a -> b -> b) -> b -> [a] ->             b
           
         (++)             []   ["Joyce","James"]  ["JoyceJames"]

So the types are: a = b = [Char]!

Q: How can we define length using foldr? How would a "folding to the left", i.e., foldl look like? With this, many apparently unrelated functions turn out to be instances of the same "recursion pattern":

sum, product     :: Num a => [a] -> a
sum               = foldl (+) 0
product           = fold' (*) 1

concat           :: [[a]] -> [a]
concat            = foldr (++) []

This concludes our introduction to Haskell (although we will be it throughout the rest of the class to illustrate general concepts, e.g., ADTs...)

ABSTRACT DATA TYPES (ADTs)

updated: see lecture notes from Feb. 5th.