Explanation of a Haskell function from an old exam

Question

I'm reviewing an old exam in my Haskell programming course and I can't seem to wrap my head around this function (I think there is just too little information given).

The code given is

myId x = x

function n f
 | n > 0 = f . function (n-1) f
 | otherwise = myId

I know that if I for example call the function with the input 2 (*2), I will get a function as result. And if I call it with (-2) (*2) 1 I will get the result 1.

I just don't know how? Also I can't wrap my head around the typecast of the function.

I know that these two options are correct but I don't understand why (probably parentheses that confuse me at the moment).

function :: (Num a, Ord a) => a -> (a -> a) -> a -> a
function :: (Num a, Ord b) => a -> (b -> b) -> b -> b

Anyone that can clarify how I should "read" this function and how I should understand how the typecast works (been reading my Programming in Haskell literature and from Learn You a Haskell but been going in circle for a few days now).

valderman valderman · Accepted Answer · 2013-05-31T11:25:54

function takes some number n and a function f :: a -> a, and composes that function with itself n times, returning another function of type a -> a. When the returned function is applied to a value of type a, the result is essentially the same as executing f in a loop n times, using the output of each previous step as the input for the next.

Perhaps it is easier to see the similarity if the final parameter is made explicit:

function :: (Ord a, Num a) -> a -> (b -> b) -> b -> b
function n f x
  | n > 0     = f (function (n-1) f x)
  | otherwise = x

This is functionally equivalent to your point-free function.

In Haskell, a function f :: a -> b -> c can be interpreted either as "a function that takes an a and a b and returns a c" or "a function that takes an a and returns a function from b to c". When you apply a function to one or more inputs, think of each input as eliminating one of the function's arguments. In this instance, function 10 returns a new function with type (a -> a) -> a -> a, and function 2 (*2) returns a function with type Num a => a -> a.

When you think of it this way, it should hopefully be clear why function (-2) (*2) 1 returns a number while function 2 (*2) returns a function. There is no type casting going on; when you are applying the three argument function to two inputs, you get another function back instead of a value, since you didn't provide the final input needed to compute that value.

Explanation of a Haskell function from an old exam

1 Answers