## Csce 314 Assignment 8 Tutoria

## Presentation on theme: "Lee CSCE 314 TAMU 1 CSCE 314 Programming Languages Haskell: Higher-order Functions Dr. Hyunyoung Lee."— Presentation transcript:

1 Lee CSCE 314 TAMU 1 CSCE 314 Programming Languages Haskell: Higher-order Functions Dr. Hyunyoung Lee

2 Lee CSCE 314 TAMU 2 Higher-order Functions A function is called higher-order if it takes a function as an argument or returns a function as a result. twice :: (a a) a a twice f x = f (f x) twice is higher-order because it takes a function as its first argument. Note: Higher-order functions are very common in Haskell (and in functional programming). Writing higher-order functions is crucial practice for effective programming in Haskell, and for understanding others’ code.

3 Lee CSCE 314 TAMU 3 Why Are They Useful? Common programming idioms can be encoded as functions within the language itself. Domain specific languages can be defined as collections of higher-order functions. For example, higher-order functions for processing lists. Algebraic properties of higher-order functions can be used to reason about programs.

4 Lee CSCE 314 TAMU 4 The Map Function The higher-order library function called map applies a function to every element of a list. map :: (a b) [a] [b] For example: > map (+1) [1,3,5,7] [2,4,6,8] The map function can be defined in a particularly simple manner using a list comprehension: map f xs = [f x | x xs] map f [] = [] map f (x:xs) = f x : map f xs Alternatively, it can also be defined using recursion:

5 Lee CSCE 314 TAMU 5 The Filter Function The higher-order library function filter selects every element from a list that satisfies a predicate. filter :: (a Bool) [a] [a] For example: > filter even [1..10] [2,4,6,8,10] Alternatively, it can be defined using recursion: Filter can be defined using a list comprehension: filter p xs = [x | x xs, p x] filter p [] = [] filter p (x:xs) | p x = x : filter p xs | otherwise = filter p xs

6 Lee CSCE 314 TAMU 6 The foldr Function A number of functions on lists can be defined using the following simple pattern of recursion: f [] = v f (x:xs) = x f xs f maps the empty list to some value v, and any non-empty list to some function applied to its head and f of its tail.

7 Lee CSCE 314 TAMU 7 For example: sum [] = 0 sum (x:xs) = x + sum xs and [] = True and (x:xs) = x && and xs product [] = 1 product (x:xs) = x * product xs v = 0 = + v = 1 = * v = True = &&

8 Lee CSCE 314 TAMU 8 The higher-order library function foldr (fold right) encapsulates this simple pattern of recursion, with the function and the value v as arguments. For example: sum = foldr (+) 0 product = foldr (*) 1 or = foldr (||) False and = foldr (&&) True

9 Lee CSCE 314 TAMU 9 foldr itself can be defined using recursion: foldr :: (a b b) b [a] b foldr f v [] = v foldr f v (x:xs) = f x (foldr f v xs) However, it is best to think of foldr non-recursively, as simultaneously replacing each (:) in a list by a given function, and [] by a given value.

10 Lee CSCE 314 TAMU 10 sum [1,2,3] foldr (+) 0 [1,2,3] = foldr (+) 0 (1:(2:(3:[]))) = 1+(2+(3+0)) = 6 = For example: Replace each (:) by (+) and [] by 0.

11 Lee CSCE 314 TAMU 11 product [1,2,3] foldr (*) 1 [1,2,3] = foldr (*) 1 (1:(2:(3:[]))) = 1*(2*(3*1)) = 6 = For example: Replace each (:) by (*) and [] by 1.

12 Lee CSCE 314 TAMU 12 Other foldr Examples Even though foldr encapsulates a simple pattern of recursion, it can be used to define many more functions than might first be expected. Recall the length function: length :: [a] Int length [] = 0 length (_:xs) = 1 + length xs

13 Lee CSCE 314 TAMU 13 length [1,2,3] length (1:(2:(3:[]))) = 1+(1+(1+0)) = 3 = Hence, we have: length = foldr (\_ n -> 1+n) 0 Replace each (:) by _ n 1+n and [] by 0 For example:

