Demystifying Jeremy's Interfaces

Show and Tell
6

First: Merry Christmas to everyone!

Second: Rupert, thank you once more for your interesting comparison between Jeremy’s interfaces and Java classes. I tested your example in IntelliJ, and indeed it works (after some minor corrections). You’re right that there’s no way to get at the internals of an “interface” in Elm. I’ll come back to this in a later post.

W r t a - Rename, Type alias, Applicative functor

Let’s start to look at the code in more detail.

Counter is just one example for the usage of Jeremy’s interfaces. In his talk, Jeremy also used the technique with pages of an SPA application, and Rupert used it with his buffer implementation. So, first, I’ll try to hide most of the Counter-specific things.

We can simply rename the types and the Counter functions:

What Old New
Main type of the interface Counter T
Type constructor Counter C
Record with the operations CounterRecord O
Function to create an Int counter intCounter intT
Function to create a List () counter listCounter listT

This gives us

type T
    = C O


type alias O =
    { up : Int -> T
    , down : Int -> T
    , value : Int
    }


intT : Int -> T
intT =
    impl O
        |> wrap (\raise rep n -> raise (rep + n))
        |> wrap (\raise rep n -> raise (rep - n))
        |> add identity
        |> map C
        |> init (\raise rep -> raise rep)


listT : Int -> T
listT =
    impl O
        |> wrap (\raise rep n -> raise (List.repeat n () ++ rep))
        |> wrap (\raise rep n -> raise (List.drop n rep))
        |> add List.length
        |> map C
        |> init (\raise n -> raise (List.repeat n ()))

Let’s examine the steps of the pipelines in intT and listT. In order to do so, I’ll change every line but the first into a comment and let my editor (VS Code) tell me the resulting type:

intT : (Int -> T) -> Int -> (Int -> T) -> (Int -> T) -> Int -> O
intT =
    impl O
        -- |> wrap (\raise rep n -> raise (rep + n))
        -- |> wrap (\raise rep n -> raise (rep - n))
        -- |> add identity
        -- |> map C
        -- |> init (\raise rep -> raise rep)

Next, I uncomment the second line, note the resulting type, and so on. In the end, this gives us

intT : Int -> T
intT =
    impl O
        -- (Int -> T) -> Int -> (Int -> T) -> (Int -> T) -> Int -> O
        |> wrap (\raise rep n -> raise (rep + n))
        -- (Int -> T) -> Int -> (Int -> T) -> Int -> O
        |> wrap (\raise rep n -> raise (rep - n))
        -- (Int -> T) -> Int -> Int -> O
        |> add identity
        -- (Int -> T) -> Int -> O
        |> map C
        -- (Int -> T) -> Int -> T
        |> init (\raise rep -> raise rep)
        -- Int -> T


listT : Int -> T
listT =
    impl O
        -- (List () -> T) -> List () -> (Int -> T) -> (Int -> T) -> Int -> O
        |> wrap (\raise rep n -> raise (List.repeat n () ++ rep))
        -- (List () -> T) -> List () -> (Int -> T) -> Int -> O
        |> wrap (\raise rep n -> raise (List.drop n rep))
        -- (List () -> T) -> List () -> Int -> O
        |> add List.length
        -- (List () -> T) -> List () -> O
        |> map C
        -- (List () -> T) -> List () -> T
        |> init (\raise n -> raise (List.repeat n ()))
        -- Int -> T

In theses types, there’s a repeating pattern, which Jeremy named “the pipeline shape” in his talk:

(Int     -> T) -> Int     -> ...
(List () -> T) -> List () -> ...

Let’s define a type alias for it. Int and List () are the hidden types used to represent the internal state of the counter. Jeremy names them rep. I’ll stick with one-letter names and use r. For the type T I’ll use the type variable t, and for the remaining “…” an innocent looking a. For the type alias itself I’d choose the name ⁉️, but once again I use a one-letter name. This gives me the following type alias:

type alias W r t a =
    (r -> t) -> r -> a

Note 1: Using type aliases for functions can make function signatures harder to understand, especially if the functions return those type aliases. In this case, it helps me to better understand the roles of Jeremy’s magic internal functions.

Note 2: In Jeremy’s code, the function (r -> t) is named raise, the second r is named rep. So whenever we see (raise -> rep -> xyz), we can replace it with W r t xyz.

Using the new type alias and renaming the type variables, the function signatures can be changed like this:

impl : t -> (raise -> rep -> t)
-->
impl : a -> W r t a

wrap : (raise -> rep -> t) -> (raise -> rep -> (t -> q)) -> (raise -> rep -> q)
-->
wrap : W r t a -> W r t (a -> b) -> W r t b

