Как передать возвращаемый тип функции в исключение в OCaml?

Question

У меня есть функция «my_a» в OCaml, что может иметь очень сложный тип возврата:

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*) 

Это моя проблема: Я использую BackTrack, чтобы найти решение. Когда исключение backtrack поднимается do_stuff, не было решения, идущего по этому пути. Однако, когда он вызывает исключение типа Continue, это означает, что он нашел решение, но, возможно, это не лучшее решение, вот когда я снова попробую с другим путем. Если есть другое исключение, я хочу вернуть ответ, который он уже нашел.

Дело в том, что для использования этой функции OCaml мне нужно сказать, какой тип данных будет продолжаться. Что возвращения верхнего уровня OCaml, когда я определить my_a:

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

Кто-нибудь есть какие-либо идеи о том, как сделать это, или другое решение, что?

Answer 1

Вы ничего не получаете, используя исключения. Вот возможное решение.

(** 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
• вторым аргументом является функция поиска, которая принимает состояние типа 'a и возвращается либо в Solution (x,a), где x имеет тип 'b и a имеет тип 'c, или Branches lst где lst имеет тип 'a list.

Answer 2

Трудно точно сказать, что вы просите. Я думаю, вы можете спросить, как получить тип внутри исключения Two, который должен быть установлен в тип возврата A без необходимости специально объявлять этот тип. Я не могу придумать, как это сделать.

Все может быть лучше, если вы использовали варианты опций вместо исключений. Или вы можете просто объявить возвращаемый тип A явно. Это может быть хорошая документация.

Пара комментариев стороны: (a) имена функций должны начинаться с буквы нижнего регистра (b) этот код выглядит довольно запутанным и трудно следовать. Может быть более простой способ структурирования ваших вычислений.