Elm Compiler in Elm - Update

Show and Tell
8

Part 3: Either in Church (?) Encoding

Ok, now that the type Either is opaque, we can change its implementation.

Notice: I always thought that the new implementation I’ll show you in this part was called “Church encoding”, but I’m not so sure anymore. I learned the name a while back when I experimented with so-called “Free Monads”. You can see a Haskell implementation of Free Monads as an Algebraic Data Type in this module: Control.Monad.Free. Back then I noticed there’s another module called Control.Monad.Free.Church which implements Free Monads as a function in the so-called “Church encoding”. This is where I got the name from.

But as I said, I think that I’ve been using the wrong term. When Marc asked his question above, I looked at the Wikipedia article for “Church encoding”. At the bottom there’s a link to the so called “Scott encoding”, and I now think that this is a better name.

So thank you Marc for helping me recognize this mistake.

The new implementation is related to the either function from the last part:

either : (a -> z) -> (b -> z) -> Either a b -> z

This could be read as follows: if we have an Either a b value, we can turn two functions (a -> z) and (b -> z) into a z value.

The so-called “Scott encoding” (!) follows exactly this interpretation. It defines the type Either as:

type Either a b
    = Either ((a -> z) -> (b -> z) -> z)

Unfortunately, this isn’t valid Elm code.

In Haskell we could define an Either type like this:

newtype Either a b =
    Either (forall z. (a -> z) -> (b -> z) -> z)

The forall keyword allows us to hide the type parameter z, but in Elm we have to make it explicit, so we have to change the type Either to:

type Either z a b
    = Either ((a -> z) -> (b -> z) -> z)

With this new definition, the helper functions can be implemented as follows:

left : a -> Either z a b
left a =
    Either (\leftFun _ -> leftFun a)

right : b -> Either z a b
right b =
    Either (\_ rightFun -> rightFun b)

either : (a -> z) -> (b -> z) -> Either z a b -> z
either leftFun rightFun (Either eitherFun) =
    eitherFun leftFun rightFun

As a client of module Either, we have to add the new type parameter z to the Either type:

eitherList : List (Either z Int Char)
eitherList =
    [ left 1
    , right 'a'
    , right 'z'
    , left 9
    , right 'p'
    ]

Normally we can leave the type parameter z unspecified as in the code above.

Only when we call the either function, the type parameter must match the result type:

either : (a -> z) -> (b -> z) -> Either z a b -> z

All four z types must be the same.

This turns the eitherToString function from the last part into:

eitherToString : Either String Int Char -> String
eitherToString anEither =
    either
        (\i -> "Int: " ++ String.fromInt i)
        (\c -> "Char: " ++ String.fromChar c)
        anEither

Notice that the type parameter z is String in this case, because we turn the Either value into a String.

The rest of the code doesn’t have to change. Here’s an Ellie with the new code: (https://ellie-app.com/t5KPkjJG9Lxa1)

Stay tuned for more…

2 Likes