function which gets another function as argument in SML

Question

Consider function g gets integer and returns true if the integer is bigger than some random const positive value that was decided before, otherwise false.

I would like to write a function f in SML which gets the function g as argument. this function f should return this random const positive value that was decided before.

Algorithm (In some other language, C or something):

 int f(int num) {
     int num = 1;
     while(!g(num)) {
         num++;
     }
     return num;
 }

Now this is what I tried in SML:

fun f g = 
let
    val num = 1;
in
    while !(g num) do (
        val num = num + 1;
    );
    num
end;

But it doesn't work. Any suggestions?

Answer 1

val num = num + 1;

First of all val is only allowed at the top level or inside a let. Secondly it defines a new variable. So in your C code, it'd be equivalent to:

int num = num + 1;

And not:

num = num + 1;

In other words, it creates a new variable rather than modifying the existing one, which doesn't help you here.

So the natural follow-up question would be how you do num = num + 1. And the most direct answer is: you don't. All variables in SML are immutable, so you can't re-assign variables. However you can work around this by using refs, which are mutable.

However the proper way to do this in SML is to not use while loops or re-assignments at all and instead use recursion.

Answer 2

As sepp2k explained, your problem has nothing to do with the passing of g but how you try to define a loop. Here is one way to implement it using recursion, which is what you normally do in ML:

fun f' g n = if g n then n else f' g (n + 1)
fun f g = f' g 1

Or if you want to keep the auxiliary function local:

fun f g =
  let fun loop n = if g n then n else loop (n + 1)
  in loop 1 end