Functional Programming PDF

Functional Programming Radu Răzvan Slăvescu Technical University of Cluj-Napoca Department of Computer Science Outline Anonymous functions: Lambda expressions List comprehensions Generators Comprehensions=Generators+Guards Some basic Higher Order Functions and...

Functional Programming Radu Răzvan Slăvescu Technical University of Cluj-Napoca Department of Computer Science Outline Anonymous functions: Lambda expressions List comprehensions Generators Comprehensions=Generators+Guards Some basic Higher Order Functions and Combinators Combinators Anonymous functions No name Name Data 1 a=1 Functions ? inc x = x+1 Example (Lambda expressions) Expression λx.x + x is called ”lambda expression” and denotes a nameless function mapping a number into its double. It consists of the symbol λ, its parameter(s) (here, just x), a dot and the body (computations to be performed; here, x + x). Example (Haskell lambdas: \ for λ, -> for the dot) Main> (\ x -> x + x) 3 6 When can we benefit from lambda expresions? Example (Avoid ”wasting” function names) squares n = map f [n, n+1, n+2] where f x = x*x could be defined in a simpler manner: squares n = map (\ x -> x*x) [n, n+1, n+2] When can we benefit from lambda expresions? Example (Functions sent as arguments) isord [] _ = True isord [x] _ = True isord (x:y:ys) ordrel = (ordrel x y) && isord (y:ys) ordrel Main> isord ["Ro","Pl","Me","Dk"] (\ x y -> x>y) True Main> isord ["Dk","Pl","Ro","Me"] (\ x y -> x b -> a const1 n _ = n const2 :: a -> b -> a const2 n = \ _ -> n Remark const2 is more natural: the call const2 n creates and returns a function \ _ -> n which does the following things: (1) waits for an argument; (2) consumes it and (3) returns n. When can we benefit from lambda expresions? Example (Formal meaning of currying-based functions) subtract x y = x - y means subtract = \ x -> (\ y -> x - y) Remark Now it should be clear that subtract 1 waits for an argument and subtracts it from 1. Ranges A range is used for enumerating list elements. Example Main> [1..6] [1,2,3,4,5,6] Example Main> [6..1] [] Ranges Example Main> [2,4..10] [2,4,6,8,10] Example Main> [6,5..1] [6,5,4,3,2,1] Remark These generators build an arithmetic progression from one initial limit up to a final limit and with a given increment. Ranges Example (A Bottomless Coin Sack) Main> take 5 [1..] [1,2,3,4,5] Example (Boolean values) Main> take 3 [False.. ] [False,True] Main> take 3 [False, False.. ] [False,False,False] List comprehensions Definition List comprehension = list generators + guards (filtering tests) Example Main> [ x | x [[t]] pr [] = [[]] pr xs = [ a:p | a b) -> [a] -> [b] mapGen f xs = [ f x | x filter odd [1..5] [1,3,5] Example (Defining filter using list comprehenions) filterGen :: (a -> Bool) -> [a] -> [a] filterGen p xs = [ x | x b -> b) -> b -> [a] -> b incorporates this pattern, with the ⊕ operation and the v value as arguments/parameters, and adds it to the language. Example (New definitions for mysum and myand) mynewsum = foldr (+) 0 mynewand = foldr (&&) True Combinators Problem Write a curried function which decrements its argument by 1. Example (A wrong approach) ((-) 1) Main> ((-) 1) 9 -8 Explanation Arguments are taken from left to right. What to do? The C combinator Example (Solution: C combinator, aka flip in Haskell) combC f x y = f y x Main> combC (-) 1 9 8 Explanation combC swaps the (first two) arguments of f Definition (Combinator) Combinator = a function with no free variables. Though we’ll use this name only for a couple of such functions. The K combinator Explanation The K combinator creates a constant function. Example (Combinator K) combK n x = n Main> combK 3 "anything" 3 Combinators and the Point-Free style Grade conversion Let us consider two countries, C1 and C2, with grade scales [mi1, ma1] and [mi2, ma2] respectively. (e.g., [0..4] for US GPA and [1..20] France). In country C2 my average is m. What is its corresponding value in country C1? Example (Scale conversion: to, from, mark) scaleMark mi1 ma1 mi2 ma2 m = mi1 + (m-mi2) / (ma2-mi2) * (ma1-mi1) Combinators and the Point-Free style Example (Scale conversion: to, from, mark) scaleMark mi1 ma1 mi2 ma2 m = mi1 + (m-mi2) / (ma2-mi2) * (ma1-mi1) toGPA = scaleMark 0.0 4.0 mix5 f p1 p2 p3 p4 p5 = f p3 p4 p1 p2 p5 franceToAnywhere = mix5 scaleMark 1 20 Remark Functions toGPA and franceToAnywhere are written in point-free style. Their arguments are ”hidden”. Summary I lambda expressions are nameless functions I list comprehensions (generators + guards) allow easy list manipulation I map, filter and foldr focus on lists instead of individual elements I lambda expressions, combinators, and higher-order functions help us writing code in a compact manner