Is it possible to implement addition on the typed elements of the Church using iterative increment?

Question

I cannot find a way to define the addition as a repeated increment, although this is possible in an untyped language. Here is my code:

{-# LANGUAGE RankNTypes #-}
type Church = forall a . (a -> a) -> (a -> a)

zero :: Church
zero = \f -> id

inc :: Church -> Church
inc n = \f -> f . n f

-- This version of addition works
add1 :: Church -> Church -> Church
add1 n m = \f -> n f . m f

-- This version gives me a compilation error
add2 :: Church -> Church -> Church
add2 n m = n inc m

Compilation error for add2equals

Couldn't match type `forall a1. (a1 -> a1) -> a1 -> a1'
                  with `(a -> a) -> a -> a'
    Expected type: ((a -> a) -> a -> a) -> (a -> a) -> a -> a
      Actual type: Church -> (a -> a) -> a -> a
    In the first argument of `n', namely `inc'
    In the expression: n inc m
    In an equation for `add2': add2 n m = n inc m

Why is this a mistake? Is there a Churchsynonym for this ((a->a) -> a -> a)?

Answer 1

, , , , . ( ImpredicativeTypes.) , ,

type Church = forall a. (a -> a) -> (a -> a)

a -0 (.. ), Church . , , , inc.

, , , , : make Church newtype , . :

{-# LANGUAGE RankNTypes #-}
newtype Church = Church { runChurch :: forall a . (a -> a) -> (a -> a) }

zero :: Church
zero = Church (\f -> id)

inc :: Church -> Church
inc n = Church (\f -> f . runChurch n f)

add2 :: Church -> Church -> Church
add2 n = runChurch n inc