difficulty returning moderately complex F# type signature

Question

I've defined F# Tree and Stack types, with a pop member on the Stack. I can't get the type signature right on results of the pop. Here is my code up until I try to use pop:

type Tree<'a> =
    | Tree of 'a * 'a Tree * Tree<'a>
    | Node of 'a 
    | None

type 'a Stack =
    | EmptyStack 
    | Stack of 'a * 'a Stack 
    member x.pop = function
        | EmptyStack -> failwith "Empty stack"
        | Stack(hd, tl) -> (hd:'a), (tl:Stack<_>)

let myTree = Tree("A", Tree("B", Node("D"), None), Tree("C", Tree("E", None, Node("G")),  Tree("F", Node("H"), Node("J"))))

let myStack = Stack((myTree, 1), Stack.EmptyStack)

Now I've tried various ways to return the pop, and each one throws a different kind of error with the signature:

let (tree, level), z = myStack.pop

throws: stdin(22,24): error FS0001: This expression was expected to have type ('a * 'b) * 'c but here has type (Tree * int) Stack -> (Tree * int) * (Tree * int) Stack

//let (tree:Tree<_>, level:int), z:Stack<Tree<_>*int> = myStack.pop
let (tree:Tree<_>, level:int), z:Stack<'a> = myStack.pop
//let (tree:Tree<'a>, level:int), _ = myStack.pop
//let (tree:Tree<string>, level:int), z:Stack<Tree<string>*int> = myStack.pop

The attempt uncommented above throws: stdin(16,46): error FS0001: This expression was expected to have type (Tree<'b> * int) * 'c but here has type 'a Stack

Stephen Swensen Stephen Swensen · Accepted Answer · 2011-05-15T21:03:24

The problem is that pop here is an instance method taking one argument (due to function), but you want it to be an instance method taking zero arguments (i.e. unit), like

type 'a Stack =
    | EmptyStack 
    | Stack of 'a * 'a Stack 
    member x.pop() =
        match x with
        | EmptyStack -> failwith "Empty stack"
        | Stack(hd, tl) -> (hd:'a), (tl:Stack<_>)

and then call it like

let (tree,level), z = myStack.pop()

[Edit]

But actually, since Stack is immutable here, it doesn't really make sense to implement pop as an instance member, since then it's really more like peek. So you might want to implement it as a function in a companion module (or / and as a static member of Stack for compatibility with other .NET languages):

type 'a Stack = \\'
    | EmptyStack 
    | Stack of 'a * 'a Stack 

[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
module Stack =
    let pop = function
        | EmptyStack -> failwith "Empty stack"
        | Stack(hd, tl) -> (hd:'a), (tl:Stack<_>)

and call it like

let (tree, level), z = Stack.pop myStack

difficulty returning moderately complex F# type signature

1 Answers