How to use polymorphism in functional programming?

问题:

How to use polymorphism in functional programming (with dynamic type system)?

Let's consider following example (first in OOP second in FP). The program is very simple - there are list of figures and we need to draw all of them, different figures use different drawing algorithms.

In OOP it can be done trivially, but how to do it in FP? Especially in languages with dynamic type system, like Scheme, Clojure (without static type resolving at compile time)?

I created simple code ( live version http://tinkerbin.com/0C3y8D9Z , press 'Run' button ). I used if/else switch in FP sample, but it's a very bad approach. How such problem can be solved better?

Samples are in JavaScript, but it's only for purpose of simplicity, it would be interesting to see a solution in any functional language with dynamic typing system.

OOP

var print = function(message){document.write(message + "\n<br/>")}

// Object Oriented Approach.
var circle = {
  draw: function(){print("drawing circle ...")}
}
var rectangle = {
  draw: function(){print("drawing rectangle ...")}
}

var objects = [circle, rectangle]
objects.forEach(function(o){
  o.draw()
})

FP

var print = function(message){document.write(message + "\n<br/>")}

// Functional Approach.
var circle = {type: 'Circle'}
var drawCircle = function(){print("drawing circle ...")}

var rectangle = {type: 'Rectangle'}
var drawRectangle = function(){print("drawing rectangle ...")}

var objects = [circle, rectangle]
objects.forEach(function(o){
  if(o.type == 'Circle') drawCircle(o)
  else if(o.type == 'Rectangle') drawRectangle(o)
  else throw new Error('unknown type!')
})

回答1:

OO polymorphism is not a part of functional programming. However some functional languages (e.g. clojure) have oo polymorphism.

Another kind of polymorphism is multimethods

(def circle {:type :circle
             :radius 50})

(def rectangle {:type :rectangle
                :width 5
                :height 10})

(defmulti draw :type)

(defmethod draw :circle [object]
  (println "circle: radius = " (:radius object)))

(defmethod draw :rectangle [object]
  (println "rectangle: "
           "width = " (:width object)
           "height = " (:height object)))

(doseq [o [rectangle circle]] (draw o))
=> rectangle:  width =  5 height =  10
   circle: radius =  50

Or you just can use functional style

(defn circle [] (println "drawing circle ..."))
(defn rectangle [] (println "drawing rectangle ..."))

(def objects [circle rectangle])

(doseq [o objects] (o))
=> drawing circle ...
   drawing rectangle ...

回答2:

Your "FP" version is not what I consider the idiomatic FP example. In FP, you often use variants and pattern matching where in OOP you'd use classes and method dispatch. In particular, you only have one draw function that already does the dispatch internally:

var circle = {type: 'Circle'}
var rectangle = {type: 'Rectangle'}

var draw = function(shape) {
  switch (shape.type) {
    case 'Circle': print("drawing circle ..."); break
    case 'Rectangle': print("drawing rectangle ..."); break
  }
}

var objects = [circle, rectangle]
objects.forEach(draw)

(Of course, that is JavaScript. In a functional language you typically have much more elegant and concise syntax for this, e.g.:

draw `Circle    = print "drawing circle..."
draw `Rectangle = print "drawing rectangle..."

objects = [`Circle, `Rectangle]
foreach draw objects

)

Now, the average OO aficionado will see the above code and say: "But the OO solution is extensible, the above is not!" That's true in the sense that you can easily add new shapes to the OO version and don't have to touch any of the existing ones (or their draw functions) when you do. With the FP way, you'd have to go in and extend the draw function, and all other operations that may exist.

But what those people fail to see is that the converse is also true: the FP solution is extensible in a way the OO one isn't! Namely, when you add a new operation over your existing shapes then you don't need to touch any of the shape definitions, nor existing operations. You simply add another function, whereas with OO, you have to go and modify every class or constructor to include an implementation for the new operation.

That is, there is a dualism here in terms of modularity. The ideal, achieving simultaneous extensibility along both axes is known in literature as "the expression problem", and while various solutions exist (especially in functional languages), they are typically more complex. Hence, in practice you'll often want to decide for one dimension, depending on which dimension is more likely to matter for the problem at hand.

There are other advantages to the functional version. E.g it trivially scales to multi-dispatch or more complex case distinctions. It also is preferable when implementing an algorithm that is complicated and where the different cases are interrelated, so that you want to have the code in one place. As a rule of thumb, whenever you start using the visitor pattern in OO, a functional-style solution would have been more appropriate (and far, far easier).

Some further remarks:

• This different preference in program organisation isn't the central idea of FP. What matters more is discouraging mutable state, and encouraging highly reusable higher-order abstractions.

• The OO community has this habit of inventing new (buzz)words for every old idea. Its use of the term "polymorphism" (which is completely different from what it means elsewhere) is one such example. It says little more than being able to call functions without statically knowing what the callee is. You can do that in any language where functions are first-class values. In that sense, your OO solution is perfectly functional as well.

• Your question has very little to do with types. Both the idiomatic OO and the idiomatic FP solution work in an untyped or typed language.

回答3:

In Clojure there are Protocols which provide basically the same ad-hoc polymorphism as Haskell's type classes:

(defprotocol shape (draw [e]))
(defrecord circle [radius])
(defrecord rectangle [w h])
(extend-protocol shape 
    circle (draw [_] "I am a nice circle")
    rectangle (draw [_] "Can I haz cornerz please?"))

You can also extend an existing type:

(extend-protocol shape 
   String (draw [_] "I am not a shape, but who cares?"))

And then you can apply the draw method to some instances

user=> (map draw [(->circle 1) (->rectangle 4 2) "foo"])
("I am a nice circle" "Can I haz cornerz please?" "I am not a shape, but who cares?")

回答4:

There really isn't anything non-functional about your first code sample. Even in languages that have no support for object orientation, you can do the same thing. That is you can create a record/structure/map that contains functions and then put those into your list.

In your simple example where there's only one function, you could also just create a list of functions directly, like objects = [drawCircle, drawRectangle].

回答5:

In several languages designed primarily for functional programming, there are ways to achieve (ad-hoc, as it is called) polymorphism, though they differ from what you call polymorphism. Haskell, for example, has type classes (not to be confused with classes from classical OOP):

class Draw a where
    draw :: a -> SomethingSomthing -- probably IO () for your example, btw

(Scala has objects, and also implicits which apparently parallel or even surpass type classes.) You can then implement any number of independent types, and make each an instance of the type class (again independently, e.g. in an entirely different module):

data Circle = Circle Point Double -- center, radius
data Rectangle = Rect Point Double Double -- center, height, width

instance Draw Circle where
    draw (Circle center radius) = …
instance Draw Rectangle where
    draw (Rect center height width) = …

This is probably what you'd use in Haskell, if you actually needed that degree of extensibility. If you have a finite number of cases belonging together (i.e. you could use sealed classes in the OOP alternative), you'd likely use algebraic data types (see below).

Another way is to do just what your JS snippet does (which is, by the way, not what you'd do to achieve polymorphism if you had any number of objects of each type, and this version has the same problem): Embed a function that does the polymorphic behavior in each object. In a sense, your "OOP" snippet is already functional.

data Drawable = Drawable (Drawable -> SomethingSomething) {- other fields -}
draw (Drawable draw) = draw Drawable

Though in a static language, this does not permit different objects to have different attributes.

A more bearable alternative to the bunch of conditions you present, but nevertheless similar and with the same limitation (it's hard to add another shape), is pattern matching with algebraic data types. Other answers on Stackoverflow have explained these well, I'll just give this concrete example in that style:

data Shape = Circle {- see second snippet -}
           | Rect {- ditto -}

draw (Circle center radius) = …
draw (Rect center height width) = …