A Tale of Two FizzBuzzes in Haskell - Part 2

"It is a far, far better thing that I do, than I have ever done; it is a far, far better rest that I go to than I have ever known."

-- Charles Dickens, A Tale of Two Cities


As I've stated before, I like the FizzBuzz kata.  FizzBuzz is one of those rare things that is very easy to understand and yet provides tons of depth once you really think about it.

Welcome to part two, last time we did FizzBuzz using TDD,  this time we'll do it again but will use the Transformation Priority Premise to guide our TDD.

In TPP, Uncle Bob give us the following order for our transformations to our code:

1. ({}–>nil) no code at all->code that employs nil
2. (nil->constant)
3. (constant->constant+) a simple constant to a more complex constant
4. (constant->scalar) replacing a constant with a variable or an argument
5. (statement->statements) adding more unconditional statements.
6. (unconditional->if) splitting the execution path
7. (scalar->array)
8. (array->container)
9. (statement->recursion)
10. (if->while)
11. (expression->function) replacing an expression with a function or algorithm
12. (variable->assignment) replacing the value of a variable.

The idea being that a transformation that is higher should always take place instead of one that is lower.  If this idea is followed our code will be cleaner.

Let's apply the Transformation Priority Premise to FizzBuzz using Haskell and HUnit.

3 => "Fizz"

Failing Test Case

import Test.HUnit

t3 = TestCase (assertEqual "3 is Fizz" "Fizz" (fizzBuzzer 3))

tests = TestList [TestLabel "3 is Fizz" t3]


[1 of 1] Compiling Main             ( fizzBuzz.hs, interpreted )

