Existential Types in Elm

Learn
1

Hello everyone,
I randomly stumbled upon this post referring to a presentation done during an online meetup about Existential types in Elm, or how to work with Elm in Object-Oriented style.

It’s basically a tutorial on how to implement and use a “type interface” that hides its implementation behind closures.

I found it very clever and interesting, so I started studying the implementation to get a better understanding. While I was unraveling the type pipeline I realized that the same result could be achieved by simply defining the interface constructors recursively, like so:

type Counter
    = Counter CounterRecord

type alias CounterRecord =
    { up : Int -> Counter
    , down : Int -> Counter
    , value : Int
    }

intCounter : Int -> Counter
intCounter n =
    Counter {
        up = \m -> n + m |> intCounter
        , down = \m -> n - m |> intCounter
        , value = n
    }


listCounter : Int -> Counter
listCounter n =
    let 
        state = List.repeat n ()
    in
        Counter {
            up = \m -> List.length state + m |> listCounter
            , down = \m -> List.drop m state |> List.length |> listCounter
            , value = List.length state
        }

Basically instead of passing around a pipeline with the anonymous raise function I just reify the interface through simple recursion.

Could someone point out if there is any advantage in @jhbrown 's approach? Do I lose something by cutting out the pipelining?

2

BTW - I was wrong to call them existential types. I think it is more accurate to describe this as ad-hoc polymorphism.

3

For the integer version, you don’t lose much by doing the recursive call the way you do it.

For the list version of the counter, though, you wind up having to convert from the internal representation (a list of length N) to an integer (N) so you can make the recursive call: up = \m -> List.length state + m |> listCounter which is at best inefficient, and for more complex data structures with hidden state would not work at all.

4

Aren’t those two slightly different concepts?

Ad hoc polymorphism allows to write code that behaves differently depending on the data type; the way I see it this can be achieved simply by passing the different behaviour explicitly, like sortWith allowing to sort different List a by specifying a custom compare function (that in other languages would be expressed with a Comparable typeclass/trait/interface).

However, this does not necessarily allow me to completely ignore the data implementation: sortWith works for Lists of any of type a, but only one list at a time. The Counter interface allows me to create a List of Counters that are implemented with different data types behind the scenes.

I’d say that ad-hoc polymorphism is a Software concept while Existential types is a more general, Logic related idea. The latter can be obtained by the former, but the former entails more.

5

What if I moved up the conversion (kinda like your approach does with the init step)?

listCounter : Int -> Counter
listCounter n = 
    let 
        innerListCounter : List () -> Counter
        innerListCounter l = Counter {
            up = \m -> List.repeat m () ++ l |> innerListCounter
            , down = \m -> List.drop m l |> innerListCounter
            , value = List.length l
            }
    in
        innerListCounter (List.repeat n ())

I guess this is more dependent on the developer optimizing their own code. Then again, no one prevents me from shooting myself in the foot with the worst of both approaches:

listCounter : Int -> Counter
listCounter =
    impl CounterRecord
        |> wrap (\_ rep n -> n + (List.length rep) |> listCounter
        |> wrap (\_ rep n -> n - (List.length rep) |> listCounter
        |> add List.length
        |> map Counter
        |> init (\raise n -> raise (List.repeat n ()))

Also, performance wise I would be more worried about the multitude of closures that are created along the pipeline, although maybe Javascript handles them better than I give it credit for.

6

I think you are right about this.

I have used this technique to write code that is processing mouse events - max a few hundred per second, and for that it was fine. This code was for a drawing program, where each element of the drawing implemented the same interface, making it easier to add new element kinds to the drawing program.

But suppose you used it to define a Comparable interface, or maybe a Hashable interface, for data structures. I think the performance penalty is going to be considerable.

Never benchmarked it. We should.

7

I agree that your innerListCounter approach is an alternate way to implement the basic idea – if you prefer that to pipelines, go for it.

In terms of performance cost, for the listCounter, copying a list of arbitrary length on every “mutation” is likely to be dominant, but you’re right that for O(1)-size data structures, making a lot of new closures on every mutation is going to be expensive. This is where you can get close to a Go- or Java-like interface, but the performance will definitely be worse because Go and Java don’t have to make a whole new set of closures each time you wrap data in an interface or mutate it.

1 Like
8

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.