Implementing Standard ML signatures in F# / .NET

(Questions are at the bottom in bold.)

I'm going through Chris Okasaki's Purely Functional Data Structures and I was attempting to translate the first data structure and its implementations from Standard ML to F#. The ML is as follows (translated from the book):

signature STACK =
sig
    type 'a Stack
    val empty : 'a Stack
    val isEmpty : 'a Stack -> bool
    val cons : 'a * 'a Stack -> 'a Stack
    val head : 'a Stack -> 'a (* raises EMPTY if stack is empty *)
    val tail : 'a Stack -> 'a Stack (* raises EMPTY if stack is empty *)
end

and its first implementation:

structure List:STACK =
struct
    type 'a Stack = 'a list

    val empty = []
    fun isEmpty s = null s

    fun cons (x,s) = x :: s
    fun head s = hd s
    fun tail s = tl s
end

and, for clarity, its second implementation:

structure CustomStack:STACK =
struct 
    datatype 'a Stack = NIL | CONS of 'a * 'a Stack

    val empty = NIL
    fun isEmpty NIL = true | isEmpty _ = false

    fun cons (x, s) = CONS(x, s)
    fun head NIL = raise EMPTY
      | head (CONS(x, s)) = x
    fun tail NIL = raise EMPTY
      | tail (CONS(x, s)) = s
end

I was able to port the ML signature to F# almost term for term:

type 'a Stack = Stack of 'a

type 'a STACK =
    val Stack : 'a Stack
    val empty : 'a Stack

    val isEmpty : 'a Stack -> bool
    val cons : 'a * 'a Stack -> 'a Stack
    val head : 'a Stack -> 'a
    val tail : 'a Stack -> 'a Stack

This code compiles even though, somewhat obviously, there is no way to implement the F# type as anything substantial, as there is no constructor and it is not recognized as an interface (and can't be written as one because val Stack and val empty are not functions). It compiles in fsi as a class, but obviously no constructor or anything to implement it. The fsi signature of the previous snippet is:

type 'a Stack = | Stack of 'a
type 'a STACK =
  class
    val Stack: 'a Stack
    val empty: 'a Stack
    val isEmpty: 'a Stack -> bool
    val cons: 'a * 'a Stack -> 'a Stack
    val head: 'a Stack -> 'a
    val tail: 'a Stack -> 'a Stack
  end

1. Is there any way to make use of this in the .NET ecosystem, to have just a pure type like this, practical or not? Also, is this considered some sort of bug to be able to create a non-implementable datatype?

2. Is there anyway to implement the Standard ML datastructures in F# without using interfaces and abstract classes, or are they mandatory because of the way .NET is structured?

Solution

What you have implemented compiles, but it's most certainly not what you intended to implement. It's only syntactically similar - what you're using is something called explicit class syntax, and your STACK type is a class ostensibly without a public constructor with a bunch of getter-only properties.

This is something you can check yourself through the reflection API. If you're using this code in FSI, you may find that a constructor is generated for that type anyway, and you can use Activator.Create to instantiate it - you'll see the properties all having the default null values.

open System
open System.Reflection

let typ = typeof<STACK<int>>

typ.GetProperties()

let stack = Activator.CreateInstance<STACK<int>>()

That's an artifact of FSI usage afaik, in compiled code you'd have no way of constructing a value of this type.

2. Is there anyway to implement the Standard ML datastructures in F# without using interfaces and abstract classes, or are they mandatory because of the way .NET is structured?

As far as translating the concepts goes, abstract classes and their subtypes are the most direct F# equivalent of SML signatures and structures.

This has to do with F# eschewing OCaml module system (with signatures, structures and functors) in favor of the OOP system already present .NET intermediate language. F# modules are severely limited in comparison, they're more of a grouping/namespacing tool similar to what Haskell has.

Not sure about what your experience is - I know newcomers to the language that come from an OOP background are often eager to completely abandon classes, interfaces and anything they associate with OOP, but that's a rather misguided approach. There's a reason why those concepts are part of F#, and by not using them, you're giving up a significant part of your ability to express things.

Check this thread for a similar example of an ML to F# "translation". Note that this is more "toy example" level than "solid library code" level - for that it would be advisable to use the entrenched .NET collection interfaces so that it meshes well with the wider ecosystem. This is what FSharp.Core collections do for example.