fizzBuzz.hs:3:48: Not in scope: `fizzBuzzer'
Failed, modules loaded: none.

Pass

Using the following rules:

({}–>nil) no code at all->code that employs nil
(nil->constant)

import Test.HUnit

fizzBuzzer::Int->String

fizzBuzzer n = "Fizz"

t3 = TestCase (assertEqual "3 is Fizz" "Fizz" (fizzBuzzer 3))

tests = TestList [TestLabel "3 is Fizz" t3]

*Main> runTestTT tests

Cases: 1  Tried: 0  Errors: 0  Failures: 0

Cases: 1  Tried: 1  Errors: 0  Failures: 0
Counts {cases = 1, tried = 1, errors = 1, failures = 0}

5 => "Buzz"

Failing Test Case

import Test.HUnit

fizzBuzzer::Int->String
fizzBuzzer n = "Fizz"

t3 = TestCase (assertEqual "3 is Fizz" "Fizz" (fizzBuzzer 3))

t5 = TestCase (assertEqual "5 is Buzz" "Buzz" (fizzBuzzer 5))

tests = TestList [TestLabel "3 is Fizz" t3
                        ,TestLabel "5 is Buzz" t5]

*Main> runTestTT tests

Cases: 2  Tried: 0  Errors: 0  Failures: 0

Cases: 2  Tried: 1  Errors: 0  Failures: 0

                                       
### Failure in: 1:5 is Buzz
5 is Buzz
expected: "Buzz"
 but got: "Fizz"
Cases: 2  Tried: 2  Errors: 0  Failures: 1
Counts {cases = 2, tried = 2, errors = 0, failures = 1}

Pass

Using the following rules:

(constant->constant+) a simple constant to a more complex constant

import Test.HUnit

fizzBuzzer::Int->String

fizzBuzzer 3 = "Fizz"

fizzBuzzer 5 = "Buzz"

t3 = TestCase (assertEqual "3 is Fizz" "Fizz" (fizzBuzzer 3))

t5 = TestCase (assertEqual "5 is Buzz" "Buzz" (fizzBuzzer 5))

tests = TestList [TestLabel "3 is Fizz" t3

                        ,TestLabel "5 is Buzz" t5]

*Main> runTestTT tests

Cases: 2  Tried: 0  Errors: 0  Failures: 0

Cases: 2  Tried: 1  Errors: 0  Failures: 0
Cases: 2  Tried: 2  Errors: 0  Failures: 0
Counts {cases = 2, tried = 2, errors = 0, failures = 0}

25 => "Buzz"

Failing Test Case

import Test.HUnit

fizzBuzzer::Int->String
fizzBuzzer 3 = "Fizz"
fizzBuzzer 5 = "Buzz"

t3 = TestCase (assertEqual "3 is Fizz" "Fizz" (fizzBuzzer 3))

t5 = TestCase (assertEqual "5 is Buzz" "Buzz" (fizzBuzzer 5))
t25 = TestCase (assertEqual "25 is Buzz" "Buzz" (fizzBuzzer 25))

tests = TestList [TestLabel "3 is Fizz" t3
                        ,TestLabel "5 is Buzz" t5
                    ,TestLabel "25 is Buzz" t25]

*Main> runTestTT tests

Cases: 3  Tried: 0  Errors: 0  Failures: 0

Cases: 3  Tried: 1  Errors: 0  Failures: 0
Cases: 3  Tried: 2  Errors: 0  Failures: 0

                                         

### Error in:   2:25 is Buzz

fizzBuzz.hs:(4,1)-(5,21): Non-exhaustive patterns in function Main.fizzBuzzer

Cases: 3  Tried: 3  Errors: 1  Failures: 0

Counts {cases = 3, tried = 3, errors = 1, failures = 0}

Pass

Using the following rules:

(constant->scalar) replacing a constant with a variable or an argument


import Test.HUnit

fizzBuzzer::Int->String
fizzBuzzer 3 = "Fizz"
fizzBuzzer n = "Buzz"

t3 = TestCase (assertEqual "3 is Fizz" "Fizz" (fizzBuzzer 3))

t5 = TestCase (assertEqual "5 is Buzz" "Buzz" (fizzBuzzer 5))
t25 = TestCase (assertEqual "25 is Buzz" "Buzz" (fizzBuzzer 25))

tests = TestList [TestLabel "3 is Fizz" t3
                       ,TestLabel "5 is Buzz" t5
                   ,TestLabel "25 is Buzz" t25]

*Main> runTestTT tests

Cases: 3  Tried: 0  Errors: 0  Failures: 0

Cases: 3  Tried: 1  Errors: 0  Failures: 0
Cases: 3  Tried: 2  Errors: 0  Failures: 0
                                          
Cases: 3  Tried: 3  Errors: 0  Failures: 0
Counts {cases = 3, tried = 3, errors = 0, failures = 0}

9 => "Fizz"

Failing Test Case

import Test.HUnit

fizzBuzzer::Int->String

fizzBuzzer 3 = "Fizz"

fizzBuzzer n = "Buzz"

t3 = TestCase (assertEqual "3 is Fizz" "Fizz" (fizzBuzzer 3))

t9 = TestCase (assertEqual "9 is Fizz" "Fizz" (fizzBuzzer 9))

t5 = TestCase (assertEqual "5 is Buzz" "Buzz" (fizzBuzzer 5))

t25 = TestCase (assertEqual "25 is Buzz" "Buzz" (fizzBuzzer 25))

tests = TestList [TestLabel "3 is Fizz" t3

                       ,TestLabel "9 is Fizz" t9

                       ,TestLabel "5 is Buzz" t5

                   ,TestLabel "25 is Buzz" t25]

*Main> runTestTT tests

Cases: 4  Tried: 0  Errors: 0  Failures: 0
Cases: 4  Tried: 1  Errors: 0  Failures: 0
                                          
### Failure in: 1:9 is Fizz
9 is Fizz
expected: "Fizz"
 but got: "Buzz"


Cases: 4  Tried: 2  Errors: 0  Failures: 1

Cases: 4  Tried: 3  Errors: 0  Failures: 1
                                          
Cases: 4  Tried: 4  Errors: 0  Failures: 1
Counts {cases = 4, tried = 4, errors = 0, failures = 1}

Pass

Using the following rules:

(unconditional->if) splitting the execution path

import Test.HUnit

fizzBuzzer::Int->String
fizzBuzzer n
  | (==) (mod n 5) 0 = "Buzz"
  | otherwise = "Fizz"

t3 = TestCase (assertEqual "3 is Fizz" "Fizz" (fizzBuzzer 3))
t9 = TestCase (assertEqual "9 is Fizz" "Fizz" (fizzBuzzer 9))

t5 = TestCase (assertEqual "5 is Buzz" "Buzz" (fizzBuzzer 5))
t25 = TestCase (assertEqual "25 is Buzz" "Buzz" (fizzBuzzer 25))

tests = TestList [TestLabel "3 is Fizz" t3
                        ,TestLabel "9 is Fizz" t9
                        ,TestLabel "5 is Buzz" t5
                    ,TestLabel "25 is Buzz" t25]

*Main> runTestTT tests

Cases: 4  Tried: 0  Errors: 0  Failures: 0

Cases: 4  Tried: 1  Errors: 0  Failures: 0
Cases: 4  Tried: 2  Errors: 0  Failures: 0
Cases: 4  Tried: 3  Errors: 0  Failures: 0
                                       
Cases: 4  Tried: 4  Errors: 0  Failures: 0
Counts {cases = 4, tried = 4, errors = 0, failures = 0}

2 => "2"

Failing Test Case

import Test.HUnit

fizzBuzzer::Int->String
fizzBuzzer n
  | (==) (mod n 5) 0 = "Buzz"
  | otherwise = "Fizz"

t2 = TestCase (assertEqual "2 is 2" "2" (fizzBuzzer 2))

t3 = TestCase (assertEqual "3 is Fizz" "Fizz" (fizzBuzzer 3))
t9 = TestCase (assertEqual "9 is Fizz" "Fizz" (fizzBuzzer 9))

t5 = TestCase (assertEqual "5 is Buzz" "Buzz" (fizzBuzzer 5))
t25 = TestCase (assertEqual "25 is Buzz" "Buzz" (fizzBuzzer 25))

tests = TestList [TestLabel "2 is 2" t2
                        ,TestLabel "3 is Fizz" t3
                        ,TestLabel "9 is Fizz" t9
                        ,TestLabel "5 is Buzz" t5
                    ,TestLabel "25 is Buzz" t25]

*Main> runTestTT tests

Cases: 5  Tried: 0  Errors: 0  Failures: 0

                                       
### Failure in: 0:2 is 2
2 is 2
expected: "2"
 but got: "Fizz"


Cases: 5  Tried: 1  Errors: 0  Failures: 1

Cases: 5  Tried: 2  Errors: 0  Failures: 1
Cases: 5  Tried: 3  Errors: 0  Failures: 1
Cases: 5  Tried: 4  Errors: 0  Failures: 1
                                       
Cases: 5  Tried: 5  Errors: 0  Failures: 1
Counts {cases = 5, tried = 5, errors = 0, failures = 1}

Pass

Using the following rules:

(constant->constant+) a simple constant to a more complex constant
(unconditional->if) splitting the execution path

import Test.HUnit

fizzBuzzer::Int->String
fizzBuzzer n
  | (==) (mod n 5) 0 = "Buzz"
  | (==) (mod n 3) 0 = "Fizz"
  | otherwise = show n

t2 = TestCase (assertEqual "2 is 2" "2" (fizzBuzzer 2))

t3 = TestCase (assertEqual "3 is Fizz" "Fizz" (fizzBuzzer 3))
t9 = TestCase (assertEqual "9 is Fizz" "Fizz" (fizzBuzzer 9))

t5 = TestCase (assertEqual "5 is Buzz" "Buzz" (fizzBuzzer 5))
t25 = TestCase (assertEqual "25 is Buzz" "Buzz" (fizzBuzzer 25))

tests = TestList [TestLabel "2 is 2" t2
                        ,TestLabel "3 is Fizz" t3
                        ,TestLabel "9 is Fizz" t9
                        ,TestLabel "5 is Buzz" t5
                    ,TestLabel "25 is Buzz" t25]

*Main> runTestTT tests

Cases: 5  Tried: 0  Errors: 0  Failures: 0
Cases: 5  Tried: 1  Errors: 0  Failures: 0
Cases: 5  Tried: 2  Errors: 0  Failures: 0
Cases: 5  Tried: 3  Errors: 0  Failures: 0
Cases: 5  Tried: 4  Errors: 0  Failures: 0
                                       
Cases: 5  Tried: 5  Errors: 0  Failures: 0
Counts {cases = 5, tried = 5, errors = 0, failures = 0}

Refactor

We now have a repeating pattern, let's refactor it our using the following rule:

(constant->constant+) a simple constant to a more complex constant

import Test.HUnit

xzzer n = (\x -> (==) (mod x n) 0)

fizzBuzzer::Int->String
fizzBuzzer n
  | xzzer 3 = "Fizz"
  | xzzer 5 = "Buzz"
  | otherwise = show n

t2 = TestCase (assertEqual "2 is 2" "2" (fizzBuzzer 2))

t3 = TestCase (assertEqual "3 is Fizz" "Fizz" (fizzBuzzer 3))
t9 = TestCase (assertEqual "9 is Fizz" "Fizz" (fizzBuzzer 9))

t5 = TestCase (assertEqual "5 is Buzz" "Buzz" (fizzBuzzer 5))
t25 = TestCase (assertEqual "25 is Buzz" "Buzz" (fizzBuzzer 25))

tests = TestList [TestLabel "2 is 2" t2
                       ,TestLabel "3 is Fizz" t3
                       ,TestLabel "9 is Fizz" t9
                       ,TestLabel "5 is Buzz" t5
,TestLabel "25 is Buzz" t25]

*Main> runTestTT tests

Cases: 5  Tried: 0  Errors: 0  Failures: 0
Cases: 5  Tried: 1  Errors: 0  Failures: 0
Cases: 5  Tried: 2  Errors: 0  Failures: 0
Cases: 5  Tried: 3  Errors: 0  Failures: 0
Cases: 5  Tried: 4  Errors: 0  Failures: 0
                                       
Cases: 5  Tried: 5  Errors: 0  Failures: 0
Counts {cases = 5, tried = 5, errors = 0, failures = 0}

15 => "FizzBuzz"

Failing Test Case

import Test.HUnit

xzzer n = (\x -> (==) (mod x n) 0)

fizzBuzzer::Int->String
fizzBuzzer n
  | xzzer 3 = "Fizz"
  | xzzer 5 = "Buzz"
  | otherwise = show n

t2 = TestCase (assertEqual "2 is 2" "2" (fizzBuzzer 2))

t3 = TestCase (assertEqual "3 is Fizz" "Fizz" (fizzBuzzer 3))
t9 = TestCase (assertEqual "9 is Fizz" "Fizz" (fizzBuzzer 9))

t5 = TestCase (assertEqual "5 is Buzz" "Buzz" (fizzBuzzer 5))
t25 = TestCase (assertEqual "25 is Buzz" "Buzz" (fizzBuzzer 25))

t15 = TestCase (assertEqual "15 is FizzBuzz" "FizzBuzz" (fizzBuzzer 15))

tests = TestList [TestLabel "2 is 2" t2
                        ,TestLabel "3 is Fizz" t3
                        ,TestLabel "9 is Fizz" t9
                        ,TestLabel "5 is Buzz" t5
                    ,TestLabel "25 is Buzz" t25
                    ,TestLabel "15 is FizzBuzz" t15]


Prelude> :reload
[1 of 1] Compiling Main             ( fizzBuzz.hs, interpreted )


fizzBuzz.hs:7:5:

    Couldn't match expected type `Bool' with actual type `a0 -> Bool'
    In the return type of a call of `xzzer'
    In the expression: xzzer 3
    In a stmt of a pattern guard for
                 an equation for `fizzBuzzer':
        xzzer 3
