Achieving polymorphism in functional programming

Question

I'm currently enjoying the transition from an object oriented language to a functional language. It's a breath of fresh air, and I'm finding myself much more productive than before.

However - there is one aspect of OOP that I've not yet seen a satisfactory answer for on the FP side, and that is polymorphism. i.e. I have a large collection of data items, which need to be processed in quite different ways when they are passed into certain functions. For the sake of argument, let's say that there are multiple factors driving polymorphic behaviour so potentially exponentially many different behaviour combinations.

In OOP that can be handled relatively well using polymorphism: either through composition+inheritance or a prototype-based approach.

In FP I'm a bit stuck between:

• Writing or composing pure functions that effectively implement polymorphic behaviours by branching on the value of each data item - feels rather like assembling a huge conditional or even simulating a virtual method table!
• Putting functions inside pure data structures in a prototype-like fashion - this seems like it works but doesn't it also violate the idea of defining pure functions separately from data?

What are the recommended functional approaches for this kind of situation? Are there other good alternatives?

Solution 1

Putting functions inside pure data structures in a prototype-like fashion - this seems like it works but doesn't it also violate the idea of defining pure functions separately from data?

If virtual method dispatch is the way you want to approach the problem, this is a perfectly reasonable approach. As for separating functions from data, that is a distinctly non-functional notion to begin with. I consider the fundamental principle of functional programming to be that functions ARE data. And as for your feeling that you're simulating a virtual function, I would argue that it's not a simulation at all. It IS a virtual function table, and that's perfectly OK.

Just because the language doesn't have OOP support built in doesn't mean it's not reasonable to apply the same design principles - it just means you'll have to write more of the machinery that other languages provide built-in, because you're fighting against the natural spirit of the language you're using. Modern typed functional languages do have very deep support for polymorphism, but it's a very different approach to polymorphism.

