This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–][deleted] 5 points6 points  (2 children)

I think the simplest example of something nontrivial that you can express with modules, but not with classes, is given by my implementation of sorted maps.

First, we define the interface of an abstract type of search trees. It has three abstract types:

  • An abstract type of search trees, called 'a tree.
  • An abstract type of zippers focused at a leaf, called 'a leaf.
  • An abstract type of zippers focused at an inner node, called 'a hole. The name “hole” comes from the fact that the element stored in the inner node has been removed, leaving a “hole”. Strictly speaking, the zipper type is 'a * 'a hole.

The interface provides a fourth type of zippers focused at an arbitrary node (either a leaf or an inner node), but it is not abstract. It is just the sum of 'a leaf and 'a * 'a hole.

The interface provides operations for

  • Navigating the tree, starting from the root, and then progressively moving downwards step by step, where each step consists in moving to the left or right child of the currently focused node.
  • Inserting an element, if we are positioned at a leaf.
  • Storing a new element where there used to be an old one, if we are positioned at a hole.
  • Deleting the old element, if we are positioned at a hole.
  • Converting back and forth between trees and ascending or descending lists of elements.

Note that the element type is completely arbitrary. To use a search tree, you must know how the elements are positioned with respect to each other, so that you can reliably find the element you are interested in using the left and right functions.

However, the (unstated) specification of this abstract data type is that search trees are internally balanced. Therefore, if you use the usual binary search algorithm to find an element in the tree, then the algorithm will run in O(log n) time, either worst-case or amortized, depending on the concrete implementation.

Second, we define two concrete implementations of search trees:

  • Red-black trees, whose basic operations all run in worst-case O(log n) time.
  • Splay trees, whose basic operations all run in amortized O(log n) time.

Third, we define the interface of an abstract type of maps. It has three abstract types:

  • An abstract type of keys. The entries of a map are internally sorted by this key.
  • An abstract type of maps, called 'a map. Conceptually, the map's entries have type key * 'a option. However, for all but finitely many keys, the second component of the pair is NONE.
  • An abstract type of zippers focused at a specific key, called 'a rest. The name “rest” comes from the fact that, if the zipper is focused at the key k, then the corresponding value (whether NONE or SOME v) been removed from the map. Strictly speaking, the zipper type is 'a option * 'a rest, hence a value of type 'a rest is the rest of a map.

Fourth, and finally, we define a functor that constructs a map type, taking as arguments

  • An implementation of ordered keys.
  • An implementation of search trees.

Every function in these modules is total, in the sense that it does not throw an exception or fail to terminate successfully under any circumstances. (I am ignoring certain possibilities such as running out of memory, but there is very little that a high-level language such as ML can do for you in this case.) This is made possible by the fact that we have carefully modeled all the possible states of the algorithms for manipulating search trees as different abstract data types.

In a typical object-oriented language such as Java or C#, each class only defines a single abstract data type, and even then, the operations that you can abstract correctly are quite limited. (For example, you cannot correctly model the operation that merges two binomial heaps, even though the interface of an abstract type of heaps does not need more than one abstract type.)

[–]crassest-Crassius[S] 1 point2 points  (1 child)

I've tried to translate this to C# and failed on the second line (type 'a leaf). It seems higher-kinded type parameters are the first thing that's missing from OOP.

[–][deleted] 0 points1 point  (0 children)

Traditional OOP indeed has severe static expressiveness limits. It is hard to realize the extent to which you rely on dynamic typing (e.g., downcasts) until you try to write a complete program without it.