Failed, modules loaded: none.

Pass

Using the following rules:

(constant->constant+) a simple constant to a more complex constant

import Test.HUnit

fizzBuzzer::Int->String
fizzBuzzer n
    | result == "" = show n
| otherwise    = result
  where
    xzzer n = (\x -> (==) (mod x n) 0)
    fizzer x = if xzzer 3 x then "Fizz" else ""
    buzzer x = if xzzer 5 x then "Buzz" else ""
    result = foldl (\acc x -> acc ++ x n) "" [fizzer, buzzer]


t2 = TestCase (assertEqual "2 is 2" "2" (fizzBuzzer 2))

t3 = TestCase (assertEqual "3 is Fizz" "Fizz" (fizzBuzzer 3))
t9 = TestCase (assertEqual "9 is Fizz" "Fizz" (fizzBuzzer 9))

t5 = TestCase (assertEqual "5 is Buzz" "Buzz" (fizzBuzzer 5))
t25 = TestCase (assertEqual "25 is Buzz" "Buzz" (fizzBuzzer 25))

t15 = TestCase (assertEqual "15 is FizzBuzz" "FizzBuzz" (fizzBuzzer 15))

tests = TestList [TestLabel "2 is 2" t2
                       ,TestLabel "3 is Fizz" t3
                      ,TestLabel "9 is Fizz" t9
                      ,TestLabel "5 is Buzz" t5
                  ,TestLabel "25 is Buzz" t25
                  ,TestLabel "15 is FizzBuzz" t15]

