Experiment with type-classes and Elm

[opvasger]

Hello

In the spirit of learning more about functional programming, I’ve watched a couple of talks on YouTube by Simon Peyton Jones, and the journey of Haskell!

Question

As Simon gets into type-classes at this point in one of his talks, I immediately though of a controversial statement from this community:

Elm doesn’t support type-classes!! When will it do so??

Needless to say, after rewatching a couple of times, and thinking about my intuitions on the subject, I wasn’t really convinced.

So, does Elm not support typeclasses?

Experiment:

I’ve done some experimentation to qualify my question a bit.

I was passively consuming video, but really felt like I could play with this idea a bit, so I went ahead and did just that.

Simon says that the underlying “System F” translation from Haskell has functions with the bounded polymorphism of type-classes simply take an extra argument with a record of functions in the given class. Here’s some type-signatures from Haskell:

sort :: Ord a => [a] -> [a]
serialise :: Show a => a -> String
member :: Eq a => a -> [a] -> Bool

ok, so in Elm:

module Orderable exposing (Orderable, isOrderable)

type alias Orderable kind value =
    { kind | orderBy : value -> value -> Basics.Order }

isOrderable : Fuzzer value -> Order kind value -> Test
isOrderable fuzzer orderable =
    Test.describe "can this type of value be ordered?"
        [ isSymmetric fuzzer orderable
        ]

isSymmetric : Fuzzer value -> Orderable kind value -> Test
isSymmetric fuzzer { orderBy } =
    Test.fuzz2 fuzzer fuzzer "is the ordering symmetric?" <|
        \first second ->
            case orderBy first second of
                EQ ->
                    Expect.equal (orderBy second first) EQ

                LT ->
                    Expect.equal (orderBy second first) GT

                GT ->
                    Expect.equal (orderBy second first) LT

So far, so good. Let’s say this exists as a library on elm-package - now, how would I implement this sort of interface on a binary-tree kind of thing?:

module Tree exposing (Tree, empty, insert)

import Orderable exposing (Orderable)

type Tree value
    = Leaf
    | Branch (Tree value) value (Tree value)

empty : Tree value
empty =
    Leaf

insert : Orderable kind value -> value -> Tree value -> Tree value
insert order value tree =
    case tree of
        Leaf ->
            Branch Leaf value Leaf

        Branch left middle right ->
            case order.orderBy value middle of
                EQ ->
                    tree

                LT ->
                    Branch (insert order value left) middle right

                GT ->
                    Branch left middle (insert order value right)

Simon says type-classes are extensible. Well, the kind-type-parameter makes Orderable extensible in the sense that you can use the extensible-records feature of Elm to build a new type-alias around it and extend with new functions - a more elaborate example of this sort of tinkering is available here. In my experience, this is a misuse of extensible records, but it’s the nicest I could come up with here.

Finally:

• type-classes can exist in the package-ecosystem, as a niche.
• you explicitly import type-classes, and have to test implementations to make sure axioms are respected
• runtime implications aren’t obvious to me - does Haskell do anything fancy to make the “pass records of functions around” fast somehow? Can it cause slowdowns?

Maybe this is a horrible idea? if so why? I don’t think I’d hate programming on this sort of interface.

[eike]

This certainly works to some degree. Unfortunately, Elm is missing some other features from Haskell as well which makes this a lot less useful: in particular, Elm does not have higher-kindred types which means that you won’t be able to implement Functor.

(I don’t quite understand the role of the kind parameter but) here’s what you’d want:

type alias Functor f = 
   { fmap : f a -> f b }

which is illegal in Elm for several reasons:

• Type parameters in Elm have to be actual types, but f needs to be of kind * -> * (i.e. for any type a, f a is a type).
• You can’t have implicitly all-quantified in functions in records. (Though maybe adding a and b as parameters to Functor would help. I can’t test it because of problem 1.)

[rupert]

@opvasger

Maybe this is a horrible idea? if so why? I don’t think I’d hate programming on this sort of interface.

Its not completely horrible and sometimes useful. I call this approach “the poor mans typeclass”, since we didn’t get full support in Elm. Asside from the inability to define the class of Functors and any other higher kinded type classes, there is another drawback around the need to fully declare all the type variables in Elm.

The type variables in Elm are forall quantified as @eike points out. ‘implicitly all-quantified’ type variables are more properly called existentially quantified or just existential type variables.

