CODEWITHSUNDEEP
typesparameterssmlsmlnjml
hakuna matata
hakuna matata

Reputation: 3327

In Standard ML, how can I define a function of type 'a * 'a -> bool?

I'm trying to make a function in Standard ML that takes 2 parameters and returns a bool, and the 2 parameters can be any type, in the specs its written to be 'a * 'a -> bool but whenever i try it, it makes the 2 parameters ints automatically. How can I make the function take 2 parameters of type 'a.

the following is the function ive been trying to implement:

fun lessThan (a, b) = 
    if a < b then true
    else false;

but after writing the above function what i get is :

val lessThan = fn : int * int -> bool

and what i want is this:

val lessThan = fn : 'a * 'a -> bool

What can I do to make it work?

Upvotes: 1

Views: 1593

Answers (2)

Edwin Dalorzo
Edwin Dalorzo

Reputation: 78639

I believe this is the kind of problem that we can solve with a functor in SML.

For instance, consider the existence of a signature called TOTALORDER that defines your function in the question (lt meaning lower than).

signature TOTALORDER = 
sig
    type element
    val lt: element * element -> bool
end

As you can see the function is defined as element * element -> bool, and the type of element is undefined here.

We can then define two different implementations of TOTALORDER to work with different types, as follows:

structure String : TOTALORDER =
struct
    type element = string
    fun lt(a:string, b) = a < b
end

structure Integer: TOTALORDER = 
struct
    type element = int
    fun lt(a, b) = a < b
end

Above we have defined an implementation capable of working strings, and another one capable of working with integers. You can see that in these implementation we define what is the actual type of element.

Now we can define the magic of interchangeable types in a functor, as follows:

functor MakeComparator(Lt: TOTALORDER):
    sig
        val descending : Lt.element * Lt.element -> Lt.element * Lt.element
        val ascending : Lt.element * Lt.element -> Lt.element * Lt.element
    end
    =
    struct
        open Lt;

        fun descending(a,b) = if lt(a,b) then (b,a) else (a,b)
        fun ascending(a,b) = if lt(a,b) then (a,b) else (b,a)
    end

And here we can see that the functor defines a signature with two functions called ascending and descending, based on our TOTALORDER definition. The functor receives as parameter an implementation of such signature. And later it uses it, in the struc implementation to sort a pair in ascending or descending order.

So, ultimately, the types of a and b depend on the type of element in the implementation of the TOTALORDER provided to the functor.

We can now create different implementations using different comparison types as follows:

structure StringComparator = MakeComparator(String)
structure IntegerComparator = MakeComparator(Integer)

And we can use them correspondingly with their types. For instance:

val res01 = StringComparator.ascending("arm","house") (*(arm,house)*)
val res02 = StringComparator.descending("arm","house") (*(house,arm)*)
val res03 = IntegerComparator.ascending(1,2) (*(1,2)*)
val res04 = IntegerComparator.descending(1,2) (*(2,1)*)

It's certainly verbose, compared to other languages like Haskell with type classes, but I believe it's a valid approach to solve the problem.

Upvotes: 0

Norman Ramsey
Norman Ramsey

Reputation: 202725

If you want the functions to terminate and return a value, Standard ML has only two functions of type 'a * 'a -> bool. They are

fun ktrue  (_, _) = true
fun kfalse (_, _) = false

All other total, pure functions of that type are indistinguishable from the two above.

And those two function actually have the more general type 'a * 'b -> bool.

This is actually a fairly deep result from programming-language theory. If you wanted to learn the foundations, you could try reading John Reynolds's work on representation-independence or Phil Wadler's work on "free theorems".

Upvotes: 6

Related Questions