*Main> runTestTT tests

Cases: 6  Tried: 0  Errors: 0  Failures: 0

Cases: 6  Tried: 1  Errors: 0  Failures: 0
Cases: 6  Tried: 2  Errors: 0  Failures: 0
Cases: 6  Tried: 3  Errors: 0  Failures: 0
Cases: 6  Tried: 4  Errors: 0  Failures: 0
Cases: 6  Tried: 5  Errors: 0  Failures: 0
                                       
Cases: 6  Tried: 6  Errors: 0  Failures: 0
Counts {cases = 6, tried = 6, errors = 0, failures = 0}

More

Let's add in a few more test cases just to show we have all the bases covered.

import Test.HUnit

fizzBuzzer::Int->String
fizzBuzzer n
    | result == "" = show n
| otherwise    = result
  where
    xzzer n = (\x -> (==) (mod x n) 0)
    fizzer x = if xzzer 3 x then "Fizz" else ""
    buzzer x = if xzzer 5 x then "Buzz" else ""
    result = foldl (\acc x -> acc ++ x n) "" [fizzer, buzzer]


t2 = TestCase (assertEqual "2 is 2" "2" (fizzBuzzer 2))
t4 = TestCase (assertEqual "4 is 4" "4" (fizzBuzzer 4))

t3 = TestCase (assertEqual "3 is Fizz" "Fizz" (fizzBuzzer 3))
t9 = TestCase (assertEqual "9 is Fizz" "Fizz" (fizzBuzzer 9))

t5 = TestCase (assertEqual "5 is Buzz" "Buzz" (fizzBuzzer 5))
t25 = TestCase (assertEqual "25 is Buzz" "Buzz" (fizzBuzzer 25))

t15 = TestCase (assertEqual "15 is FizzBuzz" "FizzBuzz" (fizzBuzzer 15))
t30 = TestCase (assertEqual "30 is FizzBuzz" "FizzBuzz" (fizzBuzzer 30))

