SML - Base case, wrong return value for declared datatype

Question

I'm having trouble with the base case of a function that I'm writing. I have a datatype that I've declared. In the base case I need to replace the nil with something. How do I tell it that the function won't return anything?

datatype 'a newThing = Cons of 'a option * (unit -> 'a newThing);

fun permutation [] = Cons(NONE, fn () => nil)
|   permutation l = .....;


Error: operator and operand don't agree [tycon mismatch]
operator domain: 'Z option * (unit -> 'Z newThing)
operand:         'Z option * (unit -> 'Y list)
in expression:
Cons (NONE,(fn () => nil))

EDIT: I'm not allowed to change the datatype.

Answer 1

Your datatype only has the Cons value constructor (indicating another element), but you want a Nil constructor (indicating no further elements).

The typechecker then gives you a type error, because you attempt to return a nil, which is of the 'a list type, rather than 'a newThing.

What you want to do is add a Nil constructor to your 'a newThing datatype, and return this value in the base case.

datatype 'a newThing = Cons of 'a option * (unit -> 'a newThing)
                     | Nil

fun permutation [] = Nil
  | permutation l = ...

If you are to not change your datatype, there is no way to terminate the list. It will always keep going, as the only thing you can have is a Cons, which represents another element.

Assuming there are no NONE elements in the lists you want to represent, you could let the value of NONE signify the end of the list, and simply keep returning NONE infinitely once you run out of elements.

fun permutation [] = Cons(NONE, permutation [])

You could also throw an exception, if you wish:

exception EndOfNewThing

fun permutation [] = raise EndOfNewThing

Honestly, though, these are pretty poor solutions compared to adding a new value constructor.