What's the functional programming's answer for overriding?

Question

I'm fresh with both functional programming and F# coming from OOP & C# background and I've noticed that in functional programming methods are more often than not are static and in modules according to types (and I can understand why).

For instance, to work with list you can use functions found in the List module, to work with option there's the Option module, etc.

However what happens when I accept a parameter of a base class, and a derived class has a more suitable implementation for it?

In OOP the appropriate implementation would be called, which is the derived implementation, even though the object is statically of the base class, because the member has been overridden.

How would it be in functional programming?

If you have the base type as parameter (as you should), you could only work with functions for it, just like you can only call for the base's members in OOP.
Only difference is that in OOP the member called is the appropriate one.

Answer 1

The override scenario you describe, having a Base Class is tied to Subtype Polymorphism. In your case you can have a common interface, something like IEnumerable. This kind of Polymorphism is very common in OOP but not in FP which relays more on the other two types of Polymorphism: Ad-Hoc and Parametric.

An example of this would be Type Classes, in Haskell you can make a Function accept any parameter of type T as long that type T is an instance of a type class C, but your Function may be implemented in a generic way> Still you can 'override' that generic definition by adding a Function that works only on that specific instance T, when such function is called with that specific type the general implementation will be overridden, note this will be known at compile-time instead of compile-time.

A trivial example would be with Functors and Monads, the fmap function may be implemented in a generic way for any Monad in terms of functions bind and return, but you can add a specific implementation of fmap to list and/or option, more efficient than the generic one.

I'm not 100% sure but I think in C# you can have this kind of optimizations in Linq, since you can define more overloads for SelectMany which is the equivalent of bind.

Unfortunately in F# there is no such built-in mechanism, though there are some ways to encode this (see default methods in FsControl) but F# is not just Functional, it's multi-paradigm and lives in the .NET world (an OOP world) so you have override for SubTyping ready available.

Having said that, it worths mentioning this is more a technical view but in most cases not one-to-one with the override in OOP in terms of design, since this is more generic than SubTyping. I mean if you migrate your OOP design to FP and change a class hierarchy to let's say a Discriminated Union, your generic method would most likely end up in the catch-all-other-cases in a match (the one with the underscore | _ -> ) and the overrides in the specific cases.

UPDATE

Here is the answer to your question in the comments:

type MyType = 
    static member Nth (x:seq<_>) = fun n -> printfn "General case"; Seq.nth n x 
    static member Nth (x:_ [])   = fun n -> printfn "Override for []"; x.[n]

let bigSeq = seq {1..10000000}
let bigLst = [ 1..10000000 ]
let bigArr = [|1..10000000|]

MyType.Nth bigSeq 9000000
// General case
// Real: 00:00:00.217, CPU: 00:00:00.218, GC gen0: 0, gen1: 0, gen2: 0

MyType.Nth bigArr 9000000
// Override for []
// Real: 00:00:00.001, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0

MyType.Nth bigLst 9000000
// General case
// Real: 00:00:00.080, CPU: 00:00:00.078, GC gen0: 0, gen1: 0, gen2: 0

But without the override for []:

MyType.Nth bigArr 9000000
// General case
// Real: 00:00:00.052, CPU: 00:00:00.046, GC gen0: 0, gen1: 0, gen2: 0

That's how overriding works in ad-hoc polymorphism (overloading).

By using .NET overloading of methods you can override but you may argue that you can't go far as the overload is resolved at the call site so you can't define another generic function on top of that call.

Now let's suppose I have a Type Class Collection which represents all types that can be upcasted to seq, and a function nth if I had Type Classes in F# I would be able to write something like:

// General implementation relaying in IEnumerable<_>
let nth n (x:Collection<_>) = Seq.nth n

// Specific implementation for arrays
let nth n (x:_ []) = x.[n]

Unfortunately this will not compile since overloading in F# works just for methods, not functions, moreover there are no Type Classes in F# at the moment, but as I mentioned there are some workarounds, with FsControl I can write this which will actually compile and allow me to run the same tests.

Anyways having the same scenario, how would you code this in OOP, since you have no access to the source code of Seq and Array? With subtype polymorphism you will not be able to override anything in that case.

Answer 2

You would not necessarily model it in that way. Consider this; a discriminated union corresponds to a whole class hierarchy rather than just a class. As such any function you define on the discriminated union already corresponds to the method on the base class including all overrides. This is the case, because discriminated unions are closed for extension by data cases, but open for adding new functions.

Typically in OOP, classes are closed for adding functionality, but open for adding new data cases.

What more closely corresponds to an FP-style function on a discriminated union, is moke like the visitor pattern. And pattern matching is a (strictly) stronger version of the dynamic dispatch done in the visitor.

Also, in F# generics play a much larger role than in C# and so you usually do not have any information about the types in question, apart from the information, that logically follows from your code. For instance, you would very often not code in terms of the base class, but rather in terms of a generic type 'a.

Edit: About writing a function that returns the nth element. Again, you would usually either already know all the types of collections there are, e.g.

type 'a Collection =
    | Array of 'a array
    | List of 'a list
    | Seq of 'a seq

in this case you can always wrap the collection into one of the three cases and you can provide special implementations for the two cases you can do something meaningful with, e.g. List and Array whilst providing some default for the more simple case. I like to think of a DU as a definition by cases. And usually the branching logic fits this view of the world rather well. So I would write an nth function in such a way, that I take care of the cases, I can meaningfully do something about. And leave the cases I don't know anything about to a default.

In functional programming, you focus less on subtype polymorphism by inheritance (the typical OOP-style, "I do not know what concrete implementation there will be at run time"), but rather parametric polymorphism (i.e. generics) ad-hoc polymorphism (overloading).

Look at the following:

[1..10] |> List.sumBy (+)
[1.0..10.0] |> List.sumBy (+)

here, you use the same + function in both cases. Even though it is in fact a different type.

Whenever you notice that some piece of code is identical in two different places, there is a very good chance, that in FP, you can abstract over that piece of code and make your code more generic and reusable. So even though a function like say, List.map is just one concrete function, it can in fact be used in a very large amount of context and behave "polymorphically", by you supplying the specific behavior, i.e. a function, that is needed in that context.

The difference between OOP style polymorphism and those higher-order functions is, that you can just pass in your needed behaviour there, where you need it, as opposed to it being part of the class hierarchy.