gistfile1.ml

#light

let rec printList xs =
    match xs with
    | [] -> printfn ""
    | [x] -> printf "%d" x
             printList []
    | x :: xs -> printf "%d, " x
                 printList xs

// natural numbers
let N = Seq.init_infinite (fun x -> x)

// pairwise diff of all the elements in a list
(*
 It seems like the recursive version below is a little faster and seems more intuitive to me
let difs xs = 
    Seq.pairwise xs 
    |> List.of_seq
    |> List.map (fun (x, y) -> y - x)
*)

let rec difs = function
    | [] -> []
    | [x] -> []
    | x::x'::xs -> x' - x :: difs (x'::xs)

let isConstant xs =
    let x = Seq.hd xs
    Seq.for_all (fun x' -> x' = x) xs
    
// keep applying diff to the result of applying f to xs until the result isConstant
let findConstant f xs =
    let rec aux xs' n =
        printList xs'
        match xs' with
        | _ when isConstant xs' -> n
        | _ -> aux (difs xs') (n + 1)
    aux (List.map f xs) 1

let rec pow x y = 
    if y = 1 then x
    else x * (pow x (y - 1))

do
    let domain = Seq.take 20 N |> List.of_seq
    let f x = 4 * (pow x 100) - 40 * (pow x 39) + 4
    let n = findConstant f domain
    printfn "Polynomial is of %d degrees." n