extension techniques in functional programming such as F#

Question

In object oriented programming inheritance and virtual methods are the common scenario for creating extensible code. In more complex settings factory methods (or dependency frameworks) help extending the base code.

What are the common approaches in functional programming (eg F#) to create extensible code?

Answer 1

Fantastic question!

Here is an answer derived from this blog article:

The functional paradigm (meaning the use of higher-order functions) only provides a single form of extensibility: higher-order functions. These allow you to factor out "inner" functions. For example, code that often appears with the same first and last code blocks:

let f x =
  first x
  stuff1 x
  last x

let g x =
  first x
  stuff2 x
  last x

can be factored into a general higher order function that is reused from the specific cases:

let hof stuff x =
  first x
  stuff x
  last x

let f = hof stuff1 x

let g = hof stuff2 x

Applying this aggressively leads to design patterns such as parser combinators and is a very powerful and lightweight technique for making code extensible. However, it does not make data types extensible.

But real functional programming languages almost always include funkier language features to help with extensibility:

• Common Lisp has the Common Lisp Object System (CLOS) and a macro system.
• Standard ML has parametric polymorphism and a higher-order module system.
• OCaml added polymorphic variants, objects, optional arguments and the Camlp4 macro system.
• Haskell has parametric polymorphism and type classes, and Template Haskell adds macros.
• Scala has Java-style OOP with some added features.

Read Chris Okasaki's excellent monograph Purely functional data structures for some great examples using higher-order modules in Standard ML and type classes in Haskell. Read Code reuse through polymorphic variants by Jacques Garrigue for a description of how that language feature can be used to attack the expression problem. However, these solutions are quite rare in the wild and, in particular, you can get a long way without them (e.g. in F#).

Historically, this diversity appeared because most functional programming languages were research projects and, consequently, they existed to add novel features. Therefore, we now have a wide variety of disparate forms of extensibility in today's functional programming languages.

F# is a different beast because its design requirements were seamless interoperability with the rest of .NET (which imposes .NET-style OOP) and pragmatism. Consequently, F# keeps the ML core with parametric polymorphism and adds .NET's object system. So you can benefit from the easy extensibility offered by generic higher-order functions and conventional OOP but not from any of the more esoteric features like higher-order modules, type classes and macros.

The only form of extensibility F# has pioneered is active patterns. These allow you to separate code that destructures via pattern matching from the concrete data representation. This is an important way to decouple code from data and, therefore, make it more reusable.

Answer 2

The basic extension technique in functional programming are

• Writing higher-order functions (functions that take other functions as parameters)
• (Functional) polymorphism (using functions and types parameterized by type - in the C# terminology, generic types and methods).

For example, instead of using abstract method (that modifies some state of the object), you'd probably pass a function as an argument. The function would take all necessary state to do the calculation (done by abstract method in OO) and it would return new state (or whatever the result of the calculation is).

Generic (polymorphic) code such as list<T> is another example of extension technique. You have some data structure and functions working with it (e.g. List.map) and you can use it together with previously unknown types (type of list item) and specify behaviors specific for this type (e.g. filtering predicate). Lists are quite basic example, but it works for non-collection types as well.

In a more complex settings, there are larger differences between programming languages

• In Haskell, people probably use type-classes (which are a bit like more powerful interfaces)
• In OCaml people use functors (similar to classic functional polymorphism, but you can parameterize by multiple functions and types as well).
• In F#, I think, people usually mix standard .NET techniques (such as interfaces) with basic functional techniques (higher order functions, passing functions as argument to object constructor etc).

This mix of FP and OO is quite a powerful combination, so you probably don't need more complicated things like dependency frameworks.