F# - Stack interface?

Question

How can I write the interface for a type of immutable stacks in F#?

Here is my attempt.

[<Interface>]
type stack<'a> =
    abstract member push : 'a -> stack<'a>
    abstract member peek : unit -> 'a option
    abstract member pop : unit -> 'a option * stack<'a>

This doesn't work. It appears the problem is that the codomain of the push function is understood to be any type implementing the interface, not this type. In this case, apparently this problem would come up with an interface for any immutable data structure such that operations return a new instance of the type.

let push_to_stack (x : 'a) (t : 't when 't:> stack<'a>) : 't = (t.push x :> 't)

Error: input.fsx (1,65)-(1,79) typecheck error The static coercion from type
stack<'a> 
to
't
involves an indeterminate type based on information prior to this program point. Static coercions are not allowed on some types. Further type annotations are needed.

Answer 1

If you really-really want to have the notion of "this type", the usual trick is to have it as another generic parameter:

[<Interface>]
type stack<'a, 'impl when 'impl :> stack<'a, 'impl>>  =
    abstract member push : 'a -> 'impl
    abstract member peek : unit -> 'a option
    abstract member pop : unit -> 'a option * 'impl

Then you can implement it like this:

type MyIntStack () =
    interface stack<int, MyIntStack> with
        member this.push x = this
        member this.peek () = None
        member this.pop () = None, this

However, that still comes out a bit awkward, because you'd have to upcast MyIntStack to stack before every call:

let s = MyIntStack()
let s' = s.push 42 // Doesn't work: `s` is not a `stack<>`
let s' = (s :> stack<_, _>).push 42 // This works, but see how inconvenient it is?

And the usual trick for that is to duplicate these private interface implementation methods as public:

type MyIntStack () =
    member this.push x = this
    member this.peek () = None
    member this.pop () = None, this
    interface stack<int, MyIntStack> with
        member this.push x = this.push x
        member this.peek () = this.peek ()
        member this.pop () = this.pop ()

(C# does this duplication automatically for you, but in F# you have to be explicit)

And now you can call them nicely:

let s = MyIntStack()
let s' = s.push 42 // Works now!

But now that you have these methods public anyway, you don't actually need the interface methods to return "this type". They can return stack<'a> just fine:

[<Interface>]
type stack<'a>  =
    abstract member push : 'a -> stack<'a>
    abstract member peek : unit -> 'a option
    abstract member pop : unit -> 'a option * stack<'a>

type MyIntStack () =
    member this.push x = this
    member this.peek () = None
    member this.pop () = None, this
    interface stack<int> with
        member this.push x = this.push x
        member this.peek () = this.peek ()
        member this.pop () = let r, s = this.pop () in r, s :> _

It's all much simpler than appears at first glance.