Polymorphism in OOP is a lot like "existential quantification" in logic - a polymorphic value has SOME run-time type but you don't know what it is. In many functional programming languages, polymorphism is more like "universal quantification" - a polymorphic value can be instantiated to ANY compatible type its user wants. They're two sides of the exact same coin (in particular, they swap places depending on whether you're looking at a function from the "inside" or the "outside"), but it turns out to be extremely hard when designing a language to "make the coin fair", especially in the presence of other language features such as subtyping or higher-kinded polymorphism (polymorphism over polymorphic types).

If it helps, you may want to think of polymorphism in functional languages as something very much like "generics" in C# or Java, because that's exactly the type of polymorphism that, e.g., ML and Haskell, favor.

Solution 2

Well, in Haskell you can always make a type-class to achieve a kind of polymorphism. Basically, it is defining functions that are processed for different types. Examples are the classes Eq and Show:

data Foo = Bar | Baz

instance Show Foo where
    show Bar = 'bar'
    show Baz = 'baz'

main = putStrLn $ show Bar

The function show :: (Show a) => a -> String is defined for every data type that instances the typeclass Show. The compiler finds the correct function for you, depending on the type.

This allows to define functions more generally, for example:

compare a b = a < b

will work with any type of the typeclass Ord. This is not exactly like OOP, but you even may inherit typeclasses like so:

class (Show a) => Combinator a where
    combine :: a -> a -> String

It is up to the instance to define the actual function, you only define the type - similar to virtual functions.

This is not complete, and as far as I know, many FP languages do not feature type classes. OCaml does not, it pushes that over to its OOP part. And Scheme does not have any types. But in Haskell it is a powerful way to achieve a kind of polymorphism, within limits.

To go even further, newer extensions of the 2010 standard allow type families and suchlike.

Hope this helped you a bit.

Solution 3

Who said

defining pure functions separately from data

is best practice?

If you want polymorphic objects, you need objects. In a functional language, objects can be constructed by glueing together a set of "pure data" with a set of "pure functions" operating on that data. This works even without the concept of a class. In this sense, a class is nothing but a piece of code that constructs objects with the same set of associated "pure functions".

And polymorphic objects are constructed by replacing some of those functions of an object by different functions with the same signature.

If you want to learn more about how to implement objects in a functional language (like Scheme), have a look into this book:

Abelson / Sussman: "Structure and Interpration of Computer programs"

Solution 4

Mike, both your approaches are perfectly acceptable, and the pros and cons of each are discussed, as Doc Brown says, in Chapter 2 of SICP. The first suffers from having a big type table somewhere, which needs to be maintained. The second is just traditional single-dispatch polymorphism/virtual function tables.

The reason that scheme doesn't have a built-in system is that using the wrong object system for the problem leads to all sorts of trouble, so if you're the language designer, which to choose? Single despatch single inheritance won't deal well with 'multiple factors driving polymorphic behaviour so potentially exponentially many different behaviour combinations.'

To synopsize, there are many ways of constructing objects, and scheme, the language discussed in SICP, just gives you a basic toolkit from which you can construct the one you need.

In a real scheme program, you'd build your object system by hand and then hide the associated boilerplate with macros.

In clojure you actually have a prebuilt object/dispatch system built in with multimethods, and one of its advantages over the traditional approach is that it can dispatch on the types of all arguments. You can (apparently) also use the heirarchy system to give you inheritance-like features, although I've never used it, so you should take that cum grano salis.

But if you need something different from the object scheme chosen by the language designer, you can just make one (or several) that suits.

That's effectively what you're proposing above.

Build what you need, get it all working, hide the details with macros.

The argument between FP and OO is not about whether data abstraction is bad, it's about whether the data abstraction system is the place to stuff all the separate concerns of the program.

"I believe that a programming language should allow one to define new data types. I do not believe that a program should consist solely of definitions of new data types."

Solution 5

http://www.haskell.org/haskellwiki/OOP_vs_type_classes#Everything_is_an_object.3F nicely discusses some solutions.

View more solutions

Comments

[mikera]

thanks - I like the elegance of Haskell as always, but isn't this effectively defining a conditional branch on the different types of Foo? How does this scale when Foo becomes extremely complex and/or contains lots of nested structures?

[mikera]

thanks for the perspective... everything you say makes sense but lots of received wisdom / code examples seem to clearly separate code and data... e.g. "prefer 1000 functions acting on 1 data structure", MVC inspired design patterns etc. hmmm maybe I should just ignore recieved wisdom and go with what works.....

[Jeremy W. Sherman]

Actually, the typeclass functions associated with a type basically get passed along as a hidden dictionary to the functions that require them, so show (Show a) => a -> () is actually show Show -> a -> () with the instance of Show provided by the compiler as appropriate for the type a.

[Lanbo]

@mikera You have to take into accord that Haskell is a lazy language, so the compiler should be smart enough not to evaluate the nested structures for just a pattern match. But I'm not 100% sure there. Generally, with pattern matching you have to trust the compiler to optimise it for your needs. The GHC does quite a good job there. Keep in mind that a pattern match is handled differently than a switch or if branch.

[Lanbo]

Also, I think type classes are rather a matter of the type checker than of the actual function evaluation, so I don't quite see why the class is passed to the function?

[mokus]

Actually, I should have also mentioned type inference as a complicating factor for supporting both approaches evenly. It's probably the single biggest reason functional languages haven't evolved more in that direction; a language supporting both existential and universal types is spectacularly hard to infer types for, and we functional programmers really like our type inference ;).

[mikera]

thanks... very interesting! As it happens I'm using a Lisp (Clojure) so compile-time type inference is less of an issue :-) but I'd still like to maintain a strict functional style

[Jeremy W. Sherman]

You should read "OOP vs typeclasses". To understand typeclasses quickly, I recommend reading the HOPL-III paper "A History of Haskell: Being Lazy With Class".

[Doc Brown]

@mikera: MVC does not separate code from data - it separates different concerns in your software. That's a different thing, because it acts on a completely different level of abstraction.