[Chattered]

They can be implemented via method dictionaries but, sans type system extensions, polymorphic recursion and separate compilation, all uses of a type variable constrained by a type class could, in principle, be monomorphised and the dictionaries eliminated. This is not true of dynamic dispatch.

[naasking]

That's true, but I believe less relevant than most would think. Most of the "dynamic dispatching" people talk about could be similarly monomoprhized. The only real dynamic dispatch occurring in most programs is due to dynamic code loading (separate compilation from your post).

[Chattered]

I disagree, and since we are talking about the expression problem, we should not be conflating dynamic dispatching code which could be statically resolved from dynamic dispatching code which is necessarily dynamic.

A standard use-case of dynamic dispatch is for representing different types of term in a parse tree, where we want to dispatch on nodes according to type. This sort of dispatch cannot be monomorphised, since the the exact callee depends on the shape of the trees being traversed and this almost certainly cannot be figured out statically.

In Haskell, you do not do this sort of dispatch with typeclasses, but instead use ADTs.

When it comes to the expression problem, the tradeoff is that ADTs allow you to easily write new sorts of traversal but do not allow you to extend the tree type in a modular way. By contrast, single dispatch OO allows you to easily extend the tree type by providing new classes to implement the traversal methods, at the cost that you cannot easily define new traversals.

[naasking]

> we should not be conflating dynamic dispatching code which could be statically resolved from dynamic dispatching code which is necessarily dynamic.

This is exactly what I said: most of what people call "dynamic dispatching" is not truly dynamic, and the use of dispatching code is merely an implementation detail.

> In Haskell, you do not do this sort of dispatch with typeclasses, but instead use ADTs.

Except you can, and this is one way to solve the expression problem in Haskell, ie. by lifting constructors to their own types with pattern matching functions lifted to type classes. At which point we come full circle: most uses of ADTs can also be monomorphized and so are not dynamically dispatched either.

Dynamic dispatches then occur only on input at runtime to select the type being instantiated (and so the type class being dispatched into).

[Chattered]

Please explain how to lift the constructors of Maybe to typeclass instances where its use can be monomorphised.

[naasking]

I don't understand what's unclear, lifting values to the type-level and pattern matching on those values to type classes is a standard construction [1].

I only claimed that operations on Maybe can be lifted to type classes, you claimed that all uses of type classes can be monomorphized (barring "fancy types", of which Maybe is presumably not one).

Since all pattern matching functions on simple sums like Maybe can be lifted to type classes using the above translation, and given you said all such type classes can be monomorphized, therefore all uses of Maybe can be monomorphized. Alternately, your original claim could be wrong, or you can provide a counter-example to my claim that pattern matching on Maybe can be translated to type class dispatch.

[1] http://koerbitz.me/posts/Solving-the-Expression-Problem-in-H...