在OCaml中倒数游戏

Question

这是一个非常典型的游戏。

给出一个整数列表和一个值。

您使用parenthesis，+，-，*，/去最接近给定值。

不一定必须使用列表中的所有整数。如果无法计算出相同的值，那么您正在追求最接近的值。

---

例如，你是给[1;3;7;10;25;50]和831。你可以做的最接近的是

7 + (1 + 10) * (25 + 50) = 832

---

如何编写程序的FP或者Ocaml来解决这个问题？

1. 如何应用括号？
2. 如何生成所有可能的表达式？

Answer 1

let (|->) l f = List.concat (List.map f l) 

type op = Add | Sub | Mul | Div 

let apply op x y = 
    match op with 
    | Add -> x + y 
    | Sub -> x - y 
    | Mul -> x * y 
    | Div -> x/y 

let valid op x y = 
    match op with 
    | Add -> true 
    | Sub -> x > y 
    | Mul -> true 
    | Div -> x mod y = 0 

type expr = Val of int | App of op * expr * expr 

let rec eval = function 
    | Val n -> if n > 0 then Some n else None 
    | App (o,l,r) -> 
    eval l |> map_option (fun x -> 
     eval r |> map_option (fun y -> 
     if valid o x y then Some (apply o x y) 
     else None)) 

let list_diff a b = List.filter (fun e -> not (List.mem e b)) a 
let is_unique xs = 
    let rec aux = function 
    | [] -> true 
    | x :: xs when List.mem x xs -> false 
    | x :: xs -> aux xs in 
    aux xs 

let rec values = function 
    | Val n -> [n] 
    | App (_,l,r) -> values l @ values r 

let solution e ns n = 
    list_diff (values e) ns = [] && is_unique (values e) && 
    eval e = Some n 

(* Brute force solution. *) 

let split l = 
    let rec aux lhs acc = function 
    | [] | [_] -> [] 
    | [y; z] -> (List.rev (y::lhs), [z])::acc 
    | hd::rhs -> 
     let lhs = hd::lhs in 
     aux lhs ((List.rev lhs, rhs)::acc) rhs in 
    aux [] [] l 

let combine l r = 
    List.map (fun o->App (o,l,r)) [Add; Sub; Mul; Div] 
let rec exprs = function 
    | [] -> [] 
    | [n] -> [Val n] 
    | ns -> 
    split ns |-> (fun (ls,rs) -> 
     exprs ls |-> (fun l -> 
     exprs rs |-> (fun r -> 
      combine l r))) 

let rec choices = function _ -> failwith "choices: implement as homework" 

let guard n = 
    List.filter (fun e -> eval e = Some n) 
let solutions ns n = 
    choices ns |-> (fun ns' -> 
    exprs ns' |> guard n) 

(* Alternative implementation *) 

let guard p e = 
    if p e then [e] else [] 
let solutions ns n = 
    choices ns |-> (fun ns' -> 
    exprs ns' |-> 
     guard (fun e -> eval e = Some n)) 

有关说明，请参见Functional Programming in OCaml。