Say you have this in an Object-Oriented application:
module Talker
def talk(word)
puts word
end
end
module Swimmer
def swim(distance)
puts "swimming #{distance}"
end
end
class Organism
def initialize
rise
end
def rise
puts "hello world"
end
end
class Animal extends Organism
def think(something)
puts "think #{something}"
end
end
class Bird extends Animal
include Talker
end
class Fish extends Animal
include Swimmer
end
bird = new Bird
fish = new Fish
In this, you can call methods which are unique to each:
bird.talk("hello")
fish.swim(50)
But you can also call methods which are the same:
bird.think("fly")
fish.think("swim")
If I have a function that takes an animal, I can call the think function:
def experience(animal)
animal.think("one")
animal.think("two")
animal.think("one")
end
In a pseudo functional language, you can do the same basically:
function experience(animal) {
think(animal)
think(animal)
think(animal)
}
But not really, you would have to check the type:
function think(genericObject) {
if (genericObject is Animal) {
animalThink(genericObject)
} else if (genericObject is SomethingElse) {
somethingElseThink(genericObject)
}
}
That is because, when implementing your "experience" function, you don't want just animals to experience, you want rocks and trees and other things to experience too, but their experience functions are different.
function experience(thing) {
move(thing)
move(thing)
move(thing)
}
function move(thing) {
case thing {
match Animal then animalMove(thing)
match Plant then plantMove(thing)
match Rock then rockMove(thing)
}
}
In this way, you can't have a cleanly reusable function, your function must know of the specific types it's going to receive somewhere down the line.
Is there any way to avoid this and make it more like OO polymorphism, in a functional language?
If so, at a high level, how does it work under the hood if this can be solved in a functional language?
Functional programming languages have a variety of ways of achieving polymorphism. I'm going to contrast Java (the OOP language I know best) with Haskell (the functional language I know best).
Way 1: "parametric polymorphism"
With parametric polymorphism, you don't need to know anything at all about the underlying type. For example, if I have a singly-linked list with elements of type T, I actually don't need to know anything about type T in order to find the length of the list. I would just write something like
length :: forall a . [a] -> Integer
length [] = 0
length (x:xs) = 1 + length xs
in Haskell (obviously I'd want to use a better algorithm in practice, but you get the idea). Note that it doesn't matter what the type of the list elements is; the code for getting the length is the same. The first line is the "type signature". It says that for every type a, length will take a list of a and output an integer.
This can't be used for too much "serious polymorphism", but it's definitely a strong start. It corresponds roughly to Java's generics.
Way 2: typeclass-style polymorphism
Even something as benign as checking for equality actually requires polymorphism. Different types require different code for checking equality, and for some types (generally functions), checking equality is literally impossible because of the halting problem. Thus, we use "type classes".
Let's say I define a new type with 2 elements, Bob and Larry. In Haskell, this looks like
data VeggieTalesStars = Bob | Larry
I would like to be able to compare two elements of type VeggieTalesStars for equality. To do this, I would need to implement an Eq instance.
instance Eq VeggieTalesStars where
Bob == Bob = True
Larry == Larry = True
Bob == Larry = False
Larry == Bob = False
Note that the function (==) has the type signature
(==) :: forall b . Eq b => b -> b -> Bool
This means that for every type b, if b has an Eq instance, then (==) can take two arguments of type b and return a Bool.
It's probably not too difficult for you to guess that the not-equals function (/=) also has the type signature
(/=) :: forall b . Eq b => b -> b -> Bool
Because (/=) is defined by
x /= y = not (x == y)
When we call the (/=) function, the function will deploy the correct version of the (==) function based on the types of the arguments. If the arguments have different types, you won't be able to compare them using (/=).
Typeclass-style polymorphism allows you to do the following:
class Animal b where
think :: b -> String -> String
-- we provide the default implementation
think b string = "think " ++ string
data Fish = Fish
data Bird = Bird
instance Animal Fish where
instance Animal Bird where
Both Fish and Bird implement the "Animal" typeclass, so we can call the think function on both. That is,
>>> think Bird "thought"
"think thought"
>>> think Fish "thought"
"think thought"
This use case corresponds roughly to Java interfaces - types can implement as many type classes as they want. But type classes are far more powerful than interfaces.
Way 3: Functions
If your object only has one method, it may as well just be a function. This is a very common way to avoid inheritance hierarchies - deal with functions rather than inheritors of a 1-method base class.
One might therefore define
type Animal = String -> String
basicAnimal :: Animal
basicAnimal thought = "think " ++ thought
An "animal" is really just a way of taking one string and producing another. This would correspond to the Java code
class Animal {
public String think(String thought) {
return "think " + thought;
}
}
Let's say that in Java, we decided to implement a subclass of animal as follows:
class ThoughtfulPerson extends Animal {
private final String thought;
public ThoughtfulPerson(final String thought) {
this.thought = thought;
}
@Override
public String think(String thought) {
System.out.println("I normally think " + this.thought ", but I'm currently thinking" + thought + ".");
}
}
In Haskell, we would implement this as
thoughtfulPerson :: String -> Animal
thoughtfulPerson originalThought newThought = "I normally think " ++ originalThought ", but I'm currently thinking" ++ newThought ++ "."
The "dependency injection" of Java code is realised by Haskell's higher-order functions.
Way 4: composition over inheritance + functions
Suppose we have an abstract base class Thing with two methods:
abstract class Thing {
public abstract String name();
public abstract void makeLightBlink(int duration);
}
I'm using Java-style syntax, but hopefully it's not too confusing.
Fundamentally, the only way to use this abstract base class is by calling its two methods. Therefore, a Thing should actually be considered to be an ordered pair consisting of a string and a function.
In a functional language like Haskell, we would write
data Thing = Thing { name :: String, makeLightsBlink :: Int -> IO () }
In other words, a "Thing" consists of two parts: a name, which is a string, and a function makeLightsBlink, which takes an Int and outputs an "IO action". This is Haskell's way of dealing with IO - through the type system.
Instead of defining subclasses of Thing, Haskell would just have you define functions which output a Thing (or define Things themselves directly). So if in Java you might define
class ConcreteThing extends Thing {
@Override
public String name() {
return "ConcreteThing";
}
@Override
public void makeLightsBlink(int duration) {
for (int i = 0; i < duration; i++) {
System.out.println("Lights are blinking!");
}
}
}
In Haskell, you would instead define
concreteThing :: Thing
concreteThing = Thing { name = "ConcreteThing", makeLightsBlink = blinkFunction } where
blinkFunction duration = for_ [1..duration] . const $ putStrLn "Lights are blinking!"
No need to do anything fancy. You can implement any behaviour you want by using composition and functions.
Way 5 - avoid polymorphism entirely
This corresponds to the "open vs closed principle" in object oriented programming.
Some times, the correct thing to do is actually to avoid polymorphism entirely. For example, consider how one might implement a singly-linked list in Java.
abstract class List<T> {
public abstract bool is_empty();
public abstract T head();
public abstract List<T> tail();
public int length() {
return empty() ? 0 : 1 + tail().length();
}
}
class EmptyList<T> {
@Override
public bool is_empty() {
return true;
}
@Override
public T head() {
throw new IllegalArgumentException("can't take head of empty list");
}
@Override
public List<T> tail() {
throw new IllegalArgumentException("can't take tail of empty list");
}
}
class NonEmptyList<T> {
private final T head;
private final List<T> tail;
public NonEmptyList(T head, List<T> tail) {
this.head = head;
this.tail = tail;
}
@Override
public bool is_empty() {
return false;
}
@Override
public T head() {
return self.head;
}
@Override
public List<T> tail() {
return self.tail;
}
}
However, this is actually not a good model because you'd like there to only be two ways of constructing a list - the empty way, and the non-empty way. Haskell allows you to do this quite simply. The analogous Haskell code is
data List t = EmptyList | NonEmptyList t (List t)
empty :: List t -> Bool
empty EmptyList = True
empty (NonEmptyList t listT) = False
head :: List t -> t
head EmptyList = error "can't take head of empty list"
head (NonEmptyList t listT) = t
tail :: List t -> List t
tail EmptyList = error "can't take tail of empty list"
tail (NonEmptyList t listT) = listT
length list = if empty list then 0 else 1 + length (tail list)
Of course, in Haskell we try to avoid functions that are "partial" - we try to make sure that every function always returns a value. So you won't see many Haskellers actually using the "head" and "tail" functions for precisely this reason - they sometimes error out. You'd instead see length defined by
length EmptyList = 0
length (NonEmptyList t listT) = 1 + length listT
using pattern-matching.
This feature of functional programming languages is called "algebraic data types". It's incredibly useful.
Hopefully, I've convinced you that not only does functional programming allow you to implement many object-oriented design patterns, it can actually allow you to express the same ideas in much more succinct and obvious forms.