tests = TestList [TestLabel "2 is 2" t2
                        ,TestLabel "4 is 4" t4
                        ,TestLabel "3 is Fizz" t3
                        ,TestLabel "9 is Fizz" t9
                        ,TestLabel "5 is Buzz" t5
                    ,TestLabel "25 is Buzz" t25
                    ,TestLabel "15 is FizzBuzz" t15
                       ,TestLabel "30 is FizzBuzz" t30]

*Main> runTestTT tests

Cases: 8  Tried: 0  Errors: 0  Failures: 0
Cases: 8  Tried: 1  Errors: 0  Failures: 0
Cases: 8  Tried: 2  Errors: 0  Failures: 0
Cases: 8  Tried: 3  Errors: 0  Failures: 0
Cases: 8  Tried: 4  Errors: 0  Failures: 0
Cases: 8  Tried: 5  Errors: 0  Failures: 0
Cases: 8  Tried: 6  Errors: 0  Failures: 0
Cases: 8  Tried: 7  Errors: 0  Failures: 0
                                       
Cases: 8  Tried: 8  Errors: 0  Failures: 0
Counts {cases = 8, tried = 8, errors = 0, failures = 0}

Conclusion

We now have a FizzBuzz that we can show to our mom, assuming that our mom knows how to program and understands Haskell (my mom does not hit into either of those categories).  I am sure someone with more experience in TPP and Haskell could do better, but I believe this is fairly good.

A Tale of Two FizzBuzzes in Haskell - Part 1

"It was the best of times, it was the worst of times, it was the age of wisdom, it was the age of foolishness, it was the epoch of belief, it was the epoch of incredulity, it was the season of Light, it was the season of Darkness, it was the spring of hope, it was the winter of despair, we had everything before us, we had nothing before us, we were all going direct to Heaven, we were all going direct the other way--in short, the period was so far like the present period, that some of its noisiest authorities insisted on its being received, for good or for evil, in the superlative degree of comparison only."

-- Charles Dickens, A Tale of Two Cities

I enjoy the FizzBuzz kata.  I find that it offers endless amounts of flexibility, but yet it is very simple to understand and yet still has some complexity to it.

TDD

Note when doing TDD, you write the test case first and have it fail before you write the code to pass it, I will not be showing that step.

Case 1: x == 3 -> "Fizz"

import Test.HUnit

fizzBuzzer::Int->String

fizzBuzzer x

  | ((==) x 3) = "Fizz"

t3 = TestCase (assertEqual "3 is Fizz" "Fizz" (fizzBuzzer 3))

tests = TestList [TestLabel "3 is Fizz" t3]

*Main> runTestTT tests

Cases: 1  Tried: 0  Errors: 0  Failures: 0

Case 2: x % 3 == 0 -> "Fizz"

import Test.HUnit

fizzBuzzer::Int->String

fizzBuzzer x

  | (mod x 3 == 0) = "Fizz"

t3 = TestCase (assertEqual "3 is Fizz" "Fizz" (fizzBuzzer 3))

t6 = TestCase (assertEqual "6 is Fizz" "Fizz" (fizzBuzzer 6))

tests = TestList [TestLabel "3 is Fizz" t3

                      ,TestLabel "6 is Fizz" t6]

*Main> runTestTT tests

Cases: 2  Tried: 0  Errors: 0  Failures: 0

Cases: 2  Tried: 1  Errors: 0  Failures: 0

Case 3: x % 3 != 0 -> "x" when x = 2

import Test.HUnit

fizzBuzzer::Int->String

fizzBuzzer x

  | (mod x 3 == 0) = "Fizz"

  | otherwise      = show x

t3 = TestCase (assertEqual "3 is Fizz" "Fizz" (fizzBuzzer 3))

t6 = TestCase (assertEqual "6 is Fizz" "Fizz" (fizzBuzzer 6))

t2 = TestCase (assertEqual "2 is 2" "2" (fizzBuzzer 2))

tests = TestList [TestLabel "3 is Fizz" t3

                      ,TestLabel "6 is Fizz" t6

                      ,TestLabel "2 is 2" t2]

*Main> runTestTT tests

Cases: 3  Tried: 0  Errors: 0  Failures: 0

Cases: 3  Tried: 1  Errors: 0  Failures: 0
Cases: 3  Tried: 2  Errors: 0  Failures: 0

Case 4: x % 3 != 0 -> "x" when x = 4

This is a interesting test case since the code already passes it.

import Test.HUnit

fizzBuzzer::Int->String

fizzBuzzer x

  | (mod x 3 == 0) = "Fizz"

  | otherwise      = show x

t3 = TestCase (assertEqual "3 is Fizz" "Fizz" (fizzBuzzer 3))

t6 = TestCase (assertEqual "6 is Fizz" "Fizz" (fizzBuzzer 6))

t2 = TestCase (assertEqual "2 is 2" "2" (fizzBuzzer 2))

t4 = TestCase (assertEqual "4 is 4" "4" (fizzBuzzer 4))

