CODEWITHSUNDEEP
haskell
user754458
user754458

Reputation: 193

Why an a -> b -> c function argument can accept a -> a type?

This compiles successfully:

test = f id
f :: (a -> b -> c) -> String
f g =  "test"

id has type a -> a, but f have a first argument of type (a -> b -> c).

I think it should not compile. I cannot understand it.

Upvotes: 2

Views: 195

Answers (2)

user1937198
user1937198

Reputation: 5348

Because you can bind the uninstantiated variable. f :: (a -> b -> c) -> String says that for any 3 types a, b and c, f takes a function from a to b to c and returns string.

Its important to remeber that f :: (a -> b -> c) -> String is equivalent to f :: (a -> (b -> c)) -> String because of currying.

id takes any type, and returns that type.

So if we swap that in, id is returning b -> c, and taking a, so if a can be b -> c which it can as a can be any type, then this is fine.

Upvotes: 7

Daniel Wagner
Daniel Wagner

Reputation: 152837

Short version: it works because id can take and return functions -- and so can behave as if it were a two-argument function. Now for the long version.

id is a function that takes a value and returns it unchanged. Because it's so simple, it can do that for all kinds of different values -- Ints and Bools and Strings and lists and trees...

id :: Int -> Int
id :: Bool -> Bool
id :: String -> String
id :: [(b, c)] -> [(b, c)]
id :: Tree b -> Tree b
id :: (b -> c) -> (b -> c)

...and functions, why not!

f is a function that takes two-argument functions and ignores them. Because its handling of the function you give it is so simple, it can do that for all kinds of different two-argument functions -- addition, concatenation, pairing, ignoring, printing...

f :: (Int -> Int -> Int) -> String
f :: ([b] -> [b] -> [b]) -> String
f :: (b -> c -> (b, c)) -> String
f :: (b -> c -> b) -> String
f :: (Handle -> String -> IO ()) -> String
f :: ((b -> c) -> b -> c) -> String

...and the operation that takes a function and an argument and applies the one to the other, why not!

Ah, but two argument functions are really just one-argument functions that themselves return a function. So these two types are really just different spellings of the same type:

(b -> c) -> (b -> c)
(b -> c) -> b -> c

And, it turns out, the two behavior descriptions I gave for these two types also turn out to be the same. Recall they were:

  1. A function that takes a function as an argument and returns it unchanged.
  2. A function that takes a function as an argument, and an argument for that function, and applies one to the other.

I'll let you stew for a bit on why those turn out to be the same!

In any case, at this point it should be much more clear why this works. And, for the mechanical version of the answer, we can take these two types:

id :: a -> a
f :: (a -> b -> c) -> String

and make them fit together by choosing a ~ b -> c for both. (It is just a coincidence that the two instantiations of a are to the same type -- this is not generally the case when doing unification!) After instantiating a to b -> c in both type signatures, we get:

id :: (b -> c) -> b -> c
f :: ((b -> c) -> b -> c) -> String

Upvotes: 6

Related Questions