Countdown problem in F# with brute force

countdown.fs

let rem x = List.filter ((=) x >> not)

let rec perms = function 
    | [] -> [[]]
    | xs -> 
        xs 
        |> List.collect (fun x -> List.map (fun l -> x :: l) (perms (rem x xs)))

//  1, [2, 3]
//   [2] [3] [2, 3] [] 
//   

let rec subs = function 
    | [] -> [[]]
    | x :: xs -> 
        let power = subs xs
        power 
        |> List.map (fun l -> x :: l)
        |> List.append power 

let subbags xs =
    [ for ys in subs xs do 
        for zs in perms ys -> zs ]

// [2] -> [([], [2]), ([2], [])]
//         [([1], [2]), ([1,2], []),  ([], [1,2])]
//          [([1, 2], [3]), ([1,2,3], []), ([], [1, 2, 3]), ([1], [2,3])]
//            [([1, 2, 3], [4]), ([1,2,3,4], []), ([1], [2, 3, 4]), ([1, 2], [3,4])]
// [1], [2, 3]
// [1, 2], [3]
let rec split = function 
    | [] -> [([], [])]
    | x :: xs ->
        let almost = 
            split xs
            |> List.map (fun (l, r) -> x :: l, r)
        ([], x :: xs) :: almost

// Maybe this defination won't be useful in deriving proofs?
let ne = function | [], _ | _, [] -> false | _ -> true 

let nesplit xs = List.filter ne (split xs) 



type Op = Add | Sub | Mul | Div 

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

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

type Expr = Val of int | App of Op * Expr * Expr 

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

let rec eval = function 
    | Val n -> if n > 0 then [n] else []
    | App (op, left, right) -> 
        [ for x in eval left do 
            for y in eval right do 
                if valid op x y then apply op x y ]


let solution e ns n = 
    List.contains (values e) (subbags ns) && eval e = [n]

let ops = [Add; Sub; Mul; Div]

let combine l r = 
    [ for o in ops -> App (o, l, r) ]

let rec exprs = function 
    | [] -> []
    | [n] -> [Val n] 
    | ns -> 
        [ for (ls, rs) in nesplit ns do
            for l in exprs ls do 
                for r in exprs rs do    
                    yield! combine l r ]


let solutions ns n = 
    [ for ns' in subbags ns do 
        for e in exprs ns' do 
            if eval e = [n] then e ]


type Result = Expr * int 

let combine': Result -> Result -> Result list = 
    fun (l, x) (r, y) -> 
        [ for o in ops do 
            if valid o x y 
                then App (o, l, r), apply o x y ] 

let rec results ns : Result list = 
    match ns with 
    | [] -> [] 
    | [n] -> [ if n > 0 then Val n, n ]
    | ns ->  
        [ for ls, rs in nesplit ns do 
            for lx in results ls do 
                for ry in results rs do 
                    yield! combine' lx ry ]

let solutions' ns n =   
    [ for ns' in subbags ns do 
        for e, m in results ns' do 
            if m=n then e ]


[<EntryPoint>]
let main argv =
    let l = [1;3;7;10;25;50]
    let target = 765

    let t1 = System.DateTime.Now
    let results = solutions' l target
    let t2 = System.DateTime.Now

    printfn "%A" results
    printfn "Time elapsed: %A" (t2-t1)

    0