exception - 関数の戻り値の型をOCamlの例外に渡す方法は?

Question

私はOCamlに関数「my_a」を持っていますが、これは非常に複雑な戻り値の型を持つ可能性があります:

exception Backtrack
exception Continue of (* How do I put the type of function 'my_a' here? *)

let my_a arg = try do_stuff (List.hd arg) 
               with 
               | Backtrack -> my_a (List.tl arg)
               | Continue (found_answer) ->  (try my_a (List.tl arg)
                                              with 
                                     | Backtrack -> raise Continue(found_answer)
                                     | Continue (other_answer) -> 
                       raise Continue (compare_answer(found_answer,other_answer));;
(* the caller of my_a will handle the Continue exception to catch the found value
if something was found*)

これは私の問題です。解決策を見つけるためにバックトラックを使用しています。do_stuff によってバックトラック例外が発生した場合、そのパスに進む解決策はありませんでした。ただし、タイプ Continue の例外が発生した場合、それは解決策が見つかったことを意味しますが、それが最善の解決策ではない可能性があるため、別のパスで再試行します。別の例外がある場合は、既に見つかった答えを返したいと思います。

問題は、OCaml のその機能を使用できるようにするには、Continue が運ぶデータ型を OCaml に伝える必要があるということです。my_a を定義したときに OCaml トップレベルが返すもの:

   'a * ('a -> ('a, 'b) symbol list list) ->
  'b list -> ('a * ('a, 'b) symbol list) list * 'b list = <fun>

誰かがそれを行う方法、またはそれに対する別の解決策を知っていますか?

Answer 1

あなたが求めていることを正確に伝えるのは難しいです。Twoこの型を明示的に宣言することなく、例外内の型を A の戻り値の型に設定する方法を尋ねているのではないかと思います。私はそれを行う方法を考えることはできません。

例外の代わりにオプションの種類を使用すると、状況が改善される可能性があります。または、 A の戻り値の型を明示的に宣言することもできます。良い資料になるかもしれません。

いくつかの補足コメント: (a) 関数名は小文字で始める必要があります (b) このコードは非常に複雑で、理解するのが難しいようです。計算を構造化するためのより簡単な方法があるかもしれません。

Answer 2

例外を使用しても何も得られません。これが可能な解決策です。

(** There are many ways to implement backtracking in Ocaml. We show here one
    possibility. We search for an optimal solution in a search space. The
    search space is given by an [initial] state and a function [search] which
    takes a state and returns either

    - a solution [x] together with a number [a] describing how good [x] is
      (larger [a] means better solution), or

    - a list of states that need still to be searched.

    An example of such a problem: given a number [n], express it as a sum
    [n1 + n2 + ... + nk = n] such that the product [n1 * n2 * ... * nk] is
    as large as possible. Additionally require that [n1 <= n2 <= ... <= nk].
    The state of the search can be expressed as pair [(lst, s, m)] where
    [lst] is the list of numbers in the sum, [s] is the sum of numbers in [lst],
    and [m] is the next number we will try to add to the list. If [s = n] then
    [lst] is a solution. Otherwise, if [s + m <= n] then we branch into two states:

    - either we add [m] to the list, so the next state is [(m :: lst, m+s, m)], or
    - we do not add [m] to the list, and the next state is [(lst, s, m+1)].

    The return type of [search] is described by the following datatype:
*)

type ('a, 'b, 'c) backtrack =
  | Solution of ('a * 'b)
  | Branches of 'c list

(** The main function accepts an initial state and the search function. *)
let backtrack initial search =
  (* Auxiliary function to compare two optional solutions, and return the better one. *)
  let cmp x y =
    match x, y with
      | None, None -> None (* no solution *)
      | None, Some _ -> y  (* any solution is better than none *)
      | Some _, None -> x  (* any solution is better than none *)
      | Some (_, a), Some (_, b) ->
        if a < b then y else x
  in
  (* Auxiliary function which actually performs the search, note that it is tail-recursive.
     The argument [best] is the best (optional) solution found so far, [branches] is the
     list of branch points that still needs to be processed. *)
  let rec backtrack best branches =
    match branches with
      | [] -> best (* no more branches, return the best solution found *)
      | b :: bs ->
        (match search b with
          | Solution x ->
            let best = cmp best (Some x) in
              backtrack best bs
          | Branches lst ->
            backtrack best (lst @ bs))
  in
    (* initiate the search with no solution in the initial state *)
    match backtrack None [initial] with
      | None -> None (* nothing was found *)
      | Some (x, _) -> Some x (* the best solution found *)

(** Here is the above example encoded. *)
let sum n =
  let search (lst, s, m) =
    if s = n then
      (* solution found, compute the product of [lst] *)
      let p = List.fold_left ( * ) 1 lst in
        Solution (lst, p)
    else
      if s + m <= n then
        (* split into two states, one that adds [m] to the list and another
           that increases [m] *)
        Branches [(m::lst, m+s, m); (lst, s, m+1)]
      else
        (* [m] is too big, no way to proceed, return empty list of branches *)           
        Branches []
  in
    backtrack ([], 0, 1) search
;;

(** How to write 10 as a sum of numbers so that their product is as large as possible? *)
sum 10 ;; (* returns Some [3; 3; 2; 2] *)

OCaml は喜んで、 の型backtrackが

'a -> ('a -> ('b, 'c, 'a) backtrack) -> 'b option

意味あり：

• 最初の引数は初期状態で、何らかのタイプがあります'a
• 2 番目の引数は検索関数で、type の状態を取り、where has typeとhas type 、またはwhere has type'aのいずれかを返します。Solution (x,a)x'ba'cBranches lstlst'a list