Understanding sigs and structs with casting a built-in list type to a custom stack type

Question

Suppose I have the beginning of the definition for a Stack like the following:

signature STACK = sig
  type 'a stack
end;

structure Stack :> STACK = struct
  type 'a stack = 'a list
end;

Clearly this doesn't work, because I can't cast a list to a stack:

- [5] : int Stack.stack;
stdIn:1.2-1.23 Error: expression doesn't match constraint [tycon mismatch]
  expression: int list
  constraint: int Stack.stack
  in expression:
    5 :: nil: int Stack.stack

Which means if I made a Stack.push or Stack.pop function, I couldn't pass in the int list, because it would expect a stack.

Wish I knew more about Standard ML to formulate a real question, I just know this doesn't work and I'm not sure how to approach signatures and structures.

Answer 1

When you're declare your structure, you're doing so using opaque signature matching (:>).

What opaque signature matching means is, the underlying type behind any types declared inside of the structure is hidden.

You can use transparent signature matching (:) if you don't wish for this to be the case.

Example with transparent signature matching:

structure Stack : STACK = struct
  type 'a stack = 'a list
end;

Before you do this, consider the advantages of not doing so: If you use opaque signature matching, the underlying implementation is hidden. If you wish to change the underlying implementation (to a tree structure, for instance), you could do so knowing that nothing outside of the structure can use any other functions than the ones you provide.

You may wish to instead provide a toList and fromList function to perform the conversion:

(* in the signature *)
val toList : 'a stack -> 'a list
val fromList : 'a list -> 'a stack

(* in your structure *)
fun toList s = s
fun fromList s = s

If you then change your underlying implementation, you would only have to change these two functions, rather than having to make changes all over your program.

Answer 2

Creating functions toList and fromList as Sebastian suggests is very fine. Alternatively you can create a more restrictive interface that does not allow importing and exporting directly, but only creating by push, pop and empty:

signature STACK =
sig
  type 'a stack
  val push : 'a -> 'a stack -> 'a stack
  val pop : 'a stack -> ('a * 'a stack)
  val peek : 'a stack -> 'a
  val empty : 'a stack
end

structure LStack :> STACK =
struct
  type 'a stack = 'a list
  fun push = ...
  fun pop = ...
  fun peek = ...
  val empty = []
end