add : (rep -> t) -> (raise -> rep -> (t -> q)) -> (raise -> rep -> q)
-->
add : (r -> a) -> W r t (a -> b) -> W r t b

map : (a -> b) -> (raise -> rep -> a) -> (raise -> rep -> b)
-->
map : (a -> b) -> W r t a -> W r t b

init : ((rep -> sealed) -> flags -> output) -> ((rep -> sealed) -> rep -> sealed) -> flags -> output
-->
init : ((r -> t) -> i -> t) -> W r t t -> i -> t

Remark: the new signatures are not as general as the old ones, but they match the actual usage, so the new code still compiles.

Ok, the new signature of the wrap function looks familiar! It’s the well-known andMap function! You can find andMap functions in many packages, even for basic Elm types:

Maybe.Extra.andMap       : Maybe a    -> Maybe (a -> b)    -> Maybe b
Result.Extra.andMap      : Result e a -> Result e (a -> b) -> Result e b
Json.Decode.Extra.andMap : Decoder a  -> Decoder (a -> b)  -> Decoder b

wrap                     : W r t a    -> W r t (a -> b)    -> W r t b

W r t a is what in other functional languages is called an “Applicative Functor”.

To be an Applicative Functor, a type has to have two other functions, besides an andMap function. One is a map function, and we indeed have it. Jeremy named it already in the Applicative Functor jargon:

map : (a -> b) -> W r t a -> W r t b

The second missing function for an Applicative Functor is called pure, and it is right there, under another name:

impl : a -> W r t a

In Elm, there are many different names for such a function:

Maybe.Just :          a -> Maybe a
Result.Ok  :          a -> Result e a
Json.Decode.succeed : a -> Decoder a

So why not rename some of the internal functions? What about

impl --> succeed
wrap --> andMap
add  --> andAdd

I chose to rename add, too, because its signature looks very similar to that of andMap, and I therefore wanted to have a name that resembles andMap.

While renaming the functions, I’ll also rename the function parameters. Here’s the result:

succeed : a -> W r t a
succeed a _ _ =
    a


andMap : W r t a -> W r t (a -> b) -> W r t b
andMap rtra rtrab rt r =
    rtrab rt r (rtra rt r)


andAdd : (r -> a) -> W r t (a -> b) -> W r t b
andAdd ra rtrab rt r =
    rtrab rt r (ra r)


map : (a -> b) -> W r t a -> W r t b
map ab rtra rt r =
    ab (rtra rt r)


init : ((r -> t) -> i -> t) -> W r t t -> i -> t
init rtit rtrt i =
    let
        rt : r -> t
        rt r =
            rtrt rt r
    in
    rtit rt i

Why the … did I choose completely meaningless and unreadable parameter names?

Well, for the same reason that I renamed the original types. If I only have to look at the types and not at names like “method”, “pipeline”, and “raise”, it helps me to understand the effect of these functions.

The names I chose are not completely meaningless, of course. Let’s look at andMap:

andMap : W r t a -> W r t (a -> b) -> W r t b
andMap rtra rtrab rt r =
    rtrab rt r (rtra rt r)

The first parameter is of type W r t a, which is an abbreviation of (r -> t) -> r -> a. If you join these letters, you get the name I chose for the first parameter: “rtra”.

The second parameter is of type W r t (a -> b) or (r -> t) -> r -> (a -> b), giving me “rtrab”.

The function result is W r t b or (r -> t) -> r -> b. If a function like andMap returns another function like here, we can remove the parentheses around the function result:

andMap :
    ((r -> t) -> r -> a)
    -> ((r -> t) -> r -> (a -> b))
    -> ((r -> t) -> r -> b)

is the same as

andMap :
    ((r -> t) -> r -> a)
    -> ((r -> t) -> r -> (a -> b))
    -> (r -> t)
    -> r
    -> b

So, we could as well say that andMap takes two more parameters: one of type (r -> t), named “rt”, and the last one of type r named “r”. The function finally returns a value of type b.

This notation helps me to visually check whether the types are correct. Applying a function a -> b (which would be named “ab”) to a value of type a (named “a”) yields a value of type b. In my notation it means that the type of “ab a” is “b”. To get the resulting type (“b”), I only need to remove the name of the argument (“a”) from the beginning of the function name (“ab”). Here’s how this works in the case of andMap:

andMap : W r t a -> W r t (a -> b) -> W r t b
andMap rtra rtrab rt r =
    rtrab rt r (rtra rt r)
    --------    -------
       rab   r     ra   r
       -------     ------
          ab         a
          ------------
                b