tests = TestList [TestLabel "3 is Fizz" t3

                      ,TestLabel "6 is Fizz" t6

                      ,TestLabel "2 is 2" t2

                      ,TestLabel "4 is 4" t4]

*Main> runTestTT tests

Cases: 4  Tried: 0  Errors: 0  Failures: 0

Cases: 4  Tried: 1  Errors: 0  Failures: 0
Cases: 4  Tried: 2  Errors: 0  Failures: 0
Cases: 4  Tried: 3  Errors: 0  Failures: 0

Case 5: x == 5 -> "Buzz"

We can use the mod if we want but we'll have to live with breaking strict TDD.

import Test.HUnit

fizzBuzzer::Int->String

fizzBuzzer x

  | (mod x 3 == 0) = "Fizz"

  | (mod x 5 == 0) = "Buzz"

  | otherwise      = show x

t3 = TestCase (assertEqual "3 is Fizz" "Fizz" (fizzBuzzer 3))

t6 = TestCase (assertEqual "6 is Fizz" "Fizz" (fizzBuzzer 6))

t2 = TestCase (assertEqual "2 is 2" "2" (fizzBuzzer 2))

t4 = TestCase (assertEqual "4 is 4" "4" (fizzBuzzer 4))

t5 = TestCase (assertEqual "5 is Buzz" "Buzz" (fizzBuzzer 5))

tests = TestList [TestLabel "3 is Fizz" t3

                      ,TestLabel "6 is Fizz" t6

                      ,TestLabel "2 is 2" t2

                      ,TestLabel "4 is 4" t4

                      ,TestLabel "5 is Buzz" t5]

*Main> runTestTT tests

Cases: 5  Tried: 0  Errors: 0  Failures: 0

Cases: 5  Tried: 1  Errors: 0  Failures: 0
Cases: 5  Tried: 2  Errors: 0  Failures: 0
Cases: 5  Tried: 3  Errors: 0  Failures: 0
Cases: 5  Tried: 4  Errors: 0  Failures: 0

Case 6: x % 5 == 0 -> "Buzz"

Again we already have the code in place to pass this test case.

import Test.HUnit

fizzBuzzer::Int->String

fizzBuzzer x

  | (mod x 3 == 0) = "Fizz"

  | (mod x 5 == 0) = "Buzz"

  | otherwise      = show x

t3 = TestCase (assertEqual "3 is Fizz" "Fizz" (fizzBuzzer 3))

t6 = TestCase (assertEqual "6 is Fizz" "Fizz" (fizzBuzzer 6))

t2 = TestCase (assertEqual "2 is 2" "2" (fizzBuzzer 2))

t4 = TestCase (assertEqual "4 is 4" "4" (fizzBuzzer 4))

t5 = TestCase (assertEqual "5 is Buzz" "Buzz" (fizzBuzzer 5))

t25 = TestCase (assertEqual "25 is Buzz" "Buzz" (fizzBuzzer 25))

tests = TestList [TestLabel "3 is Fizz" t3

                      ,TestLabel "6 is Fizz" t6

                      ,TestLabel "2 is 2" t2

                      ,TestLabel "4 is 4" t4

                      ,TestLabel "5 is Buzz" t5

                      ,TestLabel "25 is Buzz" t25]

*Main> runTestTT tests

Cases: 6  Tried: 0  Errors: 0  Failures: 0

Cases: 6  Tried: 1  Errors: 0  Failures: 0
Cases: 6  Tried: 2  Errors: 0  Failures: 0
Cases: 6  Tried: 3  Errors: 0  Failures: 0
Cases: 6  Tried: 4  Errors: 0  Failures: 0
Cases: 6  Tried: 5  Errors: 0  Failures: 0

Case 7: x == 15 -> "FizzBuzz"

We'll break strict TDD and use a mod 15.

import Test.HUnit

fizzBuzzer::Int->String

fizzBuzzer x

  | (mod x 15 == 0) = "FizzBuzz"

  | (mod x 3 == 0) = "Fizz"

  | (mod x 5 == 0) = "Buzz"

  | otherwise      = show x

t3 = TestCase (assertEqual "3 is Fizz" "Fizz" (fizzBuzzer 3))

t6 = TestCase (assertEqual "6 is Fizz" "Fizz" (fizzBuzzer 6))

t2 = TestCase (assertEqual "2 is 2" "2" (fizzBuzzer 2))

t4 = TestCase (assertEqual "4 is 4" "4" (fizzBuzzer 4))

t5 = TestCase (assertEqual "5 is Buzz" "Buzz" (fizzBuzzer 5))

t25 = TestCase (assertEqual "25 is Buzz" "Buzz" (fizzBuzzer 25))

t15 = TestCase (assertEqual "15 is FizzBuzz" "FizzBuzz" (fizzBuzzer 15))

