I’ve been using F# a little at work, so I’ve been thinking about the language again. F# seems to be to be part of a new wave of Big Languages, which fell out of favour after the Reign of C++ Then Perl in the 90s. Because of its serious dedication to functional and object-oriented styles, there are a lot of very similar ways to express data structures.

Let’s count them:

1. tuple
2. record
3. discriminated union
4. struct
5. module
6. closure
7. class

These concepts mostly increase in the amount of power they provide, and I think of each as being intended for a distinct use. This language design approach contrasts strongly with small languages like Java and Scheme. Java just gives you the most powerful construct and lets you sort it all out with heaps of design patterns. Scheme does the same with pairs and closures, except it also has macros to make the heaps of code disappear. I’m not sure which approach is best in practise—I don’t think anybody else does either, which is why there is a pendulum effect in the history of computer languages.

Originally I had a compact list here, but it’s really too compact to explain this fully. I’m going to need a paragraph for each structure and a table comparing them at least. I’ll start with the paragraphs and see how far I get. This may take more than one post.

tuple

(0, 'a', "foo") : int * char * string

A tuple is a small collection of items. It’s useful when you need to temporarily group two or three things. The canonical use for tuples is returning multiple values. They are also usually the most convenient, since you can pattern match tuples. For example, List.partition returns a 2-tuple (a pair) of items. The first is the ones that satisfy the predicate, the second is the ones that fail it:

> List.partition ((>) 3) [1 .. 5];;
([1;2], [3;4;5])

When prototyping, tuples are the first step in complexity of encapsulation. I frequently give tuples a type abbreviation even though this doesn’t provide any compiler safety. Later, when you give your data more structure, your type annotations will already be correct. Just say type Synonym = int * string.

You can store refs in a tuple, but the fields themselves cannot be made mutable like the other data structures. There isn’t any inheritance, either: in the type system, (1,1) is completely separate from (1,1,1) and from (’a', 1). You also don’t get any way to associate code with a tuple—you can’t add methods. Pattern-matching a tuple is basically the only way to get the information out.

record

type Point = { x : int; y : int}
{ x = 12; y = 12 }

Records are the next step up from tuples. You get names for your fields and the ability to declare them mutable. Records are perfect for little bags of information that need to be passed around between related functions. And since the fields can be mutable, they can be little bags of state if necessary. If this sounds kind of redundant with object oriented structures like classes and structs, you’re right. Records are a classic ML structure imported into the .NET world from OCaml.

Records can have methods in F#, but this does not fit well with their intended use. With methods, their only difference from classes is that you have to use record construction syntax (no custom constructors) and there is no inheritance. The difference from structs is actually larger; like most F# types descended from OCaml, records are reference types while structs (nominally descended from C) are value types.

discriminated union

type Suit = Hearts | Diamonds | Clubs | Spades
type Card = Joker 
  | Ace of Suit 
  | King of Suit 
  | Queen of Suit 
  | Jack of Suit 
  | Number of int * Suit
let hand = [King Hearts; 
            Queen Hearts;
            Jack Hearts;
            Number (10, Hearts);
            Number (3, Spades)]

Discriminated unions aren’t really like the other structures in the list; they’re sum types, unlike the others, which are product types. You choose only one field of a sum type at a time, whereas with product types, you have to provide all fields. In other words, discriminated unions are like enums: you choose one. However, discriminated unions can also carry a tuple of information with them, making pattern-matching them particularly powerful. Discriminated unions are often used much like an inside-out abstract class hierarchy.

And that’s all for this instalment. I’ll talk about modules, closures, structs and classes next time. Maybe even functors and object expressions!

Disclaimer: This is a description of F# as I understand it. I may make incorrect generalisations or be flat out wrong. I am not an expert and F# is still in beta. If you want to correct me, please do so I can edit this post.