Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

determining function behavior from the type of the function

Tags:

haskell

New to Haskell so sorry if this is very basic

This example is taken from "Real World Haskell" -

ghci> :type fst  
fst :: (a, b) -> a

They show the type of the fst function and then follow it with this paragraph...

"The result type of fst is a. We've already mentioned that parametric polymorphism makes the real type inaccessible: fst doesn't have enough information to construct a value of type a, nor can it turn an a into a b. So the only possible valid behaviour (omitting infinite loops or crashes) it can have is to return the first element of the pair."

I feel like I am missing the fundamental point of the paragraph, and perhaps something important about Haskell. Why couldn't the fst function return type b? Why couldn't it take the tuple as a param, but simply return an Int ( or any other type that is NOT a)? I don't understand why it MUST return type a?

Thanks

like image 726
user772110 Avatar asked Dec 15 '11 18:12

user772110


1 Answers

If it did any of those things, its type would change. What the quote is saying is that, given that we know fst is of type (a, b) -> a, we can make those deductions about it. If it had a different type, we would not be able to do so.

For instance, see that

snd :: (a, b) -> a
snd (x, y) = y

does not type-check, and so we know a value of type (a, b) -> a cannot behave like snd.

Parametricity is basically the fact that a polymorphic function of a certain type must obey certain laws by construction — i.e., there is no well-typed expression of that type that does not obey them. So, for it to be possible to prove things about fst with it, we must first know fst's type.

Note especially the word polymorphism there: we can't do the same kind of deductions about non-polymorphic types. For instance,

myFst :: (Int, String) -> Int
myFst (a, b) = a

type-checks, but so does

myFst :: (Int, String) -> Int
myFst (a, b) = 42

and even

myFst :: (Int, String) -> Int
myFst (a, b) = length b

Parametricity relies crucially on the fact that a polymorphic function can't "look" at the types it is called with. So the only value of type a that fst knows about is the one it's given: the first element of the tuple.

like image 72
ehird Avatar answered Oct 07 '22 19:10

ehird