Below is some code from one of my published packages to illustrate how this can be useful and also what the limitations are.

I have defined the class of Buffers, which can yield their head element orelse can place a new element into the buffer. This is handy for search algorithms as by subsituting different buffer implementations I can get different search orderings, depth-first, breadth-first or ordered by some heuristic or cost metric. The basic search algorithm remains the same - explore the head element from the buffer, orelse if it is not the goal of the search, expand its children into the buffer and recursively explore those.

The limitation of this is that I had to declare the buffer implementation as one of the type variables. It is either List (Node state) or (Heap (Node state)). As these types are different I cannot have a list of Buffers, if say I wanted to try a couple of searches with different orderings by providing a list of them. In Haskell you can just not declare the buffer type variable at all, in which case it is called an existential type variable.

I could do:

type BufferImpl state
    = ListBuffer (List (Node state))
    | HeapBuffer (Head (Node state))

and make them all have the same type that way. But that does not give me an open ended class which can be implemented in arbitrarily many different ways. That is, some third party using this package would not be able to extend the BuffersImpl type to add a new implementation, based on Array say.

So Elm always tries to close you down and does not provide many opportunities for coding in an extensible way, which is kind of the whole point of ‘classes’ in Haskell or OO languages. Whenever you need an existential type variable in Elm, you can always susbtitute a custom type instead, and end up with a non-extensible system instead. Mostly I like this about Elm, as it always forces you back to dealing with more concrete things instead of defining lots of clever open-ended abstractions.

{-| Defines the operations needed on state buffers that hold the pending search
states.
-}
type alias Buffer state buffer =
    { orelse : Node state -> buffer -> buffer
    , head : buffer -> Maybe ( Node state, buffer )
    , init : List (Node state) -> buffer
    }

{-| Implements a first-in first-out buffer using Lists.
-}
fifo : Buffer state (List (Node state))
fifo =
    { orelse = \node list -> node :: list
    , head =
        \list ->
            case list of
                [] ->
                    Nothing

                x :: xs ->
                    Just ( x, xs )
    , init = \list -> list
    }

{-| Implements a last-in first-out buffer using Lists and appending at to the end.
-}
lifo : Buffer state (List (Node state))
lifo =
    { fifo
        | orelse = \node list -> list ++ [ node ]
    }


{-| Implements an order buffer using a heap. A state comparison function is
supplied to construct the buffer on.
-}
ordered : Compare state -> Buffer state (Heap (Node state))
ordered compare =
    { orelse = \node heap -> Heap.push node heap
    , head = \heap -> Heap.pop heap
    , init = \list -> Heap.fromList (Heap.smallest |> Heap.using (nodeCompare compare)) list
    }

---

[ You can find the code snippets above here:
https://github.com/the-sett/ai-search/blob/master/src/Search.elm#L132
https://github.com/the-sett/ai-search/blob/master/src/Search.elm#L276
https://github.com/the-sett/ai-search/blob/master/src/Search.elm#L293
https://github.com/the-sett/ai-search/blob/master/src/Search.elm#L303
]

[mauro]

I watched https://youtu.be/QDleESXlZJw (shared by someone in this community) and it has convincing arguments against extensive and pervasive use of typeclasses. But I also know that some use of typeclasses can be useful. I think Elm doesn’t need user-defined typeclasses. I also think that the ergonomics for the currently existing typeclasses (number, comparable, appendable) can be improved !

For example, functions to create arbitrary instances of comparable and appendable would be nice

toComparable : (a -> a -> Order) -> a -> comparable

toAppendable : (a -> a -> a) -> a -> appendable

Or even numbers?

toNumber :
    { add : a -> a -> a
    , subtract : a -> a -> a
    , ...
    }
    -> a
    -> number

I don’t know how to extract the number back into an a, so this idea is probably useless . But probably there is some way of doing it without adding too much to the language (?

Also, Elm having the “equatable” typeclass would be nice. (And it probably will )

[rupert]

I think this makes a good example of the poor man’s typeclass. It makes markdown rendering more flexible, by providing an open-ended way of extending the renderer, it is also farily obvious what it does, and it is aimed at doing something quite practical and not too abstract, or trying to push the bounds of what is possible with Elm:

https://package.elm-lang.org/packages/dillonkearns/elm-markdown/latest/Markdown-Renderer

There are also quite a few packages that define new Program types which can be good examples too (some of them are getting a bit abstract, or not as useful as they might first appear).