tests = TestList [TestLabel "3 is Fizz" t3

                      ,TestLabel "6 is Fizz" t6

                      ,TestLabel "2 is 2" t2

                      ,TestLabel "4 is 4" t4

                      ,TestLabel "5 is Buzz" t5

                      ,TestLabel "25 is Buzz" t25

                      ,TestLabel "15 is FizzBuzz" t15]

*Main> runTestTT tests

Cases: 7  Tried: 0  Errors: 0  Failures: 0

Cases: 7  Tried: 1  Errors: 0  Failures: 0
Cases: 7  Tried: 2  Errors: 0  Failures: 0
Cases: 7  Tried: 3  Errors: 0  Failures: 0
Cases: 7  Tried: 4  Errors: 0  Failures: 0
Cases: 7  Tried: 5  Errors: 0  Failures: 0
Cases: 7  Tried: 6  Errors: 0  Failures: 0

Case 8: x % 15 == 0 -> "FizzBuzz"

Again, this test case already passes.

import Test.HUnit

fizzBuzzer::Int->String

fizzBuzzer x

  | (mod x 15 == 0) = "FizzBuzz"

  | (mod x 3 == 0) = "Fizz"

  | (mod x 5 == 0) = "Buzz"

  | otherwise      = show x

t3 = TestCase (assertEqual "3 is Fizz" "Fizz" (fizzBuzzer 3))

t6 = TestCase (assertEqual "6 is Fizz" "Fizz" (fizzBuzzer 6))

t2 = TestCase (assertEqual "2 is 2" "2" (fizzBuzzer 2))

t4 = TestCase (assertEqual "4 is 4" "4" (fizzBuzzer 4))

t5 = TestCase (assertEqual "5 is Buzz" "Buzz" (fizzBuzzer 5))

t25 = TestCase (assertEqual "25 is Buzz" "Buzz" (fizzBuzzer 25))

t15 = TestCase (assertEqual "15 is FizzBuzz" "FizzBuzz" (fizzBuzzer 15))

t30 = TestCase (assertEqual "30 is FizzBuzz" "FizzBuzz" (fizzBuzzer 30))

tests = TestList [TestLabel "3 is Fizz" t3

                      ,TestLabel "6 is Fizz" t6

                      ,TestLabel "2 is 2" t2

                      ,TestLabel "4 is 4" t4

                      ,TestLabel "5 is Buzz" t5

                      ,TestLabel "25 is Buzz" t25

                      ,TestLabel "15 is FizzBuzz" t15

                      ,TestLabel "30 is FizzBuzz" t30]

*Main> runTestTT tests

Cases: 8  Tried: 0  Errors: 0  Failures: 0

Cases: 8  Tried: 1  Errors: 0  Failures: 0
Cases: 8  Tried: 2  Errors: 0  Failures: 0
Cases: 8  Tried: 3  Errors: 0  Failures: 0
Cases: 8  Tried: 4  Errors: 0  Failures: 0
Cases: 8  Tried: 5  Errors: 0  Failures: 0
Cases: 8  Tried: 6  Errors: 0  Failures: 0
Cases: 8  Tried: 7  Errors: 0  Failures: 0

Now we have everything in place to prove that the FizzBuzz works.

Next time we'll do the same kata but using the Transformation Priority Premise (TPP).

Maps, Filters, and Folding ... Oh My! OR Yet Another Blog on Higher Order Functions

"Ay me! I see the ruin of my house.
The tiger now hath seized the gentle hind;
Insulting tyranny begins to jut

Upon the innocent and aweless throne.

Welcome destruction, blood, and massacre!
I see, as in a map, the end of all."
-- Shakespeare, Richard III
Act II, Scene IV, Lines 49-54

This is taken from my presentation called, "Maps, Filters, and Folding.  Oh my!" given at the Chicago Code Camp on April 27th, 2013.

f ◦ g

By higher order functions, we are talking about functions that take functions.  In other words we are talking about f ◦ g.

Mapping

Our first higher order function is f : A → B, called the mapping function.

In a mapping function everything in A has a value that it maps to through the function f to B.  Thus we can write f : A → B.

Mapping example - Identity

The identity function takes a value and maps it to the value given.  In other words it does nothing.

C#

var x = new List{1, 2, 3};

var numbers = from number in x
              select number;

F#

let x = [1; 2; 3]

let numbers = List.map (fun n -> n) x

OR

let x = [1; 2; 3]

let numbers = x |> List.map id

Haskell

map (\x -> x) [1, 2, 3]

OR

