0

我在 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 将携带什么数据类型。当我定义 my_a 时，OCaml 顶层返回的内容：

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

有没有人知道如何做到这一点，或者对此有不同的解决方案？

4

2 回答 2

1

很难确切地说出你在问什么。我想您可能会问如何将Two异常中的类型设置为 A 的返回类型，而无需专门声明此类型。我想不出任何办法。

如果您使用选项类型而不是异常，事情可能会变得更好。或者您可以明确声明 A 的返回类型。这可能是很好的文档。

一些旁注：(a) 函数名称必须以小写字母开头 (b) 这段代码看起来非常复杂且难以理解。可能有一种更简单的方法来构建您的计算。

于 2013-01-28T04:57:21.970 回答
0

通过使用异常，您一无所获。这是一个可能的解决方案。

(** 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
  • 第二个参数是搜索函数，它接受 type 的状态'a并返回Solution (x,a)where xhas type'b和ahas type 'c，或者Branches lstwhere lsthas type 'a list。
于 2013-01-29T08:37:42.790 回答