14 Lee CSCE 314 TAMU 14 Now the reverse function: reverse [] = [] reverse (x:xs) = reverse xs ++ [x] reverse [1,2,3] reverse (1:(2:(3:[]))) = (([] ++ [3]) ++ [2]) ++ [1] = [3,2,1] = For example: Replace each (:) by x xs xs ++ [x] and [] by [] Hence, we have: reverse = foldr (\x xs -> xs ++ [x]) [] Here, the append function ( ++ ) has a particularly compact definition using foldr: (++ ys) = foldr (:) ys Replace each (:) by (:) and [] by ys.

15 Lee CSCE 314 TAMU 15 Why Is foldr Useful? Some recursive functions on lists, such as sum, are simpler to define using foldr. Properties of functions defined using foldr can be proved using algebraic properties of foldr. Advanced program optimizations can be simpler if foldr is used in place of explicit recursion.

16 Lee CSCE 314 TAMU 16 foldr and foldl foldr 1 : 2 : 3 : [] => (1 + (2 + (3 + 0))) foldl 1 : 2 : 3 : [] => (((0 + 1) + 2) + 3) foldr :: (a b b) b [a] b foldr f v [] = v foldr f v (x:xs) = f x (foldr f v xs) foldl :: (a b a) a [b] a foldl f v [] = v foldl f v (x:xs) = foldl f (f v x) xs

17 Lee CSCE 314 TAMU 17 Other Library Functions The library function (.) returns the composition of two functions as a single function. (.) :: (b -> c) -> (a -> b) -> (a -> c) f. g = \x -> f (g x) For example: odd :: Int Bool odd = not. even Exercise: Define filterOut p xs that retains elements that do not satisfy p. filterOut p xs = filter (not. p) xs > filterOut odd [1..10] [2,4,6,8,10]

18 Lee CSCE 314 TAMU 18 The library function all decides if every element of a list satisfies a given predicate. all :: (a Bool) [a] Bool all p xs = and [p x | x xs] For example: > all even [2,4,6,8,10] True

19 Lee CSCE 314 TAMU 19 Dually, the library function any decides if at least one element of a list satisfies a predicate. any :: (a Bool) [a] Bool any p xs = or [p x | x xs] For example: > any isSpace "abc def" True

20 Lee CSCE 314 TAMU 20 The library function takeWhile selects elements from a list while a predicate holds of all the elements. takeWhile :: (a Bool) [a] [a] takeWhile p [] = [] takeWhile p (x:xs) | p x = x : takeWhile p xs | otherwise = [] For example: > takeWhile isAlpha "abc def" "abc"

21 Lee CSCE 314 TAMU 21 Dually, the function dropWhile removes elements while a predicate holds of all the elements. dropWhile :: (a Bool) [a] [a] dropWhile p [] = [] dropWhile p (x:xs) | p x = dropWhile p xs | otherwise = x:xs For example: > dropWhile isSpace " abc" "abc"

22 Lee CSCE 314 TAMU 22 filter, map and foldr Typical use is to select certain elements, and then perform a mapping, for example, sumSquaresOfPos ls = foldr (+) 0 (map (^2) (filter (>= 0) ls)) > sumSquaresOfPos [-4,1,3,-8,10] 110 In pieces: keepPos = filter (>= 0) mapSquare = map (^2) sum = foldr (+) 0 sumSquaresOfPos ls = sum (mapSquare (keepPos ls)) sumSquaresOfPos = sum. mapSquare. keepPos Alternative definition:

23 Lee CSCE 314 TAMU 23 Exercises (3) Redefine map f and filter p using foldr. (2) Express the comprehension [f x | x xs, p x] using the functions map and filter. (1) What are higher-order functions that return functions as results better known as?

## Presentation on theme: "Haskell Basics CSCE 314 Spring 2016. CSCE 314 – Programming Studio Using GHC and GHCi Log in to unix.cse.tamu.edu (or some other server) From a shell."— Presentation transcript:

1 Haskell Basics CSCE 314 Spring 2016

2 CSCE 314 – Programming Studio Using GHC and GHCi Log in to unix.cse.tamu.edu (or some other server) From a shell window, the compiler is invoked as > ghc myfile.hs > ghci (or as > ghc --interactive ) For multi-file programs, use --make option GHCi operates on an eval-print-loop: > sqrt (3^2 + 4^2) 5.0 > User types in a Haskell expression The interpreter evaluates it and prints out the result Waits for the next expression

