<commit_before>---
title: Church Representations
---

A project I've been playing with lately is generalizing `maybe`.
Now on the surface that sounds well.. boring. But there's actually
some interesting concepts buried in here.

## Lambda The Almighty
Let's start by specifying what I mean when I say "generalize".
When we look at `maybe`, the type gives us a pretty strong
clue on how to implement it

``` haskell
    maybe :: b -> (a -> b) -> Maybe a -> a
    maybe nothingCase justCase Nothing  = nothingCase
    maybe nothingCase justCase (Just a) = justCase a
```

Each argument of corresponds to a different case of
the sum type `Maybe`.

There's actually a name for this idea, it's encoding
a data type within functions: Church Encoding.

Let's rattle of some examples:

Tuples

``` haskell
    {-# LANGUAGE RankNTypes #-}
    -- We'll call a tuple a Product because it
    -- looks like the cartesion *product* of two types
    type Product a b = forall c. (a -> b -> c) -> c
    pair :: a -> b -> Pair a b
    pair a b = \destruct -> destruct a b

    -- We can easily make fst and snd
    fst :: Pair a b -> a
    fst p = p $ \a b -> a
    snd :: Pair a b -> b
    snd p = p $ \a b -> b
```

We can do `Either` as well

``` haskell
    -- We'll call Either a "sum" because it
    -- looks like the disjoint union (sum) of two types
    type Sum a b = forall c. (a -> c) -> (b -> c) -> c
    inl :: a -> Sum a b
    inl a = \l r -> l a

    inr :: b -> Sum a b
    inr b = \l r -> r b
```

Look familiar? That's just `Data.Either.either`!
Now if we squint at these we can imagine building up
more complex types from these building blocks

``` haskell
    data AFew = NoVal | OneVal Int | ThrVal Int Bool String

    type ChurchAFew =
      Sum () (Sum Int (Prod Int (Prod Bool String)))

    noVal :: ChurchAFew
    noVal = inl ()

    oneVal :: Int -> ChurchAFew
    oneVal i = inr (inl i)<commit_msg>Fixed a few typos<commit_after>---
title: Church Representations
---

A project I've been playing with lately is generalizing `maybe`.
Now on the surface that sounds well.. boring. But there's actually
some interesting concepts buried in here.

## Lambda The Almighty
Let's start by specifying what I mean when I say "generalize".
When we look at `maybe`, the type gives us a pretty strong
clue on how to implement it

``` haskell
    maybe :: b -> (a -> b) -> Maybe a -> b
    maybe nothingCase justCase Nothing  = nothingCase
    maybe nothingCase justCase (Just a) = justCase a
```

Each argument of corresponds to a different case of
the sum type `Maybe`.

There's actually a name for this idea, it's encoding
a data type within functions: Church Encoding.

Let's rattle of some examples:

Tuples

``` haskell
    {-# LANGUAGE RankNTypes #-}
    -- We'll call a tuple a Product because it
    -- looks like the cartesion *product* of two types
    type Product a b = forall c. (a -> b -> c) -> c
    pair :: a -> b -> Product a b
    pair a b = \destruct -> destruct a b

    -- We can easily make fst and snd
    fst :: Product a b -> a
    fst p = p $ \a b -> a
    snd :: Product a b -> b
    snd p = p $ \a b -> b
```

We can do `Either` as well

``` haskell
    -- We'll call Either a "sum" because it
    -- looks like the disjoint union (sum) of two types
    type Sum a b = forall c. (a -> c) -> (b -> c) -> c
    inl :: a -> Sum a b
    inl a = \l r -> l a

    inr :: b -> Sum a b
    inr b = \l r -> r b
```

Look familiar? That's just `Data.Either.either`!
Now if we squint at these we can imagine building up
more complex types from these building blocks

``` haskell
    data AFew = NoVal | OneVal Int | ThrVal Int Bool String

    type ChurchAFew =
      Sum () (Sum Int (Prod Int (Prod Bool String)))

    noVal :: ChurchAFew
    noVal = inl ()

    oneVal :: Int -> ChurchAFew
    oneVal i = inr (inl i)
{'fraction_non_alphanumeric': 0.10430247718383312, 'fraction_numerical': 0.0, 'mean_word_length': 2.443447037701975, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 49, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4801577', 'n_tokens_mistral': 1266, 'n_tokens_neox': 1195, 'n_words': 602}