1=Haskell =1=High-Order Functions ` `%%%`#`&12_`__~~~ alse

Download 1=Haskell =1=High-Order Functions ` `%%%`#`&12_`__~~~ alse

Post on 14-Feb-2017

221 views

Category:

Documents

5 download

TRANSCRIPT

HaskellHigh-Order Functionshttp://igm.univ-mlv.fr/~vialette/?section=teachingStephane VialetteLIGM, Universite Paris-Est Marne-la-ValleeDecember 29, 2014http://igm.univ-mlv.fr/~vialette/?section=teachingCurried functionsEvery function in Haskell officially takes only one parameter.A curried function is a function that, instead of taking severalparameters, always takes exactly one parameter.When it is called with that parameter, it returns a function thattakes the next parameter, and so on.Curried functions*Main> 1 + 23*Main> :t +:1:1: parse error on input '+'*Main> (+) 1 23*Main> :t (+)(+) :: Num a => a -> a -> a*Main>Curried functions*Main> let add = (+)*Main> :t addadd :: Num a => a -> a -> a*Main> add 1 23*Main> (add 1) 23*Main> let add1 = add 1*Main> :t add 1add 1 :: Num a => a -> a*Main> add1 23*Main>Curried functionsWhenever we have a type signature that features the arrow ->,that means it is a function that takes whatever is on the left sideof the arrow and returns a value whose type is indicated on theright side of the arrow.Curried functionsWhen we have something like a -> a -> a (reada -> (a -> a)), we are dealing with a function that takes avalue of type a, and it returns a function that also takes a value oftype a and returns a value of type a.Curried functions*Main> let multThree x y z = x * y * z*Main> :t multThreemultThree :: Num a => a -> a -> a -> a*Main> let multTwoWithNine = multThree 9*Main> :t multTwoWithNinemultTwoWithNine :: Num a => a -> a -> a*Main> multTwoWithNine 2 354*Main> let multWithNineAndFive = multTwoWithNine 5*Main> :t multWithNineAndFivemultWithNineAndFive :: Num a => a -> a*Main> multWithNineAndFive 290*Main> multThree 2 5 990*Main>Curried functions*Main> :t comparecompare :: Ord a => a -> a -> Ordering*Main> :t (compare 100)(compare 100) :: (Ord a, Num a) => a -> Ordering*Main> let compareWithHundred x = compare 100 x*Main> compareWithHundred 99GT*Main> :t compareWithHundredcompareWithHundred :: (Ord a, Num a) => a -> Ordering*Main> let compareWithHundred' = compare 100*Main> :t compareWithHundred'compareWithHundred' :: (Ord a, Num a) => a -> Ordering*Main> compareWithHundred' 99GT*Main>Curried functions*Main> let divideByTen = (/10)*Main> :t divideByTendivideByTen :: Fractional a => a -> a*Main> divideByTen 20020.0*Main> (/ 10) 20020.0*Main> let isUpperAlphanum = (`elem` ['A'..'Z'])*Main> :t isUpperAlphanumisUpperAlphanum :: Char -> Bool*Main> isUpperAlphanum 'k'False*Main> isUpperAlphanum 'K'True*Main>Some Higher-Orderism Is in OrderIn Haskell, function can take other functions as parameter, and aswe have seen, they can also return functions as return value.applyTwice :: (a -> a) -> a -> aapplyTwice f x = f (f x)-> is naturally right-associative. Therefore, here parentheses aremandatory as a -> a -> a -> a is interpreted by Haskell asa -> (a -> (a -> a)).Some Higher-Orderism Is in Order*Main> applyTwice (+3) 1016*Main> (+3) ((+3) 10)16*Main> applyTwice (++ " HAHA") "HEY""HEY HAHA HAHA"*Main> applyTwice ("HAHA " ++) "HEY""HAHA HAHA HEY"*Main> let multThree x y z = x * y * zin applyTwice (multThree 2 2) 9144*Main> applyTwice (1:) [2][1,1,2]*Main>Some Higher-Orderism Is in OrderImplementing zipWithzipWith takes a functionand two lists as parameters, and thenjoins the two lists by applying the function between correspondingelements (its in the standard library).zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]zipWith' _ [] _ = []zipWith' _ _ [] = []zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ysSome Higher-Orderism Is in OrderImplementing zipWith*Main> :t zipWith'zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]*Main> zipWith' (+) [1,2,3] [11,12,13][12,14,16]*Main> zipWith' max [1,12,3] [11,2,13][11,12,13]*Main> zipWith' (++) ["foo","bar"] ["fighther","hoppers"]["foofighther","barhoppers"]*Main> zipWith' (*) (replicate 5 2) [1..][2,4,6,8,10]*Main> zipWith' (zipWith' (*)) [[1,2],[3,4]] [[5,6],[7,8]][[5,12],[21,32]]*Main>Some Higher-Orderism Is in OrderImplementing flipflip takes a function and return a function that is like our originalfunction, but with the first two arguments flipped (its in thestandard library).flip' :: (a -> b -> c) -> b -> a -> cflip' f = g where g x y = f y xRecall that the arrow -> is right-associative, and hence(a -> b -> c) -> b -> a -> c is the same as(a -> b -> c) -> (b -> a -> c).flip' :: (a -> b -> c) -> b -> a -> cflip' f x y = f y xSome Higher-Orderism Is in OrderImplementing flip*Main> zip [1..5] "hello"[(1,'h'),(2,'e'),(3,'l'),(4,'l'),(5,'o')]*Main> flip' zip [1..5] "hello"[('h',1),('e',2),('l',3),('l',4),('o',5)]*Main> zipWith div [2,2..] [10,8,6,4,2][0,0,0,0,1]*Main> zipWith (flip' div) [2,2..] [10,8,6,4,2][5,4,3,2,1]*Main>The functionnal Programmers ToolboxThe functionnal Proframmers ToolboxThe map functionThe map function takes a function and a list, and applies thatfunction to every element in the list, producing a new list.map :: (a -> b) -> [a] -> [b]map _ [] = []map f (x:xs) = f x : map f xsmap is a versatile higher-order function that can be used in manydifferent waysThe functionnal Proframmers ToolboxThe map function*Main> map (+1) [1,2,3,4,5][2,3,4,5,6]*Main> map (++ "!") ["BIFF","BANG","POW"]["BIFF!","BANG!","POW!"]*Main> map (replicate 3) [1,2,3][[1,1,1],[2,2,2],[3,3,3]]*Main> map (map (^2)) [[1,2],[3,4]][[1,4],[9,16]]*Main> map fst [(1,2),(3,4),(5,6)][1,3,5]*Main> map snd [(1,2),(3,4),(5,6)][2,4,6]*Main>The functionnal Proframmers ToolboxThe filter functionThe filter function takes a predicate and a list, and returns thelist of elements that satify the predicatefilter :: (a -> Bool) -> [a] -> [a]filter _ [] = []filer p (x:xs)| p x = x : filter p xs| otherwise = filter p xsIf p x evaluates to True, the element is included in the new list. Ifit doesnt evaluate to True, it isnt included in the new list.The functionnal Proframmers ToolboxThe filter function*Main> filter (> 3) [1,2,3,4,5,1,2,3,4,5][4,5,4,5]*Main> filter (== 3) [1,2,3,4,5,1,2,3,4,5][3,3]*Main> filter (< 3) [1,2,3,4,5,1,2,3,4,5][1,2,1,2]*Main> filter even [1,2,3,4,5,1,2,3,4,5][2,4,2,4]*Main> filter (`elem` ['a'..'z']) "I lOvE hAsKeLl""lvhsel"*Main> filter (`elem` ['A'..'Z']) "I lOvE hAsKeLl""IOEAKL"*Main>The functionnal Proframmers ToolboxThe filter functionThe filter equivalent of applying several predicates in a listcomprehension is either filtering something several times or joiningpredicates with the logical && function.*Main> filter (< 15) (filter even [1..20])[2,4,6,8,10,12,14]*Main> let p x = x < 15 && even x in filter p [1..20][2,4,6,8,10,12,14]*Main> filter (\x -> x < 15 && even x) [1..20][2,4,6,8,10,12,14]*Main> [x | x The functionnal Proframmers ToolboxThe filter functionquicksort :: (Ord a) => [a] -> [a]quicksort [] = []quicksort (x:xs) =let smallerOrEqual = filter ( x) xsin quicksort smallerOrEqual ++ [x] ++ quicksort largerThe functionnal Proframmers ToolboxMore examples of map and filterLets find the largest number under 100 000 that is divisible by3 829.largestDivisible :: IntegerlargestDivisible = head (filter p [100000,99999..])where p x = x `mod`3829 == 0The functionnal Proframmers ToolboxMore examples of map and filterLets find the sum of all odd squares that are smaller than 10 000.*Main> sum (takeWhile (< 10000) (filter odd (map (^2) [1..])))166650*Main> sum (takeWhile (< 10000) [x | x The functionnal Proframmers ToolboxMore examples of map and filterA Collatz sequence is defined as follows: Start with any natural number. If the number is 1, stop. If the number is even, divide it by 2. If the number id odd, multiply it by 3 and add 1. Repeat the algorithm with the resulting number.Mathematicians theorize that for all starting number, the chain willfinish at the number 1.The functionnal Proframmers ToolboxMore examples of map and filterThe functionnal Proframmers ToolboxMore examples of map and filterThe functionnal Proframmers ToolboxMore examples of map and filtercollatz :: Integer -> [Integer]collatz 1 = [1]collatz n| even n = n : collatz (n `div` 2)| odd n = n : collatz (n*3 + 1)*Main> collatz 10[10,5,16,8,4,2,1]*Main> collatz 20[20,10,5,16,8,4,2,1]*Main> length $ collatz 10026*Main> length $ collatz 1000112*Main>The functionnal Proframmers ToolboxMapping functions with Multiple Parameters*Main> let listOfFuns = map (*) [0..]*Main> :t listOfFunslistOfFuns :: (Num a, Enum a) => [a -> a]*Main> (listOfFuns !! 0) 50*Main> (listOfFuns !! 1) 55*Main> (listOfFuns !! 2) 510*Main> (listOfFuns !! 3) 515*Main> (listOfFuns !! 4) 520*Main>LambdasLambdasLambdas are anonymous fucntions that we use when we need afunction only once.Normally, we make a lambda with the sole purpose of passing it toa higer-order function.To declare a lambda, we write \ (because it kind of looks like theGreek letterlambda () if you squint hard enough), and then wewrite the functions parameters, separated by spaces.After that comes a ->, and then the function body.If a lambda match fails in a lambda, a runtime error occurs, so becareful!Lambdas*Main> map (+3) [1..5][4,5,6,7,8]*Main> map (\x -> x + 3) [1..5][4,5,6,7,8]*Main> zipWith (+) [1..5] [101..105][102,104,106,108,110]*Main> zipWith (\x y -> x + y) [1..5] [101..105][102,104,106,108,110]*Main> map (\(x,y) -> x + y) [(1,2),(3,4),(5,6)][3,7,11]*Main>LambdasThe following functions are equivalent:addThree :: Int -> Int -> Int -> IntaddThree x y z = x + y + zaddThree' :: Int -> Int -> Int -> IntaddThree' = \x -> \y -> \z -> x + y + zIn the second example, the lambdas are not surroounded withparentheses. When you write a lambda without parentheses, itassumes that everything to the right of the arrow -> belongs to it.LambdasThe following functions are equivalent:flip' :: (a -> b -> c) -> b -> a -> cflip' f x y = f y xflip'' :: (a -> b -> c) -> b -> a -> cflip'' f = \x y -> f y xIn the second example, our new notation makes it obvious that thiswill often be used for producing a new function.I fold you soI fold you so Folds can be used to implement any function where youtraverse a list once, element by element, and then returnsomething based on that. A fold takes a binary function (one that takes two parameters,such as + or div), a starting value (often called theaccumulator), and a list to fold up. Lists can folded up from the left or from the right. The fold function calls the given binary function, using theaccumulator and the first (or last) element of the list asparameters. The resulting value is the new accumulator. The accumulator value (and hence the result) of a fold can beof any type.Left fold with foldlI fold you soLeft fold with foldlsum' :: (Num a) => [a] -> asum' xs = foldl (\acc x -> acc + x) 0 xs*Main> sum' []0*Main> sum' [3,5,2,1]11*Main>I fold you soLeft fold with foldlI fold you soLeft fold with foldlThe lambda function \acc x -> acc + x is the same as (+)sum'' :: (Num a) => [a] -> asum'' = foldl (+) 0*Main> sum'' []0*Main> sum'' [3,5,2,1]11*Main>A quick parenthesis-reduction An eta conversion (also written -conversion) is adding ordropping of abstraction over a function. For example, the following two values are equivalent under-conversion: \x -> abs x and abs. Converting from the first to the second would constitute an-reduction, and moving from the second to the first wouldbe an -abstraction. The term -conversion can refer to the process in eitherdirection. Extensive use of -reduction can lead to Pointfreeprogramming.A quick parenthesis-reductionThereforesum'' :: (Num a) => [a] -> asum'' xs = foldl (+) 0 xsis usually rewritten as:sum'' :: (Num a) => [a] -> asum'' = foldl (+) 0I fold you soLeft fold with foldlelem' :: (Eq a) => a -> [a] -> Boolelem' y ys = foldl (\acc x -> if x == y then True else acc) False ysPrelude> elem' 'a' ['a'..'l']TruePrelude> elem' 'm' ['a'..'l']FalsePrelude> elem' (3, 9) [(i, i^2) | i elem' (4, 17) [(i, i^2) | i I fold you soRight fold with foldr The right fold function foldr is similar to the left fold, exceptthat the accumulator eats up the values from the right. Also, the order of the parameters in the right folds binaryfunction is reversed: The current list value is the rightparameter and the accumulator is the second.Right fold with foldrI fold you soRight fold with foldrmap' :: (a -> b) -> [a] -> [b]map' f xs = foldr (\x acc -> f x : acc) [] xs*Main> map' (+ 10) [][]*Main> map' (+ 10) [1..5][11,12,13,14,15]*Main>I fold you soRight fold with foldrmap' :: (a -> b) -> [a] -> [b]map' f = foldr (\x acc -> f x : acc) []map'' :: (a -> b) -> [a] -> [b]map'' f = foldl (\acc x -> acc ++ [f x]) []Notice that the ++ function is much slower than :, so we usuallyuse right fold when we are building up new lists from lists.I fold you soRight fold with foldrThe elem function checks chether a value is part of a list.elem' :: (Eq a) => a -> [a] -> Boolelem' x = foldr (\y acc -> if x==y then True else acc) False*Main> :t elem'elem' :: Eq a => a -> [a] -> Bool*Main> 5 `elem` [10..20]False*Main> 15 `elem` [10..20]True*Main>I fold you soThe foldl1 and foldr1 functions The foldl1 and foldr1 functions work much like foldl andfoldr, except that you dont need to provide them with anexplicit starting accumulator. The foldl1 and foldr1 functions assume the first (or last)element of the list to be the starting accumulator, and thenstart the fold with the next element next to it.I fold you soThe foldl1 and foldr1 functions*Main> :t foldl1foldl1 :: (a -> a -> a) -> [a] -> a*Main> :t foldr1foldr1 :: (a -> a -> a) -> [a] -> a*Main>I fold you soThe foldl1 and foldr1 functionsminimum' :: (Ord a) => [a] -> aminimum' = foldl1 minmaximum' :: (Ord a) => [a] -> amaximum' = foldl1 max*Main> :t minimum'minimum' :: Ord a => [a] -> a*Main> minimum' []*** Exception: Prelude.foldl1: empty list*Main> minimum' [1]1*Main> minimum' $ [10..20] ++ [1..10]1*Main>I fold you soSome fold examplesreverse' :: [a] -> [a]reverse' = foldl (\acc x -> x : acc) []reverse'' :: [a] -> [a]reverse'' = foldl (flip (:)) []Main> reverse' [][]*Main> reverse' [1..5][5,4,3,2,1]*Main> reverse'' [][]*Main> reverse'' [1..5][5,4,3,2,1]*Main>I fold you soSome fold examplesfilter' :: (a -> Bool) -> [a] -> [a]filter' p = foldr (\x acc -> if p x then x : acc else acc) []last' :: [a] -> alast' = foldl1 (\_ x -> x)length' :: Num b => [a] -> blength' = foldr (\_ -> (+1)) 0I fold you soFolding infinite listsand' :: [Bool] -> Booland' = foldr (&&) True*Main> and' (repeat False)False*Main>I fold you soScans The scanl and scanr functions are like foldl and foldr,except they report all the intermediate accumulator states inthe form of a list. The scanl1 and scanr1 functions are analogous to foldl1and foldr1.I fold you soScans*Main> scanl (+) 0 [1,2,3,4][0,1,3,6,10]*Main> scanr (+) 0 [1,2,3,4][10,9,7,4,0]*Main> scanl1 (\acc x -> if x > acc then x else acc) [1..5][1,2,3,4,5]*Main> scanl1 max [1..5][1,2,3,4,5]*Main> scanl (flip (:)) [] [3,2,1][[],[3],[2,3],[1,2,3]]*Main>I fold you soFunction application with $The function application operator $ is defined as follows:($) :: (a -> b) -> a -> bf $ x = f xI fold you soFunction application with $What is this useless function? It is just function application! Well,that is almost true, but not quite.Whereas normal function application (putting a space between twothings) has a really high precedence, the $ function has the lowestprecedence.Function application with a space is left-associative (so f a b c isthe same as (((f a) b) c)), while function application with $ isright-associative.I fold you soFunction application with $*Main> sum (filter (> 10) (map (*2) [2..10]))80*Main> sum $ filter (> 10) (map (*2) [2..10])80*Main> sum $ filter (> 10) $ map (*2) [2..10]80*Main>I fold you soFunction application with $Apart of getting rid of parentheses, $ let us treat functionapplication like just another function.*Main> :t (4+)(4+) :: Num a => a -> a*Main> :t (^2)(^2) :: Num a => a -> a*Main> :t sqrtsqrt :: Floating a => a -> a*Main> :t [(4+),(^2),sqrt][(4+),(^2),sqrt] :: Floating a => [a -> a]*Main> map ($ 3) [(4+),(^2),sqrt][7.0,9.0,1.7320508075688772]*Main>Function compositionIn mathematics, function composition is defined as follows:(f g)(x) = f (g(x))Function compositionIn Haskell, function composition is pretty much the same thing.We do function composition with the . function:(.) :: (b -> c) -> (a -> b) -> (a -> c)f . g = \x -> f (g x)Function composition*Main> :t negatenegate :: Num a => a -> a*Main> :t absabs :: Num a => a -> a*Main> map (\x -> negate(abs x)) [1,-2,3,-4,5,-6][-1,-2,-3,-4,-5,-6]*Main> map (negate . abs) [1,-2,3,-4,5,-6][-1,-2,-3,-4,-5,-6]*Main>Function composition*Main> map (\xs -> negate (sum (tail xs))) [[1..5],[3..6]][-14,-15]*Main> map (negate . sum .tail) [[1..5],[3..6]][-14,-15]*Main>negate . sum .tail is a function that takes a list, applies thetail function to it, then applies the sum function to the result,and finally applies negate to the previous result.Function compositionFunction Composition with Multiple ParametersBut what about functions that take several parameters?Well, if we want to use them in function composition, we usuallymust partially apply them so that each function takes just oneparameter.*Main> sum (replicate 5 (max 6.7 8.9))44.5*Main> (sum .replicate 5) (max 6.7 8.9)44.5*Main> sum .replicate 5 $ max 6.7 8.944.5*Main> replicate 2 (product (map (*3) (zipWith max [1,2] [4,5])))[180,180]*Main> replicate 2 . product . map (*3) $ zipWith max [1,2] [4,5][180,180]*Main>Function compositionPoint-Free StyleAnother common use of function compisition is defining function inthe point-free style.f :: (RealFrac a, Integral b, Floating a) => a -> bf x = ceiling (negate (tan (cos (max 50 x))))f' :: (RealFrac a, Integral b, Floating a) => a -> bf' = ceiling . negate . tan . cos . max 50Function compositionPoint-Free StyleoddSquareSum :: IntegeroddSquareSum = sum (takeWhile (