3 Spring 2016 CSCE 314 – Programming Studio Other Haskell Options Download Haskell compiler on your computer Haskell Platform link on course webpage Windows, Mac OS X, linux Will install GHC on your computer

4 Spring 2016 CSCE 314 – Programming Studio Editing Haskell Files Use any editor to create a Haskell file Use the.hs extension to designate that it’s a Haskell file Install IDE Leksah Efficient edit-compile-run cycle, e.g., using Emacs with haskell- mode ( https://github.com/serras/emacs-haskell-tutorial/blob/master/tutorial.md ) helps indenting, debugging, jumping to an error, etc.

5 Spring 2016 CSCE 314 – Programming Studio Using GHCi Useful basic GHCi commands: :? Help! Show all commands :load test Open file test.hs or test.lhs :reload Reload the previously loaded file :main a1 a2 Invoke main with command line args a1 a2 :! Execute a shell command :edit name Edit script name :edit Edit current script :type expr Show type of expr :quit Quit GHCi Commands can be abbreviated. E.g., :r is :reload At startup, the definitions of the “Standard Prelude” are loaded

6 Spring 2016 CSCE 314 – Programming Studio Basic statements Basic arithmetic and comparisons are supported + Addition - Subtraction * Multiplication / Division (for fractions/floats) ^ Power div Integer Division function == Equality /= Inequality >, <, etc. Other comparisons

7 Spring 2016 CSCE 314 – Programming Studio The Standard Prelude Haskell comes with a large number of standard library functions. In addition to the familiar numeric functions such as + and *, the library also provides many useful functions on lists. -- Lists are written with square brackets, and elements separated by commas [1,2,3,4,5]

8 Spring 2016 CSCE 314 – Programming Studio List Operations -- Select the first element of a list: > head [1,2,3,4,5] 1 -- Remove the first element from a list: > tail [1,2,3,4,5] [2,3,4,5] -- Select the nth element of a list: > [1,2,3,4,5] !! 2 3

9 Spring 2016 CSCE 314 – Programming Studio -- Select the first n elements of a list: > take 3 [1,2,3,4,5] [1,2,3] -- Remove the first n elements from a list: > drop 3 [1,2,3,4,5] [4,5] -- Append 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]

10 Spring 2016 CSCE 314 – Programming Studio -- Calculate the length of a list: > length [1,2,3,4,5] 5 -- Calculate the sum of a list of numbers: > sum [1,2,3,4,5] 15 -- Calculate the product of a list of numbers: > product [1,2,3,4,5] 120

11 Spring 2016 CSCE 314 – Programming Studio Functions The key part of Haskell programming! Functions are created in Haskell scripts (.hs files) Cannot be defined at the command prompt in an interactive window Scripts can get loaded in :l :r to reload Scripts can be command line argument when invoked ghci Windows Once loaded, the functions defined in the script are in scope (available to use)

12 Spring 2016 CSCE 314 – Programming Studio Functions (1) Function and parameter names must start with a lower case letter, e.g., myFun1, arg_x, personName, etc. (By convention, list arguments usually have an s suffix on their name, e.g., xs, ns, nss, etc.) Functions are defined as equations: square x = x * x add x y = x + y Once defined, apply the function to arguments: > square 7 > add 2 3 49 5 In C, these calls would be square(7); and add(2,3);

13 Spring 2016 CSCE 314 – Programming Studio Functions (2) Parentheses are often needed in Haskell too > add (square 2) (add 2 3) 9 Function application has the highest precedence (after parentheses) square 2 + 3 means (square 2) + 3 not square (2+3) Function call associates to the left and is by pattern matching (first one to match is used)

14 Spring 2016 CSCE 314 – Programming Studio Functions (3) Function application operator $ has the lowest precedence and is used to avoid parentheses. sum ([1..5] ++ [6..10]) -> sum $ [1..5] ++ [6..10] Combinations of most symbols are allowed as function x @#$%^&*-+@#$% y = "What on earth?” Another (more reasonable) example: x +/- y = (x-y, x+y) > 10 +/- 1 (9,11)

15 Spring 2016 CSCE 314 – Programming Studio Function Application In mathematics, function application is denoted using parentheses, and multiplication is often denoted using juxtaposition or space. f(a,b) + c d Apply the function f to a and b, and add the result to the product of c and d In Haskell, function application is denoted using space, and multiplication is denoted using *. f a b + c*d As above, but in Haskell syntax

