10

This past year I took the leap and learned a functional programming language (F#) and one of the more interesting things that I've found is how it affects the way I design OO software. The two things I find myself missing most in OO languages are pattern matching and sum types. Everywhere I look I see situations that would be trivially modeled with a discriminated union, but I am reluctant to crowbar in some OO DU implementation that feels unnatural to the paradigm.

This generally leads me to create intermediate types to handle the or relationships that a sum type would handle for me. It also seems to lead to a good deal of branching. If I read people like Misko Hevery, he suggests that good OO design can minimize branching through polymorphism.

One of the things I avoid as much as possible in OO code is types with null values. Obviously the or relationship can be modeled by a type with one null value and one non-null value, but this means null tests everywhere. Is there a way to model heterogeneous but logically associated types polymorphically? Design strategies or patterns would be very helpful, or simply ways to think about heterogeneous and associated types generally in the OO paradigm.

  • 3
    "good OO design can minimize branching through polymorphism" sort of: it moves branching from the actual business logic to the initialization/configuration code. The benefit usually is that "initialization and configuration" happens much less (as of occurences in the code, not in terms of "execution") than an explicit branching in the business logic would be needed. The downside is that there is no room for or depending on the target objects type within the business logic... – Timothy Truckle Mar 12 '18 at 10:54
  • 3
    This may be of interest to you (basically, the author models a sum type as a hierarchy, with a bunch of overridden methods in the subclasses as a way to model pattern matching); also, in OO null checks can be avoided using the Null Object Pattern (just an object that does nothing for a given polymorphic operation). – Filip Milovanović Mar 12 '18 at 11:03
  • The composite pattern might be worth a read. – candied_orange Mar 12 '18 at 11:13
  • 1
    Can you give an example of the kind of thing you want to improve? – JimmyJames Mar 12 '18 at 15:58
  • @TimothyTruckle Good explanation, but it is not always "initialization/configuration". The branching occurs when you invoke the method, invisibly, but a dynamic language might allow you to add classes dynamically, in which case the branching is also changing dynamically. – Frank Hileman Mar 15 '18 at 1:41
15

Like you, I wish that discriminated unions were more prevalent; however, the reason they are useful in most functional languages is that they provide exhaustive pattern matching, and without this, they are just pretty syntax: not just pattern matching: exhaustive pattern matching, so that the code doesn't compile if you don't cover every possibility: this is what gives you power.

The only way to do anything useful with a sum type is to decompose it, and branch depending on which type it is (e.g. by pattern matching). The great thing about interfaces is that you don't care what type something is, because you know you can treat it like an iface: no unique logic needed for each type: no branching.

This isn't a "functional code has more branching, OO code has less", this is a "'functional languages' are better suited to domains where you have unions - which mandate branching - and 'OO languages' are better suited to code where you can expose common behaviour as a common interface - which might feel like it does less branching". The branching is a function of your design and the domain. Quite simply, if your "heterogeneous but logically associated types" can't expose a common interface, then you have to branch/pattern-match over them. This is a domain/design problem.

What Misko may be referring to is the general idea that if you can expose your types as a common interface, then using OO features (interfaces/polymorphism) will make your life better by putting type-specific behaviour in the type rather than in the consuming code.

It is important to recognise that interfaces and unions are kind of the opposite of each other: an interface defines some stuff the type has to implement, and the union defines some stuff the consumer has to consider. If you add a method to an interface, you have changed that contract, and now every type that previously implemented it needs to be updated. If you add a new type to a union, you have changed that contract, and now every exhaustive pattern matching over the union has to be updated. They fill different roles, and while it may sometimes be possible to implement a system 'either way', which you go with is a design decision: neither is inherently better.

One benefit of going with interfaces/polymorphism is that the consuming code is more extensible: you can pass in a type that wasn't defined at design time, so long as it exposes the agreed interface. On the flip side, with a static union, you can exploit behaviours that weren't considered at design time by writing new exhaustive pattern-matchings, so long as they stick to the contract of the union.


Regarding the 'Null Object Pattern': this isn't not a silver bullet, and does not replace null checks. All it does it provide a way to avoid some 'null' checks where the 'null' behaviour can be exposed behind a common interface. If you can't expose the 'null' behaviour behind the type's interface, then you will be thinking "I really wish I could exhaustively pattern match this" and will end up performing a 'branching' check.

|improve this answer|||||
  • 4
    related to the penultimate paragraph: en.wikipedia.org/wiki/Expression_problem – jk. Mar 12 '18 at 17:44
  • "an interface defines some stuff the type has to implement, and the union defines some stuff the consumer has to consider" - you don't have to look at interfaces that way. A component can define a required interface - what some other component has to implement; and a provided interface - one that a consumer component has to consider (i.e., be programmed against). – Filip Milovanović Mar 12 '18 at 17:55
  • @FilipMilovanović aye, I've not been very precise there. I was trying to avoid getting into the 'triangle' of dependencies with interfaces (consumer -> interface <- implementer/type) rather than the 'linear' dependencies with a union (consumer -> union -> types), because I'm really only trying to express where the 'decision' making is going on (e.g. where do we define what to do if we are presented with this type) – VisualMelon Mar 12 '18 at 18:06
3

There's a fairly "standard" way of encoding sum types into an object-oriented language.

Here's two examples:

type Either<'a, 'b> = Left of 'a | Right of 'b

In C#, we could render this as:

interface Either<A, B> {
    C Match<C>(Func<A, C> left, Func<B, C> right);
}

class Left<A, B> : Either<A, B> {
    private readonly A a;
    public Left(A a) { this.a = a; }
    public C Match<C>(Func<A, C> left, Func<B, C> right) {
        return left(a);
    }
}

class Right<A, B> : Either<A, B> {
    private readonly B b;
    public Right(B b) { this.b = b; }
    public C Match<C>(Func<A, C> left, Func<B, C> right) {
        return right(b);
    }
}

F# again:

type List<'a> = Nil | Cons of 'a * List<'a>

C# again:

interface List<A> {
    B Match<B>(B nil, Func<A, List<A>, B> cons);
}

class Nil<A> : List<A> {
    public Nil() {}
    public B Match<B>(B nil, Func<A, List<A>, B> cons) {
        return nil;
    }
}

class Cons<A> : List<A> {
    private readonly A head;
    private readonly List<A> tail;
    public Cons(A head, List<A> tail) {
        this.head = head;
        this.tail = tail;
    }
    public B Match<B>(B nil, Func<A, List<A>, B> cons) {
        return cons(head, tail);
    }
}

The encoding is completely mechanical. This encoding produces a result that has most of the same advantages and disadvantages of algebraic data types. You may also recognize this as a variation of the Visitor Pattern. We could collect the parameters to Match together into an interface that we could call a Visitor.

On the advantages side, this gives you a principled encoding of sum types. (It's the Scott encoding.) It gives you exhaustive "pattern matching" though only one "layer" of matching at a time. Match is in some ways a "complete" interface for these types and any additional operations we may want can be defined in terms of it. It presents a different perspective on many OO patterns such as the Null Object Pattern and State Pattern as I indicated on Ryathal's answer, as well as the Visitor Pattern and the Composite Pattern. The Option/Maybe type is like a generic Null Object Pattern. The Composite Pattern is akin to encoding type Tree<'a> = Leaf of 'a | Children of List<Tree<'a>>. The State Pattern is basically an encoding of an enumeration.

On the disadvantages side, as I wrote it the Match method puts some constraints on what subclasses can meaningfully be added, especially if we want to maintain the Liskov Substitutability Property. For example, applying this encoding to an enumeration type would not allow you to meaningfully extend the enumeration. If you did want to extend the enumeration, you would have to change all callers and implementors everywhere just as if you were using enum and switch. That said, this encoding is somewhat more flexible than the original. For example, we can add an Append implementor of List that just holds two lists giving us constant-time append. This would behave like the lists appended together but would be represented in a different manner.

Of course, many of these problems have to do with the fact that Match is somewhat (conceptually but intentionally) tied to the subclasses. If we use methods that aren't so specific, we get more traditional OO designs and we regain the extensibility, but we lose the "completeness" of the interface and thus we lose the ability to define any operation on this type in terms of the interface. As mentioned elsewhere, this is a manifestation of the Expression Problem.

Arguably, designs like the above can be used systematically to completely eliminate the need for branching ever achieving an OO ideal. Smalltalk, for example, uses this pattern often including for Booleans themselves. But as the preceding discussion suggests, this "elimination of branching" is fairly illusory. We've just implemented branching in a different manner, and it still has much of the same properties.

|improve this answer|||||
1

Handling null can be done with the null object pattern. The idea is to create an instance of your objects that returns default values for every member and has methods that don't do anything, but also don't error out. This doesn't eliminate null checks entirely, but it means you only need to check for nulls at object creation and return your null object.

The state pattern is a way to minimize branching and give some of the benefits of pattern matching. Again it pushes the branching logic to object creation. Each state is a separate implementation of a base interface, so all consuming code just needs to call DoStuff() and the proper method is called. Some languages are also adding pattern matching as a feature, C# is one example.

|improve this answer|||||
  • (Un?)Ironically, these are both examples of the "standard" way of encoding discriminated union types into OOP. – Derek Elkins left SE Mar 12 '18 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.