Can I annotate the complete type of a `fun` declaration?

manpreet Best Answer 2 years ago

In a learning environment, what are my options to provide type signatures for functions?

Standard ML doesn't have top-level type signatures like Haskell. Here are the alternatives I have considered:

1. Module signatures, which require either a separate signature file, or the type signature being defined in a separate block inside the same file as the module itself. This requires the use of modules, and in any production system that would be a sane choice.

   Modules may seem a little verbose in a stub file when the alternative is a single function definition. They both introduce the concept of modules, perhaps a bit early,

2. Using val and val rec I can have the complete type signature in one line:

   val incr : int -> int =
     fn i => i + 1
   
   val rec map : ('a -> 'b) -> 'a list -> 'b list =
     fn f => fn xs => case xs of
          []    => []
        | x::ys => f x :: map f ys

   Can I have this and also use fun?

   If this is possible, I can't seem to get the syntax right.

3. Currently the solution is to embed the argument types and the result type as such:

   fun map (f : 'a -> 'b) (xs : 'a list) : 'b list =
     raise Fail "'map' is not implemented"

   But I have experienced that this syntax gives the novice ML programmer the impression that the solution either cannot or should not be updated to the model solution:

   fun map f [] = []
     | map f (x::xs) = f x :: map f xs

   It seems then that the type signatures, which are supposed to aid the student, prevents them from pattern matching. I cannot say if this is because they think that the type signatures cannot be removed or if they should not be removed. It is, of course, a matter of style whether they should (and where), but the student should be enabled to explore a style of type inference.

manpreet 2 years ago

val map = fn f => let fun map = ... in map end

local
  fun map (f : 'a -> 'b) (x::rest : 'a list) : 'b list
        = f x :: map f rest
    | map _ ([]) = []

 in
 val (map : ('a -> 'b) -> 'a list -> 'b list) = map;
end

local
  structure X = struct
    fun id x = x
  end
  in val id = X.id 
end

exception ReplaceSorryWithYourAnswer

fun sorry () = raise ReplaceSorryWithYourAnswer

local
  (* Please fill in the _'s with the arguments
     and the call to sorry() with your answer *)
  fun map _ _ = sorry ()
in
  val map : ('a -> 'b) -> ('a list) -> ('b list) = map
end