16 Spring 2016 CSCE 314 – Programming Studio Examples Mathematics Haskell f(x) f(x,y) f(g(x)) f(x,g(y)) f(x)g(y) f x f x y f (g x) f x (g y) f x * g y

17 Spring 2016 CSCE 314 – Programming Studio Prefix vs Infix Many people are used to Infix notation: an operation comes between two arguments a op b Typical Haskell usage for functions is Prefix notation. That is, the operation comes first, then the arguments. op a b Any function with two arguments can be used as an infix operator by enclosing it in BACK quotes ` ` a `op` b Any infix operator can be used as a function (enclosed in parentheses) (*) a b

18 Spring 2016 CSCE 314 – Programming Studio Comments Ordinary comments: start with – Single line: ignore everything else on that line double x = x + x -- This is a function to double a number -- I am writing another comment Nested comments: {- -} Can be multiline, or nested one inside the other double x = x + x {- Here is a comment {- With another comment inside it -} -}

19 Spring 2016 CSCE 314 – Programming Studio Evaluating Functions (1) Think of evaluating functions as substitution and reduction add x y = x + y; square x = x * x add (square 2) (add 2 3) −− apply square add (2 * 2) (add 2 3) −− apply ∗ add 4 (add 2 3) −− apply inner add add 4 (2 + 3) −− apply + add 4 5 −− apply add 4+5 −− apply + 9

20 Spring 2016 CSCE 314 – Programming Studio Evaluating Functions (2) There are many possible orders to evaluate a function head (1:(reverse [2,3,4,5])) head (1:(reverse [2,3,4,5])) −− apply reverse −− apply head −−... many steps omitted here 1 head (1 : [5,4,3,2]) −− apply head 1 In a pure functional language, evaluation order does not affect the value of the computation It can, however, affect the amount of computation and whether the computation terminates or not (or fails with a run-time error) Haskell evaluates a function’s argument lazily “Call-by-need” - only apply a function if its value is needed, and “memoize” what’s already been evaluated

21 Spring 2016 CSCE 314 – Programming Studio My First Script double x = x + x quadruple x = double (double x) When developing a Haskell script, it is useful to keep two windows open, one running an editor for the script, and the other running GHCi: Start an editor, type in the following two function definitions, and save the script as test.hs: % ghci test.hs In another window start up GHCi with the new script: > quadruple 10 40 > take (double 2) [1,2,3,4,5,6] [1,2,3,4] Now both the standard library and the file test.hs are loaded, and functions from both can be used:

22 Spring 2016 CSCE 314 – Programming Studio factorial n = product [1..n] average ns = sum ns `div` length ns Leaving GHCi open, return to the editor, add the following definitions, and resave: div is enclosed in back quotes, not forward Lets us write using infix notation Note: > :r Reading file "test.hs" > factorial 10 3628800 > average [1,2,3,4,5] 3 GHCi does not automatically detect that the script has been changed, so a reload command must be executed before the new definitions can be used:

23 Spring 2016 CSCE 314 – Programming Studio The Layout Rule Layout of a script determines the structure of definitions Commonly use layouts instead of braces and semicolons (which are still allowed and can be mixed with layout) Each definition must begin in precisely the same column: a = 10 b = 20 c = 30 a = 10 b = 20 c = 30 a = 10 b = 20 c = 30 means a = b + c where b = 1 c = 2 d = a * 2 a = b + c where {b = 1; c = 2} d = a * 2 implicit grouping by layout explicit grouping by braces and semicolons

24 Spring 2016 CSCE 314 – Programming Studio Exercises N = a ’div’ length xs where a = 10 xs = [1,2,3,4,5] (1) What are the syntax errors in the program below? n = a `div` length xs where a = 10 xs = [1,2,3,4,5]

25 Spring 2016 CSCE 314 – Programming Studio Show how the library function last that selects the last element of a list can be defined using the functions introduced in this lecture. (2) Similarly, show how the library function init that removes all but the last element from a list can be defined in two different ways. (4) Can you think of another possible definition? (3) last xs = head ( reverse xs ) last xs = xs !! (length xs – 1) init xs = take ( length xs – 1 ) xs init xs = reverse ( tail ( reverse xs ))

## One thought on “Csce 314 Assignment 8 Tutoria”