F# advent 2015 - santas prime

santasprime.fs

// let's start with something easy: Chruch-encoded-Booleans:

type BoolC =
    abstract apply : 'a -> 'a -> 'a
   
let trueC : BoolC = 
    { new BoolC with member __.apply t _ = t  }

let falseC : BoolC = 
    { new BoolC with member __.apply _ f = f }

/// if is the catamorphism of this type
let ifC (b : BoolC) = b.apply

/// conjunction
let andC (a : BoolC) (b : BoolC) : BoolC =
    ifC a b falseC

let valueBool (b : BoolC) =
    b.apply true false


// -----------------------------------

// for a bit more fun add Pairs - we gonna need them for pred later

type PairC<'a,'b> =
    abstract apply : ('a -> 'b -> 'c) -> 'c

let fst (p : PairC<_,_>) =
    p.apply (fun a _ -> a)

let snd (p : PairC<_,_>) =
    p.apply (fun _ b -> b)

let pair (a : 'a) (b : 'b) : PairC<'a,'b> =
    { new PairC<'a,'b> with member __.apply f = f a b }

// -----------------------------------

// let's do numbers

type NatC =
    abstract apply : ('a -> 'a) -> 'a -> 'a

let zero : NatC =
    { new NatC with member __.apply _ z = z }

let succ (n : NatC) : NatC =
    { new NatC with member __.apply s z = s (n.apply s z) }

let add (a : NatC) (b : NatC) =
    a.apply succ b

let pred (n : NatC) : NatC =
    fst (n.apply (fun p -> pair (snd p) (succ (snd p))) (pair zero zero))

let sub (a : NatC) (b : NatC) =
    b.apply pred a

let isZero (n : NatC) : BoolC =
    n.apply (fun _ -> falseC) trueC

let equals (a : NatC) (b : NatC) : BoolC =
    andC (isZero (sub a b)) (isZero (sub b a))

let divides (a : NatC) (b : NatC) : BoolC =
    let decr n = ifC (equals a n) n (sub n a)
    in equals a (b.apply decr b)

let biggestDivisor (n : NatC) : NatC =
    let decr m = ifC (divides m n) m (pred m)
    in n.apply decr (pred n)

let isPrime (n : NatC) : BoolC =
    equals (biggestDivisor n) (succ zero)

// ---------------------------------------
// sum en up
let one = succ zero
let two = succ one
let three = succ two
let four = add two two
let eight = add four four
let sixteen = add eight eight
let twenty = add sixteen four
let twentythree = add twenty three

let is23prime =
    isPrime twentythree
    |> valueBool

[<EntryPoint>]
let main argv = 
    match is23prime with
    | true  -> "Hohoho - tomorrow is christmas eve"
    | false -> "Well wake me up next week"
    |> printfn "%s"

    try
        while true do
            printf "Want to try more? Insert a number: "
            let n = System.Console.ReadLine () |> System.Int32.Parse
            let prime =
                [1..n] 
                |> Seq.fold (fun m _ -> succ m) zero
                |> isPrime
                |> valueBool
            if prime
            then printfn "%d is prime" n
            else printfn "%d is not prime" n
        0
    with _ -> 0