F#

The What? and Why? of functional programming

Posted on Updated on

When I talk to fellow programmers about functional programming it’s often about something specific, but occasionally that person will suddenly turn the conversation around and ask “So what actually is functional programming, anyway?”. I will talk about some specific features of FP but I will also cover something more general, a tagline or soundbite with which I could give people an instant sense of the philosophy behind functional programming and how it differs from object-oriented programming. As we will see, however, you can get a lot of the benefits of functional programming even if you don’t program in a function language.

Literally speaking, functional programming means that the basic units of your application (i.e. the bits that you compose together to make a complete program) are functions (as opposed to Object-Oriented Programming when they are classes). However, when it comes to the philosophies of the two, I think we can be a bit broader than that to contrast the two:

The main goal of a code unit in object-oriented / imperative programming is to perform actions

The main goal of a code unit in functional programming is to compute results

Why is this distinction important? It’s why functional programming values concepts such as immutability and purity (which have a whole host of benefits).

Read the rest of this entry »

Property-based testing

Posted on Updated on

Unit testing. We all do it. Some of us even practice TDD (although I wish I had a penny for each time I see a company claiming that they practice TDD when what they actually mean is “We write unit tests.”).

Test Driven Design means that your development is actually driven by your tests. It doesn’t mean that you write unit tests (although that is required), it doesn’t mean that you write your tests first (although that is also required), but it means that the desired behaviour is implemented incrementally, one test at a time. This normally means that, for each cycle of this method, a single test is written and then the simplest possible implementation is written that will make that test pass. After each test is added and passes (along with the rest of the test suite covering that particular piece of functionality) the developer is free to refactor the code–after all, up until this point the code has grown quite organically and is likely of poor quality. This repeated process is often referred to as Red-Green-Refactor: first the test is added and fails (the test is “red”), then the implementation is augmented until the test passes (the test “goes green”) and then the dev can refactor to improve code quality.

There are many, many different aspects to writing tests, each of which has a hand in how readable, maintainable, comprehensive, useful and correct your test suite is. These include (but are far from limited to): black-box / gray-box / white-box philosophy, mocking strategies, outside-in or inside-out…

But one aspect I don’t hear many people talking about (outside of the functional programming community at least) is how you pick your test cases. It might not seem that important–just throw some example data at the test and assert that for each of those inputs the expected output is produced. Simple, right?

A ha, dear reader. Allow me to throw a spanner in the works.

This doesn’t always work (at least, not well). Let’s go for the most basic of examples:

How would you unit test the + operator?

Examples? 1 + 0? 2 + 2? 423798 + 278? Where do you stop? How would a developer, following TDD by the book, incrementally implement that function?

When designing tests it’s often helpful to pretend that the person writing the tests and the person completing the implementation of the function are different people. Let us play the part of the coder who has been tasked with implementing the “add” function as above. The signature of the function is agreed and the tester throws their first test case at us: 0 + 0. So, we dutifully write the most simple case that will solve that:

let add x y = 0

The test passes. Yay! Now, here comes the second test case: 1, 0 which should equal 1. So:

let add x y =
    if x = 1 then 1 else 0

Okay, that’s fine. It’s early days yet! So. 2, 2 = 4?

let add x y = 
    if x = 1 then 1
    elif x = 2 then 4
    else 0

Hmmm, it doesn’t look like we’re being driven towards a real implementation here. Maybe let’s try one more test case?

let add x y = 
    if x = 1 then 1
    elif x = 2 then 4
    elif x = 423798 && y = 278 then 424076
    else 0

No, this isn’t working. We’re solving each case as they come in, but we’re not getting anywhere: the if/else statement is just going to grow and grow and grow. We’re stuck in a loop of: tester adds an example, implementation solves that one particular example.

So, how do you choose your test examples? Wouldn’t it be better if you could randomly generate inputs to your test? It would certainly stop the implementation from devolving into a series of hard-coded values, but then what would you assert? This is something that has fascinated me for a while now.

Allow me to introduce Property-Based Testing.

In this context the word property is used in the mathematical way; a property means some quality, attribute, feature or characteristic that a function, or its input and output, has. In short, property-based testing doesn’t assert what the output is, it instead asserts the the output has some property / characteristic. Sometimes the property you are checking is dependent on the input having some property as well (this may or may not be the same property as you expect to see in the output). An example of this might be:

For any two positive numbers x and y, x + y must be positive

You can see here that we are now able to write an assertion that is true for all inputs to the program. For this particular property–that the output of the function is positive–we have placed a constraint on the input (x and y must be positive). We are now able to automatically generate the input data for our tests because we don’t need to know what the data is in advance.

To see how this might work, let’s write the above property in a more formal language:

For all x, y
where x > 0
and y > 0
it follows that: x + y > 0

It almost looks as if we are now following a Gherkin-style BDD syntax for our tests! Okay, so now we understand what a property is we need to come up with a way of discovering more properties.

Continuing with the mathematical example of addition, your function might have the concept of *identity*. From https://en.wikipedia.org/wiki/Function_(mathematics)#Identity_function, “The unique function over a set X that maps each element to itself is called the identity function for X”, meaning “a function who’s output is always equal to its input”. For addition this is simply “+ 0”, and is a property that we can check.

For all x
it follows that x + 0 = x

There are more mathematical properties that would be useful to check, such as commutativity:

For all x, y:
it follows that x + y = y + x

Associativity:

For all x, y, z
it follows that (x + y) + z = x + (y + z)

