About None in Ocaml

Question

I am a beginner to Ocaml. I am trying to write some code about normal order reduction, and is confused by some syntax. The following is some truncated code to isolate my error.

type expr =
| Var of char
| Num of int
| Lambda of expr
| Apply of expr * expr

let rec substitute f id e = match f with
| Num(i) -> if id == i then e else f
| _ -> f

let rec beta_lor e = match e with
| Apply(Lambda(f), e2) -> substitute f 1 e2
| Apply(e1,e2) -> beta_lor e1
| Lambda e1 -> beta_lor e1
| _ -> None

In a file of .mli I claim the beta_lor shall be of type: val beta_lor: expr -> expr option

Now when I compile this file it report error about the line the "None" I used in beta_lor: Error: This expression has type 'a option but an expression was expected of type expr

I understand that ocaml compiler tries to do type inference, and it expects me to output an expression, rather than 'a option, but I have claimed that beta_lor may output option? I am somewhat confused, please help.

Answer 1

Your problem is that substitute doesn't return expr option. It just returns expr. Maybe what you want is for beta_lor to return Some (substitute f 1 e2) for that case.

Edit

For what it's worth, your descriptions seem to be based on the idea that an option type is like a pointer type in a mainstream language, either an interesting pointer or NULL. It's more enlightening (in my opinion) to focus on the fact that there are exactly two cases: Some expr and None. You need to wrap and unwrap these two cases explicitly in OCaml, which (again, in my opinion) is vastly better than treating NULL as a legal pointer value. We see around us every day the downside of the mainstream model (sorry for editorializing).