# Curry-Howard-Lambek correspondence

**Curry-Howard Isomorphism** is an isomorphism between types (in programming languages) and propositions (in logic). Interestingly, the isomorphism maps programs (functions in Haskell) to (constructive) proofs (and *vice versa*).

## Contents

## The Answer

As is well established by now,

```
theAnswer :: Integer
theAnswer = 42
```

The logical interpretation of the program is that the type `Integer`

is inhibited (by the value `42`

), so the existence of this program *proves* the proposition `Integer`

(a type without any value is the "bottom" type, a proposition with no proof).

## Theorems for free!

Things get interesting when polymorphism comes in. The composition operator in Haskell proves a very simple theorem.

```
(.) :: (a -> b) -> (b -> c) -> (a -> c)
(.) f g x = f (g x)
```

The type is, actually, `forall a b c. (a -> b) -> (b -> c) -> (a -> c)`

, to be a bit verbose, which says, logically speaking, for all propositions `a, b`

and `c`

, if from `a`

, `b`

can be proven, and if from `b`

, `c`

can be proven, then from `a`

, `c`

can be proven (the program says how to go about proving: just compose the given proofs!)