Why is this code is generating an infinite recursion in SML if it has a base case?

Question

I wrote the following code in SML with the NJ Compiler:

fun all_answers (f, xs) = 
    let 
        fun aux(accu, xs_left) = 
            case xs of
               [] => SOME accu
            | x::xs' => case f(x) of 
                          NONE => NONE
                        | SOME y => aux(accu@y, xs')
    in
        aux([], xs)
    end

It works well for this tests:

val testAll1 = all_answers ((fn x => if x = 1 then SOME [x] else NONE), []) = SOME []
val testAll2 = all_answers ((fn x => if x = 1 then SOME [x] else NONE), [2,3,4,5,6,7]) = NONE

However, something weird happens with this test:

val testAll3 = all_answers ((fn x => if x = 1 then SOME [x] else NONE), [1]) = SOME [1]

After running the program, the terminal goes on forever.

I defined the tail recursion and used the pattern-match with xs' to reach the tail.

Moreover, I defined the base case to end the recursion so that if xs is [] then the auxiliary function returns SOME accumulator

Can anybody help me?

Thanks in advance.

Answer 1

As @kopecs pointed out, this is caused by case xs of when you want case xs_left of.

Here is a cleaned up (whitespace, naming) version of your function:

fun all_answers (f, ys) =
    let
        fun aux (accu, xs) =
            case xs of
                 [] => SOME accu
               | x::xs' => case f x of
                                NONE => NONE
                              | SOME y => aux (accu@y, xs)
    in
        aux ([], ys)
    end

There are at least two things you could do to simplify the way this function is made. (1) Perform the case xs of inside the function pattern rather than in a nested case-of. (2) Remove the inner aux function and simply do the recursion in the outer function, at the expense of some tail-recursion

The first simplification might look like:

fun all_answers2 (f, ys) =
    let
        fun aux (accu, []) = SOME accu
          | aux (accu, x::xs) =
               case f x of
                    NONE => NONE
                  | SOME y => aux (accu@y, xs)
    in
        aux ([], ys)
    end

And the second might look like:

fun all_answers' (f, []) = SOME []
  | all_answers' (f, x::xs) =
      case f x of
           NONE => NONE
         | SOME ys => case all_answers' (f, xs) of
                           NONE => NONE
                         | SOME result => SOME (ys @ result)

This shows a pattern: Whenever you have

case f x of
     NONE => NONE
   | SOME y => case g y of
                    NONE => NONE
                  | SOME z => ...

then you have a programming pattern that could be abstracted out with a function.

There is already a standard library function that is made for this called Option.map, so you could write:

fun all_answers3 (f, ys) =
    let
        fun aux (accu, []) = SOME accu
          | aux (accu, x::xs) =
              Option.map (fn y => aux (accu@y, xs))
                         (f x)
    in
        aux ([], ys)
    end

Try and play around with this function in the REPL:

- Option.map (fn y => y + 2) NONE;
> val it = NONE : int option
- Option.map (fn y => y + 2) (SOME 2);
> val it = SOME 4 : int option

---

Taking this in another direction, rather than an inner function:

(* Alternative to Option.map: *)
fun for NONE _ = NONE
  | for (SOME x) f = f x

(* Equivalent to Option.mapPartial with "flipped" arguments: *)
fun for opt f = Option.mapPartial f opt

fun all_answers'' (f, []) = SOME []
  | all_answers'' (f, x::xs) =
      for (f x) (fn ys =>
        for (all_answers'' (f, xs)) (fn result =>
          SOME (ys @ result)))

This style is more Haskell-like because it follows a monadic design pattern.