I’d like to know how to exit from calculation in OCaml.
But, first of all, I try experimenting in OCaml, but I know this programming style is not an expected way in OCaml.
The experiment is that how to program a function like member in Lisp with fold_left of OCaml(Don’t say that there is List.mem or List.memq in OCaml. I already know that).
The code I wrote was:
let member1 ?(pred = fun x y -> x = y) item lst =
List.fold_left (fun x y ->
try
match (pred item y) with
true -> raise Exit
| false -> match x with
[] -> []
| first::rest -> rest
with
Exit -> x
) lst lst
OCaml has an implicit return, because it is a functional programming language.
Therefore, I do not know something like “break” during calculation.
An information on the web around OCaml says we just use try … with syntax(of course, it is for handling exception) to “exit” from calculation, but the program above shows “No exiting” at all.
Is there any way to make-calclation-stop-and-returning-a-value way?
Thanks.
P.S.
In Lisp like Scheme, the code could be written like
I see, that’s the way, uh-huh, uh-huh, OCaml likes it, uh-huh, uh-huh. (by ‘KC And The Sunshine Band’)
you have to go through the structure manually
Yes, what you wrote, a recursive way, must be a typical way.
But what I was interested in was “to use a typical higher-order function”, or fold, and how to quit calculation in the process of fold.
let mem (type a) pred l =
let exception Found of a in
match List.iter (fun x -> if pred x then raise (Found x)) l with
| exception Found x -> Some x
| _ -> None
The issue with your code is that you are not exiting the fold_left since the exception is caught in the function argument of fold_left.
It might be however more idiomatic to write a fold variant with an explicit short-circuiting option:
type status =
| Done
| Keep_going
let rec fold_with_early_exit f acc = function
| [] -> acc
| a :: q ->
let status, acc = f acc a in
match status with
| Done -> acc
| Keep_going -> fold_with_early_exit f acc q
What seems to be strange is that, let’s make a assoc function by using fold_left.
(Don’t say that there is List.assoc in OCaml. This is just an experimental example)
let assoc1 ?(pred = fun x y -> x = y) item lst =
List.fold_left (fun x y ->
try
match (pred (List.hd x) (List.hd y)) with
true -> raise Exit
| false -> x
with
Exit -> y) [item] lst
The strange is that, in this case, try…with works fine; true the pattern matching makes throws exception Exit, the calculation stops, and then returns value.
In other words, what makes me confused is, assoc1 succeeds but member1 fails, even though those two have similar structures, or try … with syntax with raise.
exception Found of int
let mem pred l =
try
List.iter (fun x -> if pred x then raise (Found x)) l;
None
with Found x ->
Some x
Now in OCaml an exception can be caught without try…with, with a match and the keyword exception in the match.
The try…with can be put inside or outside the function provided to the higher order function depending if you want local exit or non local exit.
Edit: This answer is similar to @fccm’s above (concurrent posting…).
The problem in your first attempt is that the try ... with should be outside of the fold for it to work. It works if adapted thus:
let member1 ?(pred = fun x y -> x = y) item lst =
try
List.fold_left (fun x y ->
if pred item y then
raise Exit
) () lst;
false
with
Exit -> true
However, the fact that the folding function ignores its argument x, and in fact does not accumulates anything, suggests that this is in fact an iteration, as @otachron suggested.
In Ocaml, it does not seem a good idea to use List.fold_left on everything, relatively speaking to Lisp. It might be better to use List.iter instead, as you guys have shown here.
Hi there,
You can actually implement a call/cc-like behavior from @octachron’s first construct :
let callcc (type a) f =
let exception Kont of a in
let k x = raise (Kont x) in
try f k with
| Kont x -> x
val callcc : (('a -> 'b) -> 'a) -> 'a = <fun>
callcc
(fun k ->
let n = 1 + k 50 in
(* never reaches here *)
n * n
);;
- : int = 50
However, you need to be careful not to accidentally sink the exception from within the inner function :
let f k =
try
(* code that may trigger a Not_found exception *)
k 50
with
| _ -> 12 ;;
callcc f
- : int = 12
Let’s suppose that no Not_found exception was raised at line 3.
The exception (Kont 50) fires at line 4 and the deepest "try … with … " handler first gets the chance to match it.
Since the wildcard “_” matches any exception, (Kont 50) gets replaced by the value 12 and callcc is left under the impression that no exception has ever occured !
That’s why you should restrict that wildcard use and be more specific when catching an exception :
let f k =
try
(* code that may trigger a Not_found exception *)
k 50
with
| Not_found -> 12 ;;
callcc f;;
- : int = 50
Here, the exception (Kont 50) is not matched by the local handler.
Callcc’s handler is next in line to process it : there is a match and (Kont 50) is then caught and eventually replaced with 50
I do avoid handling exceptions whenever possible. In most usecases, you can use the “result monad” instead, a nice pattern that both composes well and yields more readable code : exception vs. monad on Ocaml discuss result monad in action
Nota :
If f needs additional arguments, you can slightly change the definition of callcc :
let callcc1 (type a) f arg =
let exception Kont of a in
let k x = raise (Kont x) in
try f k arg with
| Kont x -> x
val callcc1 : (('a -> 'b) -> 'c -> 'a) -> 'c -> 'a = <fun>
Be careful with trying to implement callcc using exceptions though, as what you get from a raise can only ever be the dynamically enclosing try, not the statically enclosing one. So the actual semantics are very different from what is expected of call/cc in e.g. SML/NJ or Scheme.
I would actually say that using fold on something that is not a fold is not a great way to deal with it in Scheme either. The idea is that these higher-order functions signal something:
iter some kind of iteration doing side-effects on the entire data structure
map some kind of transformation of one element of the structure into the other
(mapi some kind of transformation where the index of the value is of some importance)
fold some kind of accumulation of values where later values are combined with the result of accumulating the earlier values
Of course you can use fold to implement either of these, but using the right one also signals to the reader more or less what you intend to do. In fact you can even use map to implement fold by keeping a mutable accumulator at hand that you modify on every new element, but most people would agree that this is a rather poor solution in terms of understandability.
@jjb: could you explain your remark on the difference between these two “callcc” (@jperennou’s OCaml emulation and Scheme) or point to a resource explaining it ? Thanks.
A study and explanation of this that I like is Riecke and Thielecke’s article Typed Exceptions and Continuations Cannot Macro-Express Each Other. There, both exceptions and continuations are formulated in the same setting in a simple and precise way. The paper shows that neither feature can express the other, and gives example small pieces of code that demonstrate the crucial differences.
Also note that while continuations on their own cannot express exceptions, if the language supports storing continuations in mutable state, then exceptions can be expressed. But exceptions plus state still cannot express continuations, which is discussed in Thielecke’s On Exceptions Versus Continuations in the Presence of State.
These articles use an ML-flavor of callcc, which has an associated throw operation to invoke a captured continuation. Apart from working in a typed language, it is not an semantic difference compared to how Scheme’s call/cc packages captured continuations as regular functions that can just be called instead of using a separate operation.