Search code examples
haskelltype-signature

Explain the type signatures for High order functions?

function :: (t2 -> t1) -> (t1 -> t) -> t2 -> t
function f1 f2 x = f2 (f1 x )

function1 :: (t -> t) -> t -> t
function1 f1 x = f1 (f1 x)

function11 :: (t1 -> t1) -> t -> t1 -> t1
function11 f1 f2 x = f1 (f1 x)

function3 :: (t1 -> t1) -> t -> t1 -> t1
function3 f1 f2 x = f1 (f1 (f1 x))

function4 :: (t1 -> t1) -> t -> t1 -> t1
function4 f1 f2 x = f1 (f1 (f1 x))

Can anyone explain the type signatures for the the first two and also why the type signature for the last 3 are the same? I'm reading about high order functions and what they are hasn't gotten into my head.

Solution

  • Can anyone explain the type signatures for the the first two?

    Let's give some slightly more human-readable names for the type variables.

    function :: (in -> tmp) -> (tmp -> out) -> in -> out
function f1 f2 x = f2 (f1 x )

    This type says: if you give me a function that munges inputs into temporary values, and a function that munges temporary values into outputs, I will give you back a function which munges inputs into outputs. You could imagine drawing a "data processing pipeline", where we have a bunch of objects of various types, and operations that turn values of one type into values of another type. For example, here's how I might visually draw your function:

    in    ----- f1 ----->    tmp    ----- f2 ----->    out
  \                                               ^
   \                                             /
    `------------- function f1 f2 --------------'

    The intended interpretation here is that you could imagine taking two routes in this pipeline -- either you first use operation f1, then use operation f2; or else you can use the operation function f1 f2 to do the whole thing in one go.

    function1 :: (t -> t) -> t -> t
function1 f1 x = f1 (f1 x)

    Here, function1 takes a function for transforming ts (into other ts), and gives back a (potentially different) function for transforming ts (again, into other ts). Again, drawing the data-processing pipeline for this, you might get something like this:

    t    ----- f1 ----->    t    ----- f1 ----->    t
 \                                             ^
  \                                           /
   `------------- function1 f1 --------------'

    Why is the type signature for the last 3 the same?

    Let's quickly refresh our memory on the definitions of the last three functions:

    function2 f1 f2 x = f1 (f1 x)
function3 f1 f2 x = f1 (f1 (f1 x))
function4 f1 f2 x = f1 (f1 (f1 x))

    Okay, so the first interesting thing about function2, function3, and function4 is that they take three arguments, f1, f2, and x, but each of them ignores f2 entirely -- it is never mentioned on the right-hand side of the = for any of them. Secondly, function3 and function4 are defined in exactly the same way, so it's no surprise they can be given the same type.

    Taking these two things into account, we can narrow the question somewhat, so that we are asking why these two functions have the type signature:

    function2' f x = f (f x)
function3' f x = f (f (f x))

    Specifically, their shared type signature is this:

    (t -> t) -> (t -> t)

    As we discussed above for function1, this means that they take a transformation on ts, and they also happen to produce a transformation on ts. Thinking again in terms of data processing pipelines, it should now be pretty clear why they have the same type: it doesn't matter whether we apply our function f two times or three inside the pipe; the type just ain't changing:

       .------------------------ function3' f ------------------------.
  /                                                                \
 /                                                                  v
t    ----- f ----->    t    ----- f ----->    t    ----- f ----->    t
 \                                           ^
  \                                         /
   `------------ function2' f -------------'

    Assuming f is a function that starts at a node labeled t and ends at a node labeled t, then no matter how many times we apply f before stopping, we're always coming back to a function that starts at a node labeled t and ends at a node labeled t.