That is true, but the proposition is one that is encoded in the type. There are many derivations of certain proofs. Consider:
map :: (a -> b) -> [a] -> [b]
And [a] is shorthand for a recursive type: \forall a . \mu l . (a * l) + ().
And the translation of types to propositions means that the sum type -- either I have () or I have a list, translates to a logical connective of "or". The product type -- I have an a and the rest of the list -- translates to "and" .
The proposition is therefore that, for all a, for all b, if a implies b, then true or (a and list of a) implies true or (b and list of b).
There are several proofs of this proposition, and some of them are useless.
The standard one:
map f [] = []
map f (x:xs) = f x : map f xs
Is what we want.
There's another one, though:
map f [] = []
map f (x:xs) = [f x]
And many others that aren't so useful as the standard one.
Anyway, this has been a long and roundabout way of saying that, while a good type system give you a lot of nice static properties about a program, you simply cannot ignore dynamic semantics and rely on the types. Well-typed programs are correct in that they will not reach a state where evaluation is undefined / get stuck ("I'm supposed to do what? These are Strings, not Ints!"), but they do not imply correctness of the program, even though they do provide a proof of a proposition!
And the translation of types to propositions means that the sum type -- either I have () or I have a list, translates to a logical connective of "or". The product type -- I have an a and the rest of the list -- translates to "and" .
The proposition is therefore that, for all a, for all b, if a implies b, then true or (a and list of a) implies true or (b and list of b).
There are several proofs of this proposition, and some of them are useless.
The standard one:
Is what we want.There's another one, though:
And many others that aren't so useful as the standard one.Anyway, this has been a long and roundabout way of saying that, while a good type system give you a lot of nice static properties about a program, you simply cannot ignore dynamic semantics and rely on the types. Well-typed programs are correct in that they will not reach a state where evaluation is undefined / get stuck ("I'm supposed to do what? These are Strings, not Ints!"), but they do not imply correctness of the program, even though they do provide a proof of a proposition!