Search code examples
recursionpolymorphismsml

SML: Polymorphic function that calls another instantiation of itself

Is there a way, to write a polymorphic function (in sml), that calls itself with arguments of different type than the arguments it has got?

For example, I was looking on this answer, (it has the declaration datatype ('a,'b)alterlist = Nil| element of 'a*('b,'a)alterlist;) and intuitively, I would like to implement the function unzip, as:

fun unzip Nil = ([],[]) |
    unzip (element(x,l)) = let val (b,a)=unzip l in (x::a,b) end;

The type inference system understands it as ('a,'a) alterlist -> 'a list * 'a list, but I want something of type ('a,'b) alterlist -> 'a list * 'b list (such that the inner call is to a ('b,'a) alterlist -> 'b list * 'a list)

Solution

  • I believe what you are asking for is polymorphic recursion, which is not implemented in standard ML.

    This is however implemented in Haskell (and as @seanmcl pointed out, ocaml):

    import Prelude hiding(unzip)

data Alterlist a b = Nil | Elem a (Alterlist b a)

unzip :: Alterlist a b -> ([a], [b])
unzip Nil = ([], [])
unzip (Elem x l) =
    let (b, a) = unzip l
    in (x : a, b)

x = Elem 1 (Elem True (Elem 5 (Elem False Nil)))

*Main> unzip x
([1,5],[True,False])