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?

Oaten

I am interested in this questions and although the answers are all very helpful and interesting, I believe that they may miss one important point, i.e. the ability to construct a heterogeneous collection (i.e. what one would iterate over to get the benefits of this sort of polymorphism). IIRC, some languages (like Haskell) make it difficult to have really heterogeneous collections. Is that correct? Can you please consider this in your answers? – Emblaze

Great question! I'm way too late to the party but seems to me you bumped into the classic Expression Problem: OOP allows for new data to be easily added, FP makes easier to add more functions. I'd suggest reading this article – Fidel

@Ashley you might find this answer useful. – Fidel

Thank you @dbaltor, two very interesting resources. Now, I know the name of the problem :-) BTW, I think I heard (or read) Martin Odersky say in line with the first reference, that one should use OO when needing to easily add subclasses/types without redefining all functions, and FP when you want to easily add new function without modifying the types (or something like that, wish I could find the original source). Rust Traits may bridge that distinction? – Emblaze

Hey @AshleyAitken, sorry! Hadn't seen your comment before. Didn't know about the Odersky's comment but you're spot on! That's what the Expression Problem is about. I have no idea on how FP and OO could be combined into something new that could address this issue though. However, the concept of Traits seems to belong entirely to the OO realm having nothing to do with FP. In Rust e.g, Traits carry the self reference. I'm not a Haskeller but they have seemingly come up with the concept of Existencial Types to construct heterogeneous colllections. – Fidel

Answer 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.

Kandrakandy

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 ;). – Kandrakandy

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 – Oaten

Answer 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.

Adalia

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? – Oaten

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. – Kare

@Oaten 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. – Adalia

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? – Adalia

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". – Kare

The problem with this is that you normally want to group all your logic related to Bar in one file, and all your logic related to Baz in another file. But now you're forced to group it all under the Show function handler. In a large application you'll have to go hunting all over your project to find what Bar can do, instead of looking in just one place like you can in OOP – Mordy

Answer 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"

Bargeboard

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..... – Oaten

@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. – Bargeboard

Answer 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."

Rosaceous

Answer 5

It's a common misconception that inheritance is the only form of polymorphism and that OOP languages are the only languages that can achieve polymorphism. That is incredibly misguided. There are many forms of polymorphism beyond subtype polymorphism.

In fact, there are many forms of subtype polymorphism beyond inheritance. Class based polymorphism is very limited even compared to other forms of subtype polymorphism (e.g. multimethods). Even languages like Inform 7 have more flexible subtype polymorphism than inheritance hierarchies.

It's probably more accurate to say that a common trait of OOP languages is poor support for polymorphism, rather than being the dominant polymorphic paradigm. It's incredibly common advice in OOP languages that inheritance should be avoided like the plague. Composition over inheritance is generally the recommendation.

Functional languages have support for composition at least as good as OOP languages and sometimes better. Every functional language has first class functions, whereas that's not necessarily a given in OOP languages. Functions are the most flexible data type to include in composition because they have more inhabitants than every other type. Even when OOP languages do have first class functions, sometimes the way they support first class functions involves clunky extra ceremony because depending on higher order functions is discouraged compared to wrapping everything in a class (e.g. Python).

Different functional languages have different blessed ways of achieving polymorphism that are way more flexible than fragile class hierarchies. Haskell and Scala have typeclasses. Common Lisp has multimethods. Clojure has protocols and multimethods. Rust has traits. (Technically Rust is neither functional nor object-oriented but a secret third thing.) I'm pretty sure there's similar stuff for the Erlang family and most ML languages, but I'm not familiar with those languages. (Would love if someone who knows would edit this post with those additions.) There are a few exceptions, such as in Elm.

If we want to name a common form of polymorphism that every functional language is guaranteed to have, then AFAIK the only examples would be what you said where higher order functions are passed as parameters or data types take in functions as properties. It's better than inheritance, but not by much. However, I think that's an impractical way of judging most of the functional languages you will come across. They usually implement a more robust form of polymorphism that is language-specific rather than paradigm-specific.

Bunt