Subsequences of a seq<'a>

let cons x xs = seq { yield x

                      yield! xs }

let (|Empty|Cons|) xs : Choice<Unit, 'a * seq<'a>> =

     if (Seq.isEmpty xs) then

        Empty

      else

        Cons(Seq.head xs, Seq.skip 1 xs)

let rec subseq xs =

    match xs with

    | Empty -> seq[seq[]]

    | Cons(x,xs) -> let subseq = subseq xs

                    Seq.append (Seq.map (cons x) subseq) subseq

open System

open FsCheck

type MyGenerators =

    static member Seq() =

        let fsList = Arb.Default.FsList()

        {new Arbitrary<seq<'a>>() with

            override x.Generator =

                Gen.resize 10 (Gen.map (List.toSeq) (fsList.Generator))

            override x.Shrinker t =

                Seq.map (List.toSeq) (fsList.Shrinker(Seq.toList t)) }

ignore (Arb.register<MyGenerators>())

Check.Quick (fun xs -> (Seq.length (subseq xs) =

                       int (Math.Pow(2.0, (float (Seq.length xs))))))

Factorial using only Algebraic Data Types and Pattern Matching

type Nat = Zero | Succ of Nat

let one = Succ Zero

let two = Succ (Succ Zero)

let three = Succ (Succ (Succ Zero))

let rec add x y = match x with

                  | Zero -> y

                  | Succ x -> Succ (add x y)

let rec mul x y = match y with

                  | Zero -> Zero

                  | Succ Zero -> x

                  | Succ y -> add x (mul x y)

let rec fac n = match n with

                | Zero -> Succ Zero

                | Succ x -> mul n (fac x)

open FsCheck

// Addition properties

Check.Quick (fun x y -> (add x y) = (add y x))

Check.Quick (fun x y z -> (add x (add y z)) = (add (add x y) z))

Check.Quick (fun x -> (add x Zero) = x)

// Multiplication properties

Check.Quick (fun x y -> (mul x y) = (mul y x))

Check.Quick (fun x y z -> (mul x (mul y z)) = (mul (mul x y) z))

Check.Quick (fun x -> (mul x one) = x)