Given these properties, it’s now much harder to write an implementation of (+) that is incorrect yet passes all our tests.

This is all very good in theory, but how does this actually work? How do we actually implement this? In part 2 of this series we’ll go through a worked example with something a bit harder than addition: the Diamond Kata.

Classic mashup: An FSharp coding dojo

Posted on Updated on

Yesterday I attended the FSharp Dojo: Picasquez and Velasso at Skills Matter in London.

This dojo is all about manipulating images and creating mashups, like this:

Classic mashup image

Read the rest of this entry »

Be careful with attribute routes in projects with both MVC and WebApi

Posted on Updated on

This is a pretty easy trap to fall into! I have been tearing my hair out recently trying to figure out why, in my pet project website, one of the controllers was not having any routes generated. I was able to inspect the generated routes during debugging by setting a breakpoint after the line

routes.MapMvcAttributeRoutes();

and inspecting the routes object. Sure enough routes for the HomeController and ChatController were there, but nothing for the BlogController. What could it be? Everything appeared to be set up correctly:

[<RoutePrefix "blog">]
type BlogController
    (
    _filterBlogPostsQuery: FilterBlogPostsQuery,
    _getBlogPostQuery: GetBlogPostQuery,
    _getAllBlogPostsQuery: GetAllBlogPostsQuery) =
 
    inherit MySiteController()
        
    [<Route "">]
    member this.Index() =
        task {
            let! posts = _getAllBlogPostsQuery()
 
            return this.View posts
        }

Eventually I figured it out after stumbling across this StackOverflow post: https://stackoverflow.com/questions/25727305/asp-mvc-5-attribute-routing-not-registering-routes/. It turns out that, when you have a project with both WebApi and MVC installed, you have two RoutePrefixAttribute classes and two RouteAttribute classes available; one in System.Web.Http and one in System.Web.Mvc. Make sure you’re referencing the right one!

This was also, perhaps, a consequence of using F#, and the fact that the Visual Studio tooling is not as feature-complete as the other languages; I didn’t get a warning from the compiler that there was a naming clash between these two Attributes, despite the fact that I had both the System.Web.Http and System.Web.Mvc namespaces opened at the top of the file. In the end, removing the System.Web.Http namespace was all that was needed to fix the problem.

Lesson learned. Still, it highlights a fragmentation issue between the Mvc and WebApi teams; one which I hope will be fixed in ASP.NET vNext (I assume this will be the case because MVC and WebApi will now share the same base controller).

SOLID, CQRS and functional dependency injection

Posted on Updated on

I was prompted to write this after reading Mark Seemann’s post (http://blog.ploeh.dk/2014/03/10/solid-the-next-step-is-functional/)

From http://kozmic.net/2012/10/23/ioc-container-solves-a-problem-you-might-not-have-but-its-a-nice-problem-to-have/:

Fol­low­ing Sin­gle Respon­si­bil­ity Prin­ci­ple will lead you down the road of hav­ing plenty of small classes.

Open Close Prin­ci­ple will lead you down the way of encap­su­lat­ing the core logic of each type in it, and then del­e­gat­ing all other work to its depen­den­cies, caus­ing most of those small classes to have mul­ti­ple dependencies.

Read the rest of this entry »

“The missing number” programming exercise

Posted on

This is another entry in the brain teaser / programming exercise / interview question collection. It goes like this:

Imagine a list of consecutive numbers. The list is, however, unsorted and one number is missing. Write a function that finds which number is missing with the constraint that you may only allocate O(1) memory (i.e. the amount of memory you use cannot vary with the size of the list).

The fact that the list is unsorted means that you cannot step through in a pairwise fashion and compare each element of the list to the next to see if they are consecutive. Sure, we could sort the array first but the fact that you cannot allocate memory according to the size of the array means that you cannot create a helper array in the solution and certain sorting algorithms are ruled out. An in-place sorting algorithm such as quicksort would do it, but I don’t think that sorting the array is the best way to go.

What if we sum the list? We’re talking about a sequence of integers, after all. It turns out that there is a linear formula for calculating the sum of a sequence of consecutive integers: sum(1..n) = n(n+1) / 2.

This means that you can work out what the sum of the input list should be; all we must do it actually sum the list and the difference between the two will be the missing number. Our implementation then looks like this:


let findMissing (list : int array) =
    let n = list.Length + 1
    let expectedSum = n * (n + 1) / 2
    let actualSum = Seq.sum list
    
    expectedSum - actualSum

Note the let n = list.Length + 1. We have to add one to the length of the list to get the max element in the list because one element is missing. After that it’s pretty simple!

A functional Fizzbuzz

Posted on Updated on

After reading Scott Wlashin’s post (http://fsharpforfunandprofit.com/posts/railway-oriented-programming-carbonated/) on writing FizzBuzz in a more functional style and with the ability to have more rules (other than 3 => fizz, 5 => buzz, etc) I decided to give it a go myself. This represents the most idiomatic F# I could come up with, and I think it reads pretty well. It uses partial application, list operations, shorthand match-expressions-as-functions and option types.

let carbonate rules i =    
    rules
    |> List.choose (fun (divisor, replacement) ->
        if i % divisor = 0 then Some replacement else None)
    |> function [] -> string i | list -> String.concat "" list
        
let carbonateAll rules = List.map (carbonate rules)
    
let fizzbuzzbazz = carbonateAll [3, "fizz"; 5, "buzz"; 7, "bazz"]

fizzbuzzbazz [100..110] |> printfn "%A"

See if you can follow how it works.