Chapter 6: Higher Order Functions

Learn You a Haskell for Great Good!

Curried functions

  • Every function in Haskell officially only takes one parameter
  • If we call a function with too few parameters, we get back a partially applied function (the return ->)
multThree :: (Num a) => a -> a -> a -> a
multThree x y z = x * y * z
  • If we do multThree 3 4 5, which is same as ((multThree 3) 4) 5, the 3 is applied to multThree and the function type is the same as
multThree :: (Num a) => a -> (a -> (a -> a))
  • and will return another function that has type as follow
multThree :: (Num a) => a -> (a -> a)
  • applied 4 to this function and it is return a function with the following type
multThree :: (Num a) => a -> a
  • and finally apply 5 to the last function and return a. By calling the function  with too few parameter, we create new function on the fly.
  • The following two functions are the same because compare has type (Ord a) => a -> (a -> Ordering) and we can use that function for the value we need to compare with.
compareWithHundred :: (Num a, Ord a) => a -> Ordering
compareWithHundred x = compare 100 x

compareWithHundred = compare 100
  • Similarly, Infix function works the same way. The function will take one parameter and then applied to the missing operand. Thus, calling divideByTen 200 is equivalent to 200 / 10 or (/10) 200.
divideByTen :: (Floating a) => a -> a
divideByTen = (/10)

Some higher-orderism is in order

  • Function can take a function as parameter
applyTwice :: (a -> a) -> a -> a
applyTwice f x = f (f x)
  • applyTwice take two parameters, a function (a->a) and a of the same type and return a. This function apply whatever the function is twice and then apply it to the value.
  • zipWith’ takes two lists and a function and apply the function to each corresponding element of the lists and produce a result list.
zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' _ [] _ = []
zipWith' _ _ [] = []
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys
  • We can use this function in many ways as long as the type is consistent with the declaration. The last one zipWith list of list.
ghci> zipWith' (+) [4,2,5,6] [2,6,2,3]  
[6,8,7,9ghci> zipWith' max [6,3,2,1] [7,3,1,5]  
[7,3,2,5ghci> zipWith' (++) ["foo ""bar ""baz "] ["fighters""hoppers""aldrin"]  
["foo fighters","bar hoppers","baz aldrin"ghci> zipWith' (*) (replicate 5 2) [1..]  
[2,4,6,8,10ghci> zipWith' (zipWith' (*)) [[1,2,3],[3,5,6],[2,3,4]] [[3,2,2],[3,4,5],[5,4,3]]  
[[3,4,6],[9,20,30],[10,12,12]]

Maps and filters

  • map take a function and a list and applies that function to every element in the list
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs

ghci> map (+3) [1,2,3,4,5]
[4,5,6,7,8]
  • You can do this with list comprehension
[x + 3 | x <- [1,2,3,4,5]]
  • filter is a function that takes a predicate (which is a function that return true or false) and a list and returns the list of elements that satisfy the predicate.
filter :: (a -> Bool) -> [a] -> [a]
filter _ [] = []
filter p (x:xs)
    | p x       = x : filter p xs
    | otherwise = filter p xs

ghci > filter (>3) [1,2,3,4,5]
[4,5]
  • Again, you can do this with list comprehension
[ x | x <- [1,2,3,4,5], x > 3]
  • find the largest number under 100000 that’s divisible by 3829
largestDivisible :: (Integral a) => a
largestDivisible = head (filter p [100000,99999..])
    where p x = x `mod` 3829 == 0
  • more general largestDivisible’ with the max limit and the divisor.
largestDivisible' :: (Integral a) => a -> a -> a
largestDivisible' x y = head (filter p [x,(x-1)..])
    where p z = z `mod` y == 0
  • takeWhile function takes a predicate and a list and then goes from the beginning of the list and returns its elements while the predicate holds true.
  • take the first word of the string “elephants know how to party”. Not equal is /=.
ghci> takeWhile (/=' ') "elephants know how to party"
"elephants"
  • find the sum of all odd squares that are smaller than 10000. We  use both filter & map or list comprehension to achieve the same result. However, both needed takeWhile as a stopping condition.
ghci> sum (takeWhile (<10000) (filter odd (map (^2) [1..])))
166650 

ghci> sum (takeWhile (<10000) [n^2 | n <- [1..], odd (n^2)])
166650
  •  you can use pure list comprehension to do the same thing without takeWhile but must upper bound the list
ghci> sum ([n^2 | n <- [1..10000], odd (n^2), (n^2) < 10000])
166650
  •  the following create a list of function and use it by selecting an element from it. The first line create a list of [(0*), (1*), (2*)..] or (Num a) => [a -> a].
ghci> let listOfFunc = map (*) [0..]
ghci> (listofFunc !! 4) 5
20

Lambdas

  • Lambdas are anonymous functions that are used because we need some functions only once.
chain :: (Integral a) => a -> [a]
chain 1 = [1]
chain n
    | even n = n:chain (n `div` 2)
    | odd n  = n:chain (n * 3 + 1)

numLongChains :: Int
numLongChains = length (filter isLong (map chain [1..100]))
    where isLong xs = length xs > 15

numLongChains :: Int
numLongChains = length (filter (\xs -> length xs > 15) (map chain [1..100]))
  • Lambdas is an expression (e.g \xs -> length xs > 15) return a function.
  • Lambdas can take multiple parameters (e.g. \a b)
  • Lambdas can use pattern matching but can’t define multiple patterns for the same parameter. Any fall through will result in error.

Only folds and horses

  • fold takes a binary function, a starting value and a list to fold up. The type signature
foldl :: (a -> b -> a) -> a -> [b] -> a
  • foldl function (left fold) fold from the left side. The following are equivalent function to sum a list
sum' :: (Num a) => [a] -> a
sum' xs = foldl (\acc x -> acc + x) 0 xs

sum' :: (Num a) => [a] -> a
sum' = foldl (+) 0
  • any function with signature foo a = bar b a can be rewritten to foo = bar b.
elem' :: (Eq a) => a -> [a] -> Bool
elem' y ys = foldl (\acc x -> if x == y then True else acc) False ys
  • foldr function folds from the right side. use accumulator signature (\x acc -> …).
  • right fold works on infinite list and left don’t.
  • foldl1 and foldr1 is similar to foldl and foldr except they take the first or last (respectively) value as starting value. Therefore, the same sum function can implement as follow but will have runtime error on empty list
sum' = foldl1 (+)
  • scanl and scanr are like foldl and foldr but create a list of all the intermediate accumulator states. scanl1 and scanr1 are scanl and scanr without using starting value.

Function application with $

  • function application ($) is right associative. Lowest precedence. Consider the following two lines are equivalent. $ replaced parentheses.
sum (map sqrt [1..130])
sum $ map sqrt [1..130]
  • map function application over a list of functions. The following maps 3 to all the function in the list
ghci> map ($ 3) [(4+), (10*), (^2), sqrt]
[7.0,30.0,9.0,1.7320508075688772]

Function composition

  • definition: (f \circ g) (x) = f(g(x))
  • function composition is represented by the period “.” and is right associative. therefore, f(g(h x)) is equivalent to (f.g.h) x. Its implementation is as follow:
(.) :: (b -> c) -> (a -> b) -> a -> c
f . g = \x -> f (g x)
  • For functions with multiple parameters, we must first partially apply them so that each function only take one parameter before being use in function composition.

Other commands

  • To change directory
    • :cd
  • To use shell commands
    • :! (e.g. :!ls to list file)
Advertisements