fold int option function

I wrote a program that takes integers of lists in lists and adds them together. Now I am trying to write this function again, but using int option integers instead.

I changed my original functions from

fun fold f base [] = base
  | fold f base (x::rest) = f x (fold f base rest);
fun add x y = x+y;
fun sumList L = fold add 0 L;

fun fold2 f base [] = SOME(base)
  | fold2 f base (x::rest) = f (SOME x) (fold2 f base rest);
fun add2 x y = SOME (x + y);
fun sumList2 L = fold2 add2 NONE L;

The add and fold2 functions both compile, but when I try to run variations of sumList2 I get operand don't agree errors.

Solution

It is a little unclear what the purpose of the options are; do you want to add the numbers inside int option lists? E.g. [SOME 1, SOME 2, NONE, SOME 3]. Or even int option list lists? E.g. [[SOME 1, NONE], [NONE, SOME 2, SOME 3], [], [NONE, NONE, NONE]]. Or are you trying to write fold using optional types on lists that don't contain optional values?

Your problem lies in the type of f's arguments. In fold2, it can be inferred to have type

'a option -> 'b option -> 'b option

because the first argument is always (SOME x), which has type 'a option, the second argument is always (fold2 f base rest), which has type 'b option because of fold2's base case, and returns 'b option for the same reason. Your add2, however, has type

int -> int -> int option

You could do one of the following things to fix this:

Your add2 assumes that its operands are integers, not integer options; i.e. you're writing SOME (x + y), and you can only add x and y when they're just numbers. Depending on what it is you're doing, add2 could treat its operands as optional; e.g.
```
fun add2 NONE b = b
  | add2 a NONE = a
  | add2 (SOME x) (SOME y) = SOME (x + y)
```
would treat NONEs as 0s. So would e.g.
```
fun add2 a b = SOME (Option.getOpt (a, 0) + Option.getOpt (b, 0))
```
but they would differ in the case of add2 (NONE, NONE) being either NONE or SOME 0.

Your fold2 is kind of pointless in the sense that it always wraps a SOME around the x: If that's always the case, then why ever do it? You can make fold2 responsible for discarding NONEs, e.g.

fun fold2 f base [] = base
  | fold2 f base (NONE::rest) = fold2 f base rest
  | fold2 f base (SOME x::rest) = f x (fold2 f base rest)

in which case its type becomes

('a -> 'b -> 'b) -> 'b -> 'a option list -> 'b

and you've created a special kind of fold that simultaneously discards NONEs. I'd probably prefer to have a separate function that does that and use it in combination with a regular fold:

fun fold f base [] = base
  | fold f base (x::rest) = f x (fold f base rest)

fun somes [] = []
  | somes (NONE::xs) = somes xs
  | somes (SOME x::xs) = x::somes xs

fun curry f x y = f (x, y)

fun sumListOption xs = fold (curry op+) 0 (somes xs)

Still, it depends entirely on what you're trying to accomplish.