Higher order Functions

1 Parentheses!? atHome

Give examples for functions with the following types:

(Float −> Float) −> Float
Float −> (Float −> Float)
(Float −> Float) −> (Float −> Float)
-- For example (all these expressions have more general polymorphic types, but, in particular, type check at the requested types)
\f -> f 2.0 :: (Float −> Float) −> Float 
(*) :: Float −> (Float −> Float)
(.) (+1) :: (Float −> Float) −> (Float −> Float)

Give an example program p with the following type and explain how the function arrow -> associates:

p :: Int -> Bool -> Int
-- For example
p i b = if b then i else -i
-- Indeed, the function arrow -> always associates to the right, so this type should be read as 
-- the type Int -> (Bool -> Int) of curried multiple argument functions, rather than the type (Int -> Bool) -> Int of higher order functions

Give examples of programs foo, bar and baz, such that foo bar baz type checks and please explain how function application associates.

-- For example,
foo :: Int -> Int -> Int
foo = (+)
bar :: Int 
bar = 1
baz :: Int
baz = 2
-- Then foo bar baz is well-typed at type Int 
-- Indeed, function application always associates to the left so the expression should be read as (foo bar) baz
-- Another example would be 
foo :: (a -> [a] -> [a]) -> [a] -> [a] -> [a]
foo = foldr 
bar :: a -> [a] -> [a]
bar a as = as ++ [a] 
baz :: [a] 
baz = []
-- Then, foo bar baz (which should be read as (foo bar) baz) has type [a]
-- Note that function application associating to the left and function arrows associating to the right are nice behaviour because it means 
-- that we can implement the default use-case of curried functions of multiple arguments and partial application of such functions without writing many parentheses in either the type or the program.

Can you give examples of programs foo, bar and baz, such that one might expect foo bar baz to be well-typed if function application were to associate in the opposite direction, but such that foo bar baz is in reality ill-typed?

-- For example,
foo :: Bool -> Bool
foo = not
bar :: Bool -> Bool 
bar = not
baz :: Bool
baz = True
-- Then foo (bar baz) is well-typed at type Bool
-- However, as function application associates to the left in reality and not to the right, foo bar baz should be parsed as (not not) True, which does not type check.

2 Currying inClass

Please implement two functions

curry :: ((a, b) -> c) -> (a -> b -> c)
uncurry :: (a -> b -> c) -> ((a, b) -> c)
curry f a b = f (a, b)
uncurry g (a, b) = g a b

Can you convince yourself that curry and uncurry are mutually inverse? Try it out on some example functions!

Please simplify the types of curry and uncurry by removing unnecessary parentheses

curry :: ((a, b) -> c) -> a -> b -> c
uncurry :: (a -> b -> c) -> (a, b) -> c

3 Filter atHome

The function filter can be defined in terms of concat and map:

filter p = concat . map box
  where box x = _

Complete the definition of box.

box x = if p x then [x] else []

4 Function Composition atHome

Function composition first applies the latter of the supplied functions to the argument, the former thereafter. Write a function before that can be used to rewrite f . g . h to h `before` g `before` f. What can you say about associativity of (.) and before?

before :: (a -> b) -> (b -> c) -> (a -> c)
before = flip (.)
-- both (.) and before are associative operations

5 Higher order data types atHome challenging

We have seen that [...] is a type function that maps types to types. Similarly because −> is a type constructor mapping two types to a type, for some c also c −> is a type function mapping a type a to c −> a. Rewrite the type of map by substituting the type function [...] by c −>. Can you derive an implementation from the resulting type?

mapFun :: (a -> b) -> (c -> a) -> (c -> b)
mapFun = (.)