Create a gist now

Instantly share code, notes, and snippets.

F# advent 2015 - santas prime
// 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment