Hide your Design Decisions with Abstract Data Types

We all know the importance of protecting consumers of our libraries from our design decisions.  In object oriented programming we refer to this protection mechanism as encapsulation or black box design.  Functional programming allows us to achieve the same goal under a slightly different guise, abstract data types.

 

Abstract Data Types in ML

 

The first way to build an abstract data type in ML is to define the data type using abstype instead of datatype.

 

abstype ‘a Set = set of ‘a list

with …

 

Here we’ve chosen to use a list as the underlying store for our Set data type.  As long as we keep the “interface” the same, we are free to choose a different design for the underlying store.  The abstype keyword hides the set data constructor from the consumer, preventing sets being constructed from lists.

 

The abstype keyword may seem convenient, however, modern ML programs rarely use it.  Abstype has been deprecated in favor of opaque signature ascription.

   

signature SetSig =

sig

    type ‘a set

    val empty : ‘a set

    val singleton : ‘a -> ‘a set

end;

 

structure Set :> SetSig =

struct

    type ‘a set = ‘a list;

    val empty = [];

    fun singleton a = [a]

end;

 

The Set structure is similar to a typeclass where we’ve provided an implementation for SetSig using lists.  We are free to provide an implementation using binary trees and change the implementation Set will use under the covers.

 

signature SetSig = …

structure ListSet :> SetSig = …

structure TreeSet :> SetSig = …

Set = TreeSet

 

The consumer remains unaware that we’re now using a binary tree instead of a list to represent sets.

 

Abstract Data Types in F#

 

There is no abstype keyword in F# so we’ll use opaque signature ascription to achieve our data abstraction.

 

module SetSig

    type ‘a set

    val internal toList : ‘a set -> ‘a list

    val empty : ‘a set

    val singleton : ‘a -> ‘a set

   

module SetSig

    type ‘a set = internal Set of ‘a list

    let toList s = match s with Set lst -> lst

    let empty = Set[]

    let is_empty s = List.length(toList s) = 0

    let singleton x = Set[x]

 

There are a couple of problems with the F# implementation.

 

The fist is just annoying.  We use the module keyword for both the signature and the implementation in F#.  The signature must go into a file with the fsi extension and the implementation in a file with an fs extension.  The system is similar to header files in c and went out of favor around the time Java was introduced.  Hopefully, the day will come when the signature and the many implementations of the signature can be declared in the same file.

 

The second is limiting.  Notice how we’ve had to declare a toList method to convert our set to a list?  This limits our signature to lists.  Without the concept of functors we have no way to vary our implementation without changing our signature.

 

The third is explicitness. Even with functors in the language we would constantly have to convert from a set to a functor and back again.  There is no implicit conversion mechanism.

 

The fourth is the module system. Notice how without a different keyword for signature and structure we have no way to provide additional implementations of our signature.  ML allows the following all in one file

 

signature SetSig = …

structure ListSet :> SetSig = …

structure TreeSet :> SetSig = …

Set = TreeSet

 

How we achieve this in F# I do not know.

 

Expanding Our Set Signature

 

Let’s add a bit more functionality to our Set signature to get an idea of how cumbersome problem number two is.

 

module SetSig

    type ‘a set

    val internal toList : ‘a set -> ‘a list (* list all set elts, sorted low to high *)

    val empty : ‘a set (* the empty set *)

    val is_empty : ‘a set -> bool (* is a set the empty set *)

    val singleton : ‘a -> ‘a set (* a set with one element *)

    val union: ‘a set -> ‘a set -> ‘a set (* union of two sets *)

    val is_member : ‘a -> ‘a set -> bool (* is elt a member of given set? *)

    val remove : ‘a -> ‘a set -> ‘a set (* remove elt from given set *)

 

module SetSig

    type ‘a set = internal Set of ‘a list

    let toList s = match s with Set lst -> lst

    let empty = Set[]

    let is_empty s = List.length(toList s) = 0

    let singleton x = Set[x]

    let union s1 s2 = Set(ListSetUtils.union (toList s1) (toList s2))

    let is_member x s = ListSetUtils.is_member x (toList s)

    let remove x s = Set(ListSetUtils.remove x (toList s))

 

Two patterns should immediately jump out at you.

 

1.    We constantly have to use toList to convert our set to a list

2.    We constantly have to use the Set data constructor to wrap our list as a set

 

The constant wrapping and unwrapping obfuscates the purpose of our code and makes it harder to vary the implementation without rewriting everything.  You wish there was a way to tell the compiler to implicitly convert from list to set and vice versa instead of always having to explicitly make the conversion.

 

Pattern Matching To the Rescue

 

All is not doom and gloom, however, F# has very cool pattern matching capabilities.  Let’s say a consumer of our library wants to add a function to calculate the cardinality of the set.  In ML we would provide a destructor function and force the user into the following pattern.

 

let rec cardinality s =

    if is_empty s then 0 else

    let (x,s’) = singleton_split s

    1 + cardinality s’ 

 

With F# we can provide pattern matching over our abstract data types.

 

module SetSig

    …

    val internal singleton_split : ‘a set -> ‘a * ‘a set (* remove elt from given set and return singleton *)

    val (|Nil|Cons|) : ‘a set -> Choice<’a set,(’a * ‘a set)>

 

module SetSig

    …

    let singleton_split s =

        match toList s with

        | [] -> invalid_arg “s”

        | x::s -> let lst = ListSetUtils.remove x s

                  (x, Set(lst))

    let (|Nil|Cons|) s =

        if is_empty s then Nil(s)

        else Cons(singleton_split s)

 

Notice the return type of our pattern matching function, choice basically returns all possibilities and allows us to match on them.  The consumer of our library can now do the following.

 

let rec cardinality s =

    match s with

    | Nil s -> 0

    | Cons(x,s) -> 1 + cardinality s

 

Handy, and an F# exclusive feature.

 

A Mixed Bag of Functionality

 

The Set class provided in Microsoft.FSharp actually implements a Set as an object oriented class.  Unfortunately, swapping this Set out for your own implementation is a non starter as it does not implement an interface.

 

With Haskell we get higher kinded polymorphism and type classes, ML solves many of the same problems with a sophisticated module system, F# uses the object oriented type system of .Net to solve problems the way you would in VB or C#.  Hopefully, at some point F# will be free to forge its own road on the .Net platform, making it easier to solve problems the other functional languages have licked.