On CPS Part 1

"O, many
Have broke their backs with laying manors on 'em
For this great journey. What did this vanity
But minister communication of
A most poor issue?"
-- Shakespeare
Henry VIII
Act I, Scene I
Lines 83-87

I've moved further along in my journey of functional programming.  I find myself in a densely wooded forest of colossal pine trees.  The smell of juniper fills the air, bring with it memories of winters gone by.  This forest is where continuation lives.

Continuation-passing style is programming with no return, literally there is no return statement when you use continuation-passing style (CPS).  Instead what you do is pass in the function which you would like the function you are calling to return its result to.

Simple CPS example

Say you have function called f and you want f to take what ever value you give it and pass it to another function you give it that well call k.

In F# (on tryfsharp)

let f = fun x k -> k(x)


> val f : x:'a -> k:('a -> 'b) -> 'b


What we do is pass a function through k which takes one argument, like this:


f 5 (printfn "%d")



> 5
val it : unit = ()

FizzBuzz example

Lets do my favorite kata FizzBuzz using CPS.

First we make the fizzer and buzzer.

In F# (on tryfsharp)

let xzz n (w:string) =

    fun x ->
      match x with
      | x when x % n = 0 -> Some(w)
      | _ -> None
  
  let fizz x = (xzz 3 "Fizz") x
  
  let buzz x = (xzz 5 "Buzz") x

> val xzz : n:int -> w:string -> x:int -> string option
> val fizz : x:int -> string option
> val buzz : x:int -> string option


We now have a fizzer and a buzzer which will return string options.

Now let's make the fizzBuzzer using these functions.  We'll also use List.choose so we'll have either ["Fizz"], ["Buzz"], ["Fizz";"Buzz"], or [] as a result of applying fizzer and buzzer against the numerical input.  We'll then use List.reduce to concat the possible ["Fizz";"Buzz"] result.

In F# (on tryfsharp)

let fizzBuzzer n k =
  match [fizz; buzz] |> List.choose (fun f -> f n) with
  | [] -> k(n.ToString())
  | x -> k(x |> List.reduce (+))