[x | x <- 2="" 3="" font="">

OR

 map id [1, 2, 3]

C

int* mapIdentity(int* list, int length) {

  int result[length];

  int i;

  for (i = 0; i < length; i++) {

    result[i] = list[i];

  }

  return result;

}

Mapping example - Turtles All the Way Down

Stephen Hawkings in a Brief History of Time gives us the following story:

A well-known scientist once gave a public lecture on astronomy. He described how the earth orbits around the sun and how the sun, in turn, orbits around the center of a vast collection of stars called our galaxy. At the end of the lecture, a little old lady at the back of the room got up and said: "What you have told us is rubbish. The world is really a flat plate supported on the back of a giant tortoise." The scientist gave a superior smile before replying, "What is the tortoise standing on?" "You're very clever, young man, very clever," said the old lady. "But it's turtles all the way down!"

If you want to create a function, which would describe a world in which everything is a Turtle you could use the following.

C#

var x = new List{1, 2, 3};

var numbers = 
  x.Select(t => "turtle");

F#

[1; 2; 3] |> List.map (fun _ -> "turtle")

Haskell

map (\_ -> "turtle") [1, 2, 3]

Mapping example - Shift Letters

Suetonius in The Twelve Caesars gives use the following about Julius Caesar:

If he had anything confidential to say, he wrote it in cipher, that is, by so changing the order of the letters of the alphabet, that not a word could be made out. If anyone wishes to decipher these, and get at their meaning, he must substitute the fourth letter of the alphabet, namely D, for A, and so with the others.

If we wanted to create a simple shifting function we could use the following.

C#

var caesar = 

  String.Concat(

    "DOG".Select(

      c => (char)(c + 13)));

F#

"DOG" 

  |> List.ofSeq

  |> List.map (fun c -> char(int c + 13))

  |> List.toArray

  |> (fun s -> System.String s)

Haskell

map (\c -> chr (ord c + 13)) "DOG"

Filtering

Our second higher order function is f : A → if (f(A)) then B, called filtering.

In filtering, not everything in A which goes through the function f has a value in B.  Thus we say that f filters A into B or f : A → if (f(A)) then B.

Filtering example - Odds only

Say we want a function which will only let Odd values into a club.  We could use the following as a bouncer.

C#

var x = new List{1, 2, 3};

var odd = x.Where(

            (a) => a % 2 == 1);

F#

[1; 2; 3] |> List.filter (fun x -> x % 2 = 1)

Haskell

filter (\x -> mod x 2 == 1) [1, 2, 3]

OR

filter odd [1, 2, 3]

Filtering example - Strings longer than 7

Say you want a function which will only let strings that are greater than 7 in length.

C#

var x = new List{

  "Scarecrow",

  "Tin Man",

  "Cowardly Lion"};

var moreThanSeven = 

  x.Where((a) => a.Length > 7);

F#

["Scarecrow"; "Tin Man"; "Cowardly Lion"]

  |> List.filter (fun x -> String.length x > 7)

Haskell

filter (\x -> length x > 7) 

  ["Scarecrow", "Tin Man", "Cowardly Lion"]

Filtering example - Divisors of 6

In number theory it is common to want to know if some is a divisor of a number.

C#

var x = 

  new List{1, 2, 3, 4, 5};

var divisor = 

  x.Where((a) => 6 % a == 0);

F#

[1..5] |> List.filter (fun x -> 6 % x = 0)

Haskell

filter (\x -> mod 6 x == 0) [1..5]

Folding

Our third and finial higher order function is folding.  Folding is when you have a set of values and you run them through a function f and get one value out of the function, f : A → a.  Max, sum, average, ... are all examples of folding.

Folding example - Sum

A common problem with a set of number is finding the total, this is also called summing.

Since addition is associative, it does not matter if we fold from the left or from the right.  If we were doing subtracts, it would matter.  5 - 2 = 3, but 2 - 5 = -3.

C#

var x = new List{1, 2, 3};

var s = x.Sum();

F#

[1; 2; 3] |> List.fold (fun acc x -> acc + x) 0

OR

[1; 2; 3] |> List.sum

Haskell

foldl (\acc x -> acc + x) 0 [1, 2, 3]

OR

sum [1, 2, 3]

Folding example - Counting

It is funny once you get into really high mathematics you find that a lot the same problems that you study earlier, come up again with fancier names and more abstract ideas.  Combinatorics is a branch of mathematics which is concerned with grouping and counting items.  We can use folding to create a counting function.

C#

var x = new List{1, 2, 3};

var c = x.Count();

F#

[1; 2; 3] |> List.fold (fun acc _ -> acc + 1) 0

OR

[1; 2; 3] |> List.length

Haskell

foldl (\acc _ -> acc + 1) 0 [1, 2, 3]

OR

length [1, 2, 3]

Folding example - Min

It is quite a common problem to want to find the minimum value of a given set.  Again, we can use a folding function to solve this problem.

C#

var x = new List{1, 2, 3};

var m = x.Min();

F#

[1; 2; 3] |> List.fold (

        fun m x -> if m > x then x else m)

      System.Int32.MaxValue

OR

[1; 2; 3] |> List.min

Haskell

foldr1 (\m x -> if m > x then x else m) [1, 2, 3]

OR

minimum [1, 2, 3]

The rest of the presentation has been covered in the following previous blog post:

• Finding Perfect Numbers
• Counting Letter Occurrence
• Finding Islands of Data