The answer is deceptively simple: higher-order functions. An object with virtual methods in the OO language is nothing more than a glorified notation of functions along with some local state. In Haskell, you can directly use function records and store local states in their closures.
More specifically, an OO object consists of:
- A pointer (vptr) to a vtable (virtual method table) that contains implementations for the virtual methods of the object class. In other words, a set of functional pointers; recording functions. In particular, each function has a hidden parameter, which is the object itself, which is passed implicitly.
- Member Data (Local State)
In most cases, all objects and virtual functions look like a complex workaround for the lack of support for closures.
For example, consider the Java Comparator interface:
public interface Comparator<T> { int compare(T o1, T o2);
And suppose you want to use it to sort the list of strings by the nth string characters (suppose they are long enough). You would define a class:
public class MyComparator implements Comparator<String> { private final int _n; MyComparator(int n) { _n = n; } int compare(String s1, String s2) { return s1.charAt(_n) - s2.charAt(_n); } }
And then you use it:
Collections.sort(myList, new MyComparator(5));
In Haskell, you would do it like this:
sortBy :: (a -> a -> Ordering) -> [a] -> [a] myComparator :: Int -> (String -> String -> Ordering) myComparator n = \s1 s2 -> (s1 !! n) 'compare' (s2 !! n) -- n is implicitly stored in the closure of the function we return foo = sortBy (myComparator 5) myList
If you are not familiar with Haskell, here is how it would look in pseudo-Java: (I'm going to do this only once)
public void <T> sortBy(List<T> list, Ordering FUNCTION(T, T) comparator) { ... } public (Ordering FUNCTION(String, String)) myComparator(int n) { return FUNCTION(String s1, String s2) { return s1[n].compare(s2[n]); } } public void foo() { sortBy(myList, myComparator(5)); }
Please note that we did not define any types. All we used are functions. In both cases, the “payload” we passed to the sort function was a function that takes two elements and gives their relative order. In one case, this was achieved by defining a type that implements the interface, implementing its virtual function accordingly and passing an object of this type; otherwise, we simply passed the function directly. In both cases, we retained the internal integer in passing the sort functions. In one case, this was done by adding a private data member to our type, in the other, simply by referencing it in our function, which led to its saving in the function closure.
Consider a more complex widget example with event handlers:
public class Widget { public void onMouseClick(int x, int y) { } public void onKeyPress(Key key) { } public void paint() { } ... } public class MyWidget extends Widget { private Foo _foo; private Bar _bar; MyWidget(...) { _foo = something; _bar = something; } public void onMouseClick(int x, int y) { ...do stuff with _foo and _bar... } }
In Haskell, you can do this as follows:
data Widget = Widget { onMouseClick :: Int -> Int -> IO (), onKeyPress :: Key -> IO (), paint :: IO (), ... } constructMyWidget :: ... -> IO Widget constructMyWidget = do foo <- newIORef someFoo bar <- newIORef someBar return $ Widget { onMouseClick = \xy -> do ... do stuff with foo and bar ..., onKeyPress = \key -> do ..., paint = do ... }
Once again, we note that after the initial Widget we did not define any types. We just wrote a function to create a record of functions and store things in their closures. Which, in most cases, is also the only reason for defining a subclass in an OO language. The only difference from our previous example is that instead of one function, there is a plural, which in the case of Java is encoded by simply placing several functions (and its implementations) in the interface, and in Haskell, by passing a function record instead of a single function. (We could pass a record containing one function in the previous example, but we didn’t like it.)
(It is worth noting that in most cases you do not need dynamic dispatch. If you just want to sort the list based on the default order for the type, you would simply use sort :: Ord a => [a] -> [a] , which uses the Ord instance defined for the given type a , which is selected statically.)
Type-based dynamic submission
One of the differences between the Java approach and the Haskell approach described above is that in the Java approach, the behavior of an object (except for its local state) is determined by its type (or, to put it mildly, a new type is required for each implementation). At Haskell, we record functions as we like. In most cases, this is a net gain (flexibility achieved, nothing is lost), but suppose, for some reason, we want this to be a Java method. In this case, the path that was mentioned in the other answers is type classes and existentials.
To continue our Widget example, suppose we want the Widget implementation to follow from its type (so that a new type is required for each implementation). We define a type class to map the type to its implementation:
-- the same record as before, we just gave it a different name data WidgetImpl = WidgetImpl { onMouseClick :: Int -> Int -> IO (), onKeyPress :: Key -> IO (), paint :: IO (), ... } class IsWidget a where widgetImpl :: a -> WidgetImpl data Widget = forall a. IsWidget a => Widget a sendClick :: Int -> Int -> Widget -> IO () sendClick xy (Widget a) = onMouseClick (widgetImpl a) xy data MyWidget = MyWidget { foo :: IORef Foo, bar :: IORef Bar } constructMyWidget :: ... -> IO MyWidget constructMyWidget = do foo_ <- newIORef someFoo bar_ <- newIORef someBar return $ MyWidget { foo = foo_, bar = bar_ } instance IsWidget MyWidget where widgetImpl myWidget = WidgetImpl { onMouseClick = \xy -> do ... do stuff with (foo myWidget) and (bar myWidget) ..., onKeyPress = \key -> do ..., paint = do ... }
It’s a little awkward that we only have a class to get a record of functions, from which we then need to extract functions separately. I did this only to illustrate certain aspects of type classes: they also simply glorify function entries (which we use below) along with some magic when the compiler inserts the corresponding entry based on the inferred type (which we use above). and keep using below). Let me simplify:
class IsWidget a where onMouseClick :: Int -> Int -> a -> IO () onKeyPress :: Key -> a -> IO () paint :: a -> IO () ... instance IsWidget MyWidget where onMouseClick xy myWidget = ... do stuff with (foo myWidget) and (bar myWidget) ... onKeyPress key myWidget = ... paint myWidget = ... sendClick :: Int -> Int -> Widget -> IO () sendClick xy (Widget a) = onMouseClick xya -- the rest is unchanged from above
This style is often adopted by people who come from OO languages, because it is more familiar and closer to an individual display of how OO languages ​​do it. But for most purposes, it is simply more complex and less flexible than the approach described in the first section. The reason is that if the only essential feature of different widgets is how they implement widget functions, then it makes no sense to create types, interface instances for these types, and then abstract the underlying type again by placing them in an existential shell: it’s easier to simply pass functions directly .
One advantage I can think of is that although Haskell has no subtypes, it does have “subclasses” (probably best called a sub-interface or a sub-constraint). For example, you can do:
class IsWidget a => IsWidgetExtra a where ...additional methods to implement...
and then with any type for which you have IsWidgetExtra , you can also easily use IsWidget methods. The only alternative to a record-based approach is to have records inside records, which includes manual packaging and deployment of internal records. But this would be beneficial only if you want to explicitly emulate a deep hierarchy of OO language classes, which, in turn, you would only do if you wanted to complicate your life. (Also note that in Haskell there is no built-in way to dynamically cast down from IsWidget to IsWidgetExtra . But there is ifcxt )
(What about the benefits of a record-based approach? Besides the need to define a new type every time you want to create something new, records are simple things at the level of values, and values ​​are much easier to manipulate than types. You could For example, write a function that takes Widget as an argument and creates a new Widget based on it, in which some things differ and others remain unchanged. This is similar to subclasses from a template parameter in C ++, only less confusing.)
Glossary
Higher-order function: a function that takes other functions as arguments (or returns them as results)
Record: struct (a class with public data members and nothing more). Also known as a dictionary.
Closing: functional languages ​​(and many others) allow you to define local functions (functions in functions, lambda expressions) that refer to objects in the scope of the definition site (for example, arguments to an external function) that you usually don't expect to be stored, but there is a function "closure". Alternatively, if you have a function like plus that takes two integers and returns an integer, you can only apply it to one argument, say 5 , and the result is a function that takes an integer and returns an integer by adding 5 to it - in this case 5 also stored in the resulting function closure. (In other contexts, “closure” is also sometimes used to mean “function with closure.”)
Type class: not the same as a class in OO. It seems like an interface, but also very different. See here .
UPDATE 29-11-14: Although I think that the core of this answer is still mostly true (HOF in Haskell correspond to virtual methods in OOP), my value judgments have grown with some nuance since I wrote it. In particular, now I think that neither the approach to Haskell nor the OOP is strictly "more fundamental" than another. See this Reddit comment .