It’s no surprise that this code type checks “visually”, too. This way of naming the parameters might help me later when I start to rearrange the code.

Using the new function and parameter names, I think I finally understand all the internal functions, with one exception: init. I don’t understand how it works, but at least I can visually verify that the types are correct. Here’s the function again:

init : ((r -> t) -> i -> t) -> W r t t -> i -> t
init rtit rtrt i =
    let
        rt : r -> t
        rt r =
            rtrt rt r
    in
    rtit rt i

The second parameter of type W r t t or (r -> t) -> r -> t seems to be especially important. The let clause somehow transforms this to a function of type r -> t, which is exactly what is needed as the parameter “raise” in the intT and listT functions. It is a function that takes an r (also called “rep”, a value of the internal type like Int or List ()) and transforms it to the type t, in our case to the main type T.

It’s still mysterious to me…

How do the user-supplied functions look like after the renaming? I’ll leave the type comments in the code, now using the type alias:

intT : Int -> T
intT =
    succeed O
        -- W Int T ((Int -> T) -> (Int -> T) -> Int -> O)
        |> andMap (\raise rep n -> raise (rep + n))
        -- W Int T ((Int -> T) -> Int -> O)
        |> andMap (\raise rep n -> raise (rep - n))
        -- W Int T (Int -> O)
        |> andAdd identity
        -- W Int T O
        |> map C
        -- W Int T T
        |> init (\raise rep -> raise rep)
        -- Int -> T


listT : Int -> T
listT =
    succeed O
        -- W (List ()) T ((Int -> T) -> (Int -> T) -> Int -> O)
        |> andMap (\raise rep n -> raise (List.repeat n () ++ rep))
        -- W (List ()) T ((Int -> T) -> Int -> O)
        |> andMap (\raise rep n -> raise (List.drop n rep))
        -- W (List ()) T (Int -> O)
        |> andAdd List.length
        -- W (List ()) T O
        |> map C
        -- W (List ()) T T
        |> init (\raise n -> raise (List.repeat n ()))
        -- Int -> T

If you know Parser or Decoder pipelines, at least the first steps should be understandable now:

  • We start with succeed O, where O is the record constructor function, with expects values for the up, down and value fields.

  • We then use andMap and andAdd to supply the values for the up, down, and value fields. What we get after these steps is a W r T O value, with r being the internal type, either Int or List ().

  • With map C this is changed to a value of type W r T T, which is exactly the special type mentioned above, which lets init do its magic to internally generate a function of type r -> T.

  • In both cases, init finally gives us a function Int -> T (this Int is the starting value for the counter).

Let’s take a final look at the parameters of andMap, andAdd and init:

In the counter example, andMap always gets a function with 3 parameters: “raise”, the type-raising function of type r -> T, “rep”, the internal representation of the current counter state of type r, and “n”, the Int parameter of the up and down functions.

In these functions, we calculate the result (again of type r). For example, in the down function, the values for the new state are rep - n and List.drop n rep, respectively. In the end, the “raise” function is applied to the result, so that we get back a value of type T.

andAdd is similar to andMap. In this example, it takes a function of type r -> Int, which returns the current counter state. Here it isn’t necessary to change the type of the result, so the functions don’t need a “raise” parameter.

To make it even more explicit and more similar to the andMap calls, I would change the andAdd lines:

        |> andAdd identity
-->
        |> andAdd (\rep -> rep)

        |> andAdd List.length
-->
        |> andAdd (\rep -> List.length rep)

Finally, init gets a function with 2 parameters: again “raise”, the type-raising function of type r -> T, and a second parameter, named “rep” in the intT function, and “n” in the listT function. In both cases it is the starting value for the counter of type Int, therefore I would name the parameter “n” in both cases.

In these functions, we create an internal representation of the starting value (of type r), and then apply the “raise” function to the result, so that we get back a value of type T, just like in the andMap cases.

With the minor changes mentioned above, the functions now look like this:

intT : Int -> T
intT =
    succeed O
        |> andMap (\raise rep n -> raise (rep + n))
        |> andMap (\raise rep n -> raise (rep - n))
        |> andAdd (\rep -> rep)
        |> map C
        |> init (\raise n -> raise n)


listT : Int -> T
listT =
    succeed O
        |> andMap (\raise rep n -> raise (List.repeat n () ++ rep))
        |> andMap (\raise rep n -> raise (List.drop n rep))
        |> andAdd (\rep -> List.length rep)
        |> map C
        |> init (\raise n -> raise (List.repeat n ()))

At least for me, it is now much easier to understand what we are doing here.

In the next part, I’ll start to change the structure of the code.

3 Likes