Programs written in for example Java rely a lot on dynamic dispatch. How do such programs be expressed in functional languages such as Haskell? In other words what is the Haskell way of expressing the idea underneath "dynamic dispatch"?
|
The answer is deceptively simple: higher-order functions. An object with virtual methods in an OO language is nothing more than a glorified record of functions together with some local state. In Haskell you can use records of functions directly, and store the local state in their closures. More concretely, an OO object consists of:
A lot of the time the whole edifice of objects and virtual functions feels like an elaborate workaround for the lack of support for closures. For example consider Java's
And suppose you want to use it to sort a list of strings based on the strings' Nth characters (assume they are long enough). You would define a class:
And then you use it:
In Haskell you would do it like this:
If you're not familiar with Haskell, here's how it would roughly look in a kind of pseudo-Java: (I'm only going to do this once)
Note that we did not define any types. All we used are functions. In both cases the "payload" that we passed to the sort function was a function that takes two elements and gives their relative ordering. In one case this was accomplished by defining a type implementing an interface, implementing its virtual function in the appropriate way, and passing an object of that type; in the other case we just passed a function directly. In both cases we stored an internal integer in the thing we passed to the sort function. In one case this was done by adding a private data member to our type, in the other by simply referring to it in our function, causing it to be retained in the function's closure. Consider the more elaborate example of a widget with event handlers:
In Haskell you could do it like this:
Note again that after the initial (It's worth noting somewhere that a lot of the time you don't need dynamic dispatch. If you just wanted to sort a list based on the default ordering for the type, then you would simply use Type-Based Dynamic DispatchOne difference between the Java approach and the Haskell approach above is that with the Java approach, the behaviour of an object (except for its local state) is determined by its type (or less charitably, each implementation requires a new type). In Haskell we're making our records of functions however way we like. Most of the time this is a pure win (flexibility gained, nothing lost), but suppose that for some reason we want it the Java way. In that case the way to go, as mentioned by other answers, is type classes and existentials. To continue our
It's a bit awkward that we have a class only to get a record of functions, which we then have to take the functions out of separately. I only did it this way to illustrate separate aspects of type classes: they're also just glorified records of functions (which we use below) together with some magic where the compiler inserts the appropriate record based on the inferred type (which we use above, and continue using below). Let's simplify:
This style is often adopted by people coming from OO languages, because it's more familiar and closer to a one-for-one mapping from the way OO languages do it. But for most purposes it's just more elaborate and less flexible than the approach described in the first section. The reason is that if the only significant thing about the various Widgets is the way they implement the widget functions, then there's little point in making types, instances of the interface for those types, and then abstracting away the underlying type again by putting them in an existential wrapper: it's simpler to just pass the functions around directly. One advantage I can think of is that while Haskell doesn't have subtyping, it does have "subclassing" (probably better referred to as sub-interfacing or sub-constraining). For example you could do:
and then with any type for which you have (What about the advantages of the record-based approach? Besides not having to define a new type every time you want to do a new thing, records are simple value-level things, and values are much easier to manipulate than types. You could, for example, write a function that takes a Glossary
EDIT 29-11-14: While I think the kernel of this answer is still essentially correct (HOFs in Haskell correspond to virtual methods in OOP), my value judgements have grown some nuance since I wrote it. In particular, I now think that neither Haskell's nor OOP's approach is strictly "more fundamental" than the other. See this reddit comment. |
||||
|
It's surprising how often you don't actually need dynamic dispatch, just polymorphism. For example, if you're going to write a function that sorts all the data in a list, you want it to be polymorphic. (I.e., you do not want to have to reimplement this function for every single type, by hand. That would be bad.) But you don't actually need anything dynamic; you know at compile-time what's actually in the list or lists you want sorted. So you don't actually need run-time type lookup at all in this case. In Haskell, if you just want to move stuff around and you don't need to know or care what type it is, you can use so-called "parametric polymorphism", which is roughly something like Java generics or C++ templates. If you need to be able to apply a function to the data (e.g., to sort data you need order comparisons), you can pass the function to do that in as an argument. Alternatively, Haskell has a thing that's a bit like a Java interface, and you can say "this sorting function accepts any type of data that implements this interface". So far, no dynamic dispatch at all, only static. Note also that since you can pass functions as arguments, you can do "dispatch" manually by hand. If you really need actual dynamic dispatch, you can use "existential types", or you can use the |
||||
|
Ad-hoc polymorphism is done via typeclasses. More OOP-like DD is emulated with existential types. |
|||||
|
Maybe you need ADT plus pattern matching ?
|
|||
|