いわゆるチャーチエンコーディング…かと思いきや、Boehm-Berarducciエンコーディングと呼ぶらしい(http://okmij.org/ftp/tagless-final/course/Boehm-Berarducci.html )。
{-# LANGUAGE Rank2Types #-}
import Prelude hiding (Maybe, Bool, Either)
type Unit = forall a. a -> a
unit :: Unit
unit = \x -> x
type Tuple a b = forall c. (a -> b -> c) -> c
pair :: a -> b -> Tuple a b
pair x y = \f -> f x y
type Either a b = forall c. (a -> c) -> (b -> c) -> c
left :: a -> Either a b
left x = \l r -> l x
right :: b -> Either a b
right x = \l r -> r x
type List a = forall b. (a -> b -> b) -> b -> b
nil :: List a
nil = \c n -> n
cons :: a -> List a -> List a
cons x xs = \c n -> c x (xs c n)
type Bool = forall a. a -> a -> a
false :: Bool
false = \f t -> f
true :: Bool
true = \f t -> t
type Maybe a = forall b. b -> (a -> b) -> b
nothing :: Maybe a
nothing = \n j -> n
just :: a -> Maybe a
just x = \n j -> j x