> val fizzBuzzer : n:int -> k:(string -> 'a) -> 'a


Note this uses the fizz and buzz from before.

In order to consume this CPS version of FizzBuzz you could do the following:


 let p = (fun x -> printfn "%s" x);;
  fizzBuzzer 2 p;;
  fizzBuzzer 9 p;;
  fizzBuzzer 10 p;;
  fizzBuzzer 30 p;;

> val p : x:string -> unit

> 2
val it : unit = ()
> Fizz
val it : unit = ()
> Buzz
val it : unit = ()
> FizzBuzz
val it : unit = ()

The great thing about CPS with TDD is that you can pass what you are testing its own test case (see Full FizzBuzz example below).  I'll have more on CPS, once I wrap my head around it fully.  I am working on understanding one of the best responses I've seen on StackOverflow.

Full Fizz Buzz example in F# (with FsUnit):

open NUnit.Framework

open FsUnit

let xzz n (w:string) =

  fun x ->

    match x with

    | x when x % n = 0 -> Some(w)

    | _ -> None

let fizz x = (xzz 3 "Fizz") x

let buzz x = (xzz 5 "Buzz") x

let fizzBuzzer n k =

  match [fizz; buzz] |> List.choose (fun f -> f n) with

  | [] -> k(n.ToString())

  | x -> k(x |> List.reduce (+))

[<Test>]

let ``Validate that 2 can be Done`` () =

  (xzz 2 "Done") 2 |> should equal (Some("Done"))

[<Test>]

let ``Validate that 2 can not match`` () =

  (xzz 42 "Wrong") 2 |> should equal None

[<Test>]

let ``Validate that 6 is Fizz`` () =

  fizz 6 |> should equal (Some("Fizz"))

[<Test>]

let ``Validate that 5 is not Fizz`` () =

  fizz 5 |> should equal None

[<Test>]

let ``Validate that 10 is Buzz`` () =

  buzz 10 |> should equal (Some("Buzz"))

[<Test>]

let ``Validate that 3 is not Buzz`` () =

  buzz 3 |> should equal None

[<Test>]

let ``Validate that 2 is 2`` () =

  fizzBuzzer 2 id |> should equal "2"

[<Test>]

let ``Validate that k can be assert`` () =

  fizzBuzzer 2 (fun x -> Assert.AreEqual("2", x))

[<Test>]

let ``Validate that k can be shoulded`` () =

  fizzBuzzer 2 (fun x -> should equal "2" x)

[<Test>]

let ``Validate that 9 is Fizz`` () =

  fizzBuzzer 9 (fun x -> should equal "Fizz" x)

[<Test>]

let ``Validate that 20 is Buzz`` () =

  fizzBuzzer 20 (fun x -> should equal "Buzz" x)

[<Test>]

let ``Validate that 30 is FizzBuzz`` () =

  fizzBuzzer 30 (fun x -> should equal "FizzBuzz" x)

On Mapping

"You must be the change you wish to see in the world."
-- Mahatma Gandhi

Working in an industry with large amounts of data and having a need to apply changes to this data, I often find myself needing to apply functions against members of a data set.  In the world of functional programming this applying functions against a data set takes place on the island of higher order function on the beach known as mapping.

A mapping does exactly what we need to do when we want to apply a function against a data set, it takes each member of the data set and applies the function against it giving a resulting data set which has the results applied against it.

Here are a few simple examples:

Case 0: Identity function

The identity function does nothing, it literally takes the input and passes it as the output, applying nothing against the input.

Both Haskell and F# have a built in function called id which is the identity function.

In Haskell (on codepad):

map id [1 .. 4]

=> [1,2,3,4]

In F# (on tryfsharp):

List.map id [1 .. 4];;

val it : int list = [1; 2; 3; 4]

Case 1: Increment by 1

The "Hello World" for mapping (that actually does something) would be the increment by 1.  The function would add 1 to each input yielding an output with values that are one greater than the input.

Both Haskell and F# allow for the applying of the addition operator (+) in a mapping,

In Haskell (on codepad):

map (+1) [1 .. 4]

=> [2,3,4,5]

In F# (on tryfsharp):

List.map ((+) 1) [1 .. 4];;

val it : int list = [2; 3; 4; 5]

Case 2: Obtain first element of a tuple (or any complex data type)

One use that might not be obvious at first but is really useful is to map a certain part of a data set.  Mapping a certain value of a data set can allow for other higher order functions to apply to element later on in a chain.  Lets say you have a list of tuples and would like to get the first value of each one.

Both Haskell and F# have a first function which returns the first value in a tuple.

In Haskell (on codepad):

map fst [(1,2), (2,3), (3,5), (4,2)]

=> [1,2,3,4]

In F# (on tryfsharp):

List.map fst [(1,2); (2,3); (3,5); (4,2)];;

val it : int list = [1; 2; 3; 4]

There you have it a few simple examples of mapping in Haskell and F#.

On COUNT(*)

"The discovery of truth is prevented more effectively, not by the false appearance things present and which mislead into error, not directly by weakness of the reasoning powers, but by preconceived opinion, by prejudice."
-- Arthur Schopenhauer

I made a discovery today, much to my chagrin it seems that COUNT returns 0 only when it is presented an empty table, not when it is presented an empty group.  It seems that I am not the first to make this discovery and I do not think I will be the last.

Here are some examples to illustrate what I am talking about:

SELECT *
  FROM dbo.tbl
;

(empty)

SELECT COUNT(*)
  FROM dbo.tbl
;

COLUMN_0
0

SELECT COUNT(*)
  FROM dbo.tbl
  GROUP BY value
;

(empty)

SELECT COUNT(*) OVER (PARTITION BY value)
  FROM dbo.tbl
;

(empty)

SELECT COUNT(value)
  FROM dbo.tbl
;

COLUMN_0
0

SELECT COUNT(value)
  FROM dbo.tbl
  GROUP BY value
;


(empty)

The above can be found on SQL Fiddle.

Letter Occurrence

"Machines take me by surprise with great frequency."
-- Alan Turning

I do a code kata a day to keep unemployment away.  Well I actually do it to learn F#, but the previous statement sounds better.  Recently I was on Rosetta Code looking for an idea and came across a letter frequency counting problem.

The problem is simple:

Given a string, count how many times each letter occurs in said string.

Not too hard of a problem, but how do we "best" solve this with a functional language?

What I would like to do, would be to group each letter together and then count the number of occurrences of each letter in the group.  To make it easier to test I'll place the results into a Map with the key being the letter and the value being the number of occurrences of the letter in the input string.

In F# if you want to do a Group By you'll have to use Seq.groupby which takes a function (in this case we can use the identity since we are not doing anything with the elements of the string) and a sequence (in this case the string).  It gives you a sequence of keys and the complete sequence of values (e.g. A * seq AAAA).  Once we have that we just need to make a tuple with the value as a string and the number of times the value occurs, we can use Seq.map to do this.  Last we just need to place these tuples into a Map.

let occurs str =

  str 

      |> Seq.groupBy (fun c -> c) 

      |> Seq.map (fun (c, n) -> (c.ToString(), Seq.length n)) 

      |> Map.ofSeq

With this simple function we can now count the number of times a letter occurs in a string (similar to the Hadoop Hello World type program).

Below you'll find the full code from the kata including the unit tests.  For comparison I did the same kata again in Javascript (again and always with unit tests).

In F# (with FsUnit):

open NUnit.Framework

open FsUnit

let occurs str =

  str |> Seq.groupBy (fun c -> c) |> Seq.map (fun (c, n) -> (c.ToString(), Seq.length n)) |> Map.ofSeq

[<Test>]

let ``Validate that "A" has 1 A occurence`` () =

  let result = Map.empty.Add("A", 1)

  occurs "A" |> should equal result

[<Test>]

let ``Validate that "AAA" has 3 A occurence`` () =

  let result = Map.empty.Add("A", 3)

  occurs "AAA" |> should equal result

[<Test>]

let ``Validate that "AB" has 1 A occurence and 1 B occurence`` () =

  let result = Map.empty.Add("A", 1).Add("B", 1)

  occurs "AB" |> should equal result

[<Test>]

let ``Validate that "ABBBCCA" has 2 A occurence, 3 B occurence, and 2 C`` () =

  let result = Map.empty.Add("A", 2).Add("B", 3).Add("C", 2)

  occurs "ABBBCCA" |> should equal result

You can find the F# source code here.

In Javascript (with QUnit):

function occurs(letters) {

          var countletters = {}, index = 0;

         

          return function counter() {

                   if (letters.length <= index) {

                     return countletters;

                   }

                  

                   return function incrument() {

                       var letter = letters[index++];

                             countletters[letter] ? countletters[letter] += 1 : countletters[letter] = 1;

                             return counter();

                   }();

          }();

}

test("Count a string with 1 A", function () {

          var actual, expected = {};

          expected["A"] = 1;

          actual = occurs("A");

          deepEqual(actual, expected);

});

test("Count a string with 2 A", function () {

          var actual, expected = {};

          expected["A"] = 2;

          actual = occurs("AA");

          deepEqual(actual, expected);

});

test("Count a string with 1 A and 1 B", function () {

          var actual, expected = {};

          expected["A"] = 1;

          expected["B"] = 1;

          actual = occurs("AB");

          deepEqual(actual, expected);

});

test("Count a string with 2 A and 2 B", function () {

          var actual, expected = {};

          expected["A"] = 2;

          expected["B"] = 2;

          actual = occurs("ABAB");

          deepEqual(actual, expected);

});

test("Count a string with 2 A and 2 B and 1 C", function () {

          var actual, expected = {};

          expected["A"] = 2;

          expected["B"] = 2;

          expected["C"] = 1;

          actual = occurs("ABCAB");

          deepEqual(actual, expected);

});

You can find the Javascript source code here.

F# FizzBuzz using Functions

"Success is neither magical nor mysterious. Success is the natural consequence of consistently applying the basic fundamentals."
-- Jim Rohn

"When I was young, I had to learn the fundamentals of basketball. You can have all the physical ability in the world, but you still have to know the fundamentals."
-- Michael Jordan

FizzBuzz is one of the most basic programs that is doable in an interview, yet hard enough that it can be used to filter out candidates.  The problem you need to solve is simple.

Print out all of the numbers from 1 to 100.  If a number is divisible by 3 then print out Fizz.  If a number is divisible by 5 then print out Buzz.  If a number is divisible by both 3 and 5 then print out FizzBuzz.

A simple problem which make for a good kata, but deep enough that there are a lot of different ways to solve the problem.  I've been doing an F# kata-a-day for about 6 months now and recently I decided to do FizzBuzz again but to try not to test for 15 directly.  I thought about it a little bit and it hit me.  What I want to do is map a number divisible by 3 to Fizz, number divisible by 5 to Buzz, and if it is divisible by both then map it to both.

I create two function to support my mapping.

let fizzer n =

  if n % 3 = 0 then "Fizz"

  else ""

let buzzer n =

  if n % 5 = 0 then "Buzz"

  else ""

Since I do TDD, I used the following FsUnit test to drive out these two function.

[<Test>]

let ``Validate that 18 is Fizz`` () =

  fizzer 18 |> should equal "Fizz"

[<Test>]

let ``Validate that 4 is not Fizz`` () =

  fizzer 4 |> should equal ""

[<Test>]

let ``Validate that 20 is Buzz`` () =

  buzzer 20 |> should equal "Buzz"

[<Test>]

let ``Validate that 22 is not Buzz`` () =

  buzzer 22 |> should equal ""

Now what I need is a function which will map these two functions.

let fizzBuzzer num =

  let result = [fizzer; buzzer] |> List.map (fun x -> x num) |> List.reduce (fun acc x -> acc + x)

  if result = "" then num.ToString()

  else result

What fizzBuzzer does is map the number given to it against the functions fizzer and buzzer created above.  This gives two results which are then folded using List.reduce.  This gives use four different cases:

1. "" (empty string)
2. "Fizz"
3. "Buzz"
4. "FizzBuzz"

In the case of the empty string what we want to do is return the number given to fizzBuzzer as a string (e.g. fizzBuzzer(2) returns "2").  In order to do that we look at the result from the step above, if it is the first case then we return the number passed in as a string using toString.

There you have it.  FizzBuzz without a direct check for 15!  And it uses higher order functions!

Full code from my 25 min kata is below.  It can also be found on Try F#.

open NUnit.Framework

open FsUnit

let fizzer n =

  if n % 3 = 0 then "Fizz"

  else ""

let buzzer n =

  if n % 5 = 0 then "Buzz"

  else ""

let fizzBuzzer num =

  let result = [fizzer; buzzer] |> List.map (fun x -> x num) |> List.reduce (fun acc x -> acc + x)

  if result = "" then num.ToString()

  else result

[<Test>]

let ``Validate that 3 is Fizz`` () =

  fizzBuzzer 3 |> should equal "Fizz"

[<Test>]

let ``Validate that 9 is Fizz`` () =

  fizzBuzzer 9 |> should equal "Fizz"

[<Test>]

let ``Validate that 5 is Buzz`` () =

  fizzBuzzer 5 |> should equal "Buzz"

[<Test>]

let ``Validate that 25 is Buzz`` () =

  fizzBuzzer 25 |> should equal "Buzz"

[<Test>]

let ``Validate that 2 is 2`` () =

  fizzBuzzer 2 |> should equal "2"

[<Test>]

let ``Validate that 15 is FizzBuzz`` () =

  fizzBuzzer 15 |> should equal "FizzBuzz"

[<Test>]

let ``Validate that 30 is FizzBuzz`` () =

  fizzBuzzer 30 |> should equal "FizzBuzz"

[<Test>]

let ``Validate that 18 is Fizz`` () =

  fizzer 18 |> should equal "Fizz"

[<Test>]

let ``Validate that 4 is not Fizz`` () =

  fizzer 4 |> should equal ""

[<Test>]

let ``Validate that 20 is Buzz`` () =

  buzzer 20 |> should equal "Buzz"

[<Test>]

let ``Validate that 22 is not Buzz`` () =

  buzzer 22 |> should equal ""