18

Fair warning, I'm new to functional programming so I may hold many bad assumptions.

I've been learning about algebraic types. Many functional languages seem to have them, and they are fairly useful in conjunction with pattern matching. However, what problem do they actually solve? I can implement a seemingly (sort-of) algebraic type in C# like this:

public abstract class Option { }
public class None : Option { }
public class Some<T> : Option
{
    public T Value { get; set; }
}

var result = GetSomeValue();
if(result is None)
{
}
else
{
}

But I think most would agree this is a bastardization of object oriented programming, and you shouldn't ever do it. So does functional programming just add a cleaner syntax that makes this style of programming seem less gross? What else am I missing?

|improve this question
  • 6
    Functional programming is a different paradigm than object oriented programming. – Basile Starynkevitch Jun 21 '15 at 18:03
  • @BasileStarynkevitch I realize, but there are languages like F# that are a little of both. The question is not so much about functional languages, but more about what problem algebraic data types solve. – ConditionRacer Jun 21 '15 at 18:04
  • 7
    What happens when I define class ThirdOption : Option{} and give you a new ThirdOption() where you expected Some or None? – amon Jun 21 '15 at 18:09
  • 1
    @amon languages that have sum types generally have ways of disallowing it. For example, Haskell defines data Maybe a = Just a | Nothing (equivalent to data Option a = Some a | None in your example): you can't add a third case post-hoc. While you can sort of emulate sum types in C# in the way you've shown, it's not the prettiest. – Martijn Jun 22 '15 at 9:47
  • 1
    I think it's less "what problem do ADTs solve" and more like "ADTs are a different way of approaching things". – MathematicalOrchid Jun 22 '15 at 14:30
44

Classes with interfaces and inheritance present an open world: Anyone can add a new kind of data. For a given interface, there may be classes implementing it all over the world, in different files, in different projects, at different companies. They make it easy to add cases to the data structures, but because the implementations of the interface are decentralized, it is hard to add a new method to the interface. Once an interface is public, it is basically frozen. Nobody knows all the possible implementations.

Algebraic data types are the dual to that, they are closed. All the cases of the data are listed in one place and operations not only can list the variants exhaustively, they are encouraged to do so. Consequently writing a new function operating on an algebraic data type is trivial: Just write the damn function. In return, adding new cases is complicated because you need to go over basically the entire code base and extend every match. Similar to the situation with interfaces, in the Rust standard library, adding a new variant is a breaking change (for public types).

These are two sides of the expression problem. Algebraic data types are an incomplete solution to them, but so is OOP. Both have advantages depending on how many cases of data there are, how often those cases change, and how frequently the operations are extended or changed. (Which is why many modern languages provide both, or something similar, or go straight for more powerful and more complicated mechanisms that try to subsume both approaches.)

|improve this answer
  • Do you get a compiler error if you fail to update a match, or is it only at run time you find out? – Ian Jun 22 '15 at 8:17
  • 6
    @Ian Most functional languages are statically typed and check exhaustiveness of pattern matching. However, if there is a "catch all" pattern, the compiler is happy even if the function would have to deal with the new case to do its job. In addition, you have to recompile all dependent code, you can't compile just one library and re-link it into an already-built application. – user7043 Jun 22 '15 at 8:43
  • Also, statically checking that a pattern is exhaustive is expensive in general. It solves the SAT problem at best and at worst the language allows for arbitrary predicates which makes this undecidable. – usr Jun 27 '15 at 9:55
  • @usr No language I'm aware of attempts a perfect solution, either the compiler understands that it's exhaustive or you're forced to add a catch-all case where you crash and burn. I don't know of a relation to SAT though, do you have a link to a reduction? Regardless, for actual code written in real programs, exhaustiveness checking is a drop in the bucket. – user7043 Jun 27 '15 at 10:09
  • Imagine you are matching on N booleans. Then you add match clauses like (a, b, _, d, ...). The catch-all case is then !clause1 && !clause2 && .... That looks like SAT to me. – usr Jun 27 '15 at 10:22
12

So does functional programming just add a cleaner syntax that makes this style of programming seem less gross?

That is a simplification perhaps, but yes.

What else am I missing?

Let's be clear on what algebraic data types are (summarizing this fine link from Learn you as Haskell):

  • A sum type that says "this value can be an A or a B".
  • A product type that says "this value is both an A and a B".

your example only really works with the first.

What you're perhaps missing is that by providing these two basic operations, functional languages let you build everything else. C# has structs, classes, enums, generics on top of those, and piles of rules to govern how these things behave.

Combined with some syntax to help, the functional languages can decompose operations down to these two paths, providing a clean, simple and elegant approach to types.

What problem do algebraic data types solve?

They solve the same problem as any other type system: "what values are legal to use here?" - they just take a different approach to it.

|improve this answer
  • 4
    Your last sentence is kind of like telling someone that "ships solve the same problem as airplanes: transportation -- they just take a different approach to it". It's a completely correct statement, and also a pretty useless one. – Mehrdad Jun 22 '15 at 7:27
  • @mehrdad - I think that's overstating it a little bit. – Telastyn Jun 22 '15 at 11:21
  • 1
    No doubt you understand algebraic data types just fine, but your bulleted list ("A sum type is..." and "A product type is...") looks more like a description of union and intersection types, which aren't quite the same thing as sum and product types. – pyon Jul 23 '15 at 16:29
6

It may surprise you to learn that pattern matching is not considered the most idiomatic way to work with Options. See the documentation of Scala's Options for more about that. I'm not sure why so many FP tutorials encourage this usage.

Mostly what you're missing is there are a whole bunch of functions created to make working with Options easier. Consider the main example from the Scala docs:

val name: Option[String] = request getParameter "name"
val upper = name map { _.trim } filter { _.length != 0 } map { _.toUpperCase }
println(upper getOrElse "")

Notice how map and filter let you chain operations on Options, without having to check at each point whether you have None or not. Then at the end, you use getOrElse to specify a default value. At no point are you doing something "gross" like checking types. Any unavoidable type checking is done internal to the library. Haskell has its own set of analagous functions, not to mention the large set of functions that will work on any monad or functor.

Other algebraic data types have their own idiomatic ways to work with them, and pattern matching is low on the totem pole in most cases. Likewise, when you create your own types, you're expected to provide similar functions to work with them.

|improve this answer

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.