wiki

Codit Wiki

Loading information... Please wait.

Codit Blog

Posted on Wednesday, October 25, 2017 1:44 PM

Stijn Moreels by Stijn Moreels

One of the first questions people sometimes ask me about functional programming, is the question about readability. It was a question I had myself when I started with learning functional concepts.

Readability

Now, before moving on; the term “readability” is something very subjective and yet we can define some common grounds. So, it’s not that easy to find something that everyone agrees on about readability.

Single-Letter Values and Functions

The first thing I (and maybe many before and after me) discovered was that the rules of naming conventions in an object-oriented language couldn’t be entirely used within a functional environment.

Functional programmers have this habit of giving values and functions very short names. So short that it only consists of a single letter. If we use this habit in an object-oriented language; this is almost always a bad practice (maybe not a for-loop with an aggregated index?).

So, why is this different in a functional environment?

The answer to this can be many things I guess; one of the things that comes to mind is that in a functional environment, you will very often write functions that can be used for any type (generic). Naming such values and functions can be difficult. Should we name it “value”?

In functional languages, the x is most of the time used as this “value”. Strangely, by using x I found the code a lot clearer. So, for values: x, y and z for functions: f, g and h. (Note that these letters are the same as we use in mathematics.)

When we talk about multiple values, we add and trailing 's'; like xs.

Ok, look for example at this following “bind” function for the Either Monad (Rop):

We have written the values explicitly like we would do in an imperative scenario. Now look at the following:

Most of all in the infix operator, the most important part is that we clearly see that the arguments passed in to the “bind” function are flipped. This was something we could quite see immediately in the first example.

After a while, when you see an f somewhere; you automatically understand it’s a function, just like x is some “value”.

Now, I’m not going to state anything; but in my personal opinion, the second example shows more what’s going on with less explicit names. We reach a higher level of readability by abstracting our names, rather strange at first.

Partially Applied Functions

One of the powerful concepts in functional languages that I really miss in object-oriented languages (without off course custom-made functionality like Extension Methods in C#); is the concept of Partial Application. This concept describes the idea that if you send an argument to a function, you get back a function with the remaining arguments. This concept is very strong because now we can decompose for example a three arguments function into three functions with 1, 2 and 3 arguments respectively.

In practice, this concept can really be of help when declaring problems. In my previous post; I solved the Coin Change Kata. In one the properties, I needed to describe the overall core-functionality. In the assertion, I needed to assert on the sum all the coin values:

The “( )” around the operators “+” and “=” makes sure I get a function back with the remaining argument. I could have written the assertion as the following expression:

And I can understand that in the beginning this will maybe be more understandable for you than the previous example. But please note that, with this anonymous function explicitly specified, we have written a “lot” of code just for addition and equality verification.

I personally think that every functional programmer will refactor this to the first example. Not only because it can be written in fewer characters, but it also expresses more what we’re trying to solve. In imperative languages, we typically assign a value to a variable, and that can be used to another variable, … and without you knowing you’ve created a pipeline. I like this concept very much. I don’t have to assign the next result to a value anymore but can just pass it along to the next function.

“For the Change”
“We need to have each value”
“So we can sum all the values”
“And sum it with the remaining value”
“This should be the same as we expected”

Notice that we always use the verb in the front of the sentence. The action we’re trying to express in code now in front of the line by partially applying one of the arguments and not at the end.
Also note that, when we specify the function explicitly, you can’t read the expression in the second example from top to bottom without moving you’re eyes to the right to see the addition or the equality verification; which is actually the most important part of the line.

This is also one of the reasons I like this form of programming.

Yes, I know that it takes some time to get used to this way of writing functions; but I can assure you. Once you have mastered this technique, you would want this in your favorite object-oriented language as well. (That's one of the reasons I implemented them in the form of Extension Methods).

Infix Operators

One thing that I can’t find a common approach about yet, is the feature of defining your own operators and where to use it. Infix operators can make your code a lot cleaner and more readable; but it can also harm your readability; that’s why it’s probably difficult to define a common approach.

There are already many operators available and by specifying your own operators that looks similar; we can guess what the operator does.

The (|>) pipe operator already exists, and by defining and operators like (||>) or (|>>), we can guess that it has something to do with piping more than one argument, or has something to do with piping and composing.

I didn’t find a global rule to this approach, but I guess it’s something that must be used carefully. If we would define for every function an operator, the code would be less readable.

The (>>=) operator is used for the binding, and so it’s reasonable to define them instead of writing “bind” over-and-over again; because we're actually more interested in WHAT you're trying to bind. The same can be said about the (<*>) operator for the Applicative Bind or the (<!>, <$>) operator for the Mapping. When you see the (<|>) you know it has something to do with Conditional Piping since it pipes in two directions ("if then?"). Some operators are well known and so, are probably never questionable to define.

FsCheck defines (.&.) and (.|.) operators to define the AND and OR of Properties. We already know the boolean operators without the dots leading and trailing them, that’s why it’s easier to know what the infix operator does.

The tricky part is when we use too much operators. I would like to use those operators when we’re changing the data flow in such a way that we can reuse it somewhere else. In those cases it’s probably a good approach to define an infix operator.

Conclusion

This small blog post was for me a small reminder of why I write lesser characters and still make more Declarative Code. It was strange at first to think about it. Most of the time in Object-Oriented Languages; when you talk about smaller names, short-handed operators, … you’re quickly end up with an “anti-pattern” or a bad practice while in Functional Programming this is the right way to do it.

Both imperative and functional programmers are right in my opinion. It’s just a way the language allows us to write clear/clean readable code, because that is really what we want to do.

Categories: Technology
written by: Stijn Moreels

Posted on Thursday, October 5, 2017 11:43 PM

Stijn Moreels by Stijn Moreels

This post will expand on this subject in how I changed my way of writing code and how I became a functional guide.

Introduction

One of the things current Functional Programmers and Enthusiasts come across very often when working in a “mainstream” development environment, is that they must work together with non-functional programmers.

My opinion is that people should not try to convince other people of their opinion, but instead only show you how to do certain things and let the audience decide what they feel most comfortable with.

That’s exactly what happened to me, I worked on a project and because I used functional approaches; people asked me to explain some concepts that I introduced to the rest of the team.

Guidance

Instead of directly talking about Higher-Order Functions, Currying, Monads, Catamorphisms, Endomorphisms, … I decided that I wanted to start with the simplest thing I think was possible to change.

PipeTo

In functional programming, we try to compose all the functions together to create new functions. In imperative languages, we use variables that we can send to the next function instead of sending the result of the first function directly. Piping and Composition are those building blocks.

Note that Composition is the very root of all software development. It always feels to me that functional programming is using this all the way: Everything is an expression, and so, everything can be composed.

My first change was to add an extension method called ‘PipeTo’ in the C# project:

What piping really means to me, is just the order in which you express a value and a function. With piping, you can change that order. Normally we would type the method and then the argument that we want to send to that method.

What piping allows me to do, is to first write the value and then the method.

This simple extension allowed me to write quite powerful expressions:

This is some dummy example of how you can use this approach. Note that I use FsCheck as testing framework and that my test is actually expressed in a single line.

I see two major benefits about this approach:

  1. First, when I use this piping-method, I don’t have to express intermediate variables that sometimes only clutter the actual functionality you want to write. Together with the variables, in C# we must also express the types (if we don’t use ‘var’ everywhere); so, it struck me that I wasted time reading types instead of reading method names.
  1. Second, instead of assigning the result of a method to a variable, we can immediately send it to the next method. This allows us to write in the same order of the data flow like we would express this with intermediate variables.

To go a little deeper on the second benefit. This is what it looks like with the intermediate variables:

We need this intermediate variables to have the data flow from top to bottom (like you read a book). To get rid of the intermediate variabeles without the ‘PipeTo’, we could inline the variables:

But I hope that you find this less readable, that’s why we would extract this in separate variables for the same reason we can use the ‘PipeTo’: to have the data flow from top to bottom but still get that readability.

Maybe

In F#, we use the ‘Option’ type to indicate that a value might be missing. In Haskell we use ‘Maybe’. By default, in C# and other imperative languages, we use ‘null’ to indicate that there’s a value missing.

I’m not going explain fully why because that would lead us to far. There are many posts and books that will explain this you. Even the inventor of the ‘null’ type thought it was the ‘Billion Dolar Mistake’.

So, we use an other type to indicate this missing value. So what?

Well, this is very powerful and a lot more robust because now you now exactly where there’s a value present and where not. C# (for example) doesn’t have any such thing for reference types, but it got a less stronger type called ‘Nullable<>’ for value types.

My second change was to implement some basic functionality of the Maybe Monad.

The ‘Map’ in F# is the ‘Select’ in C#,
the ‘Filter’ in F# is the ‘Where’ in C#.

With this simple implementation, I’ve created some functionality that we can use to start implementing missing values with the ‘Maybe’ type.

The first thing I explained in this type, is the binding functionality. When you show people of endless ‘if’ structures that all would check ‘IsPresent’ on this type, you can show that this is exactly what the ‘Bind’ does:

Normally these ‘if’ structures would check for ‘null’. If we would use our already known practices of refactoring, we would see that there’s a duplication. The thing that’s variable is the action that must be executed when there’s a value. This is exactly what the ‘Bind’ method gets, so we could rewrite it like this:

The other two methods ‘Where’ and ‘Select’ must be familiar to you if you know LINQ. It’s strange to see that experienced C# developers know the functionality of LINQ but aren’t yet using the concepts behind LINQ in their own design. LINQ is functional programming.

The ‘Select’ takes the value from the ‘Maybe’ instance (if there is one) and execute a method that accepts this value. The return of the ‘Select’ is then a new ‘Maybe’ instance with the result of the just executed method.

The ‘Where’ takes a predicate and will return a ‘Maybe’ instance if the value is presents and the predicate holds for the value inside the ‘Maybe’.

This type itself isn’t functional, but what we do with it is; that’ why I think it’s also good first step into functional programming in C#.

 Extensions

I showed some examples of how we can achieve a more functional approach in an object-oriented language like C#. We can extend this idea and come up with even more extensions:

The first ones are probably the simplest. We define a foreach loop that we can use to run through a list of items and execute a (side-effect/dead-end) function on each one. We also define a ‘Tee’ that we can use to send a ‘dead-end’ function inside a pipeline. We don’t have to stop after our method returns ‘void’; we can just continue with the original value.

I also added a ‘Use’ extension to pipe a disposable resource and a ‘Compose’ extension to compose two functions together into a single function.

Now I think it would be a good exercise in functional programming to come up with some changes in your code that uses this extensions!

Conclusion

Instead of directly writing the software in a different language, with different keywords, syntax, practices, … I discovered that people are more comfortable if I use functional approaches first in the languages they're familiar with.

This way, you can clearly see in the same language syntax the “Before” and “After” part.

Remember, don’t try to convince other people of your opinion. Everyone has a different view and ways he or she works and feels comfortable. The only thing you can do, is show how you work and how you see things without blaming other languages or persons because they use a different approach.

Just like everything else, try to be open-minded!

Categories: Technology
written by: Stijn Moreels

Posted on Tuesday, October 3, 2017 9:28 AM

Stijn Moreels by Stijn Moreels

In this post, we will look at how F#'s feature Active Patterns can help build a clear, declarative solution for the Validation of Domain Models. By using a Partial Pattern for each Business Rule, we can clearly see how the input is restricted to verify each rule.

Introduction

The reason I wrote this post was to learn more about F# Active Patterns, and how I can use this for certain, specific problems. They say this feature is a real “killer” feature of the F# environment, so I found it a good exercise to think about how I can use this in my daily practice.

Scott Wlaschin has an amazing blog post series where he writes about this topic. He shows how we regularly miss the true definition of the domain and how we can fix this with the simplicity of F#.

My blog post builds upon that idea and looks how we can validate our models in the same simplicity.

Domain Modeling

When thinking about the modeling of the domain, F# has a very nice way to express this. Throughout this post, I will be using F# for my modeling and for the validation of my model. Sometimes I will show your what the alternative would look like in an Object-Oriented Language like C#.

Book

Ok, let’s define our model. We want to define a “Book” in our domain. A book in our domain has several items which defines “a book”; but for the sake of this exercise we’ll keep it very short:

Just like Scott Wlaschin has asked the question, I'll ask it again: “What’s wrong with this design?”.

Several things, as a Security Expert you could say that we’re could have a problem if someone enters negative pages, or special chars for the ISBN or the Author.
As a Domain Expert, you could say that this model doesn’t actually represent the domain.

PositiveInt

Let’s start with a simple one: we can’t have negative pages; so, let’s define a new type for this. Note that we have cleared it “private” so we can’t call this new type directly via its Value Constructor. Because we have made it private; we need another function that will create this type for us. When we enter a negative number, we can’t create a type. That’s sounds like an Option to me:

FYI: At this point, Scott's talk stops because the talk is about the domain itself and not to specify how we can refactor the validation of the models.

Now we can start with the refactoring to Active Patterns. Because this is a simple type, I think you can’t see the immediate benefit of this approach; so, hang on. We use the Partial Pattern approach for these Business Rules because we can’t wrap all possible values in a single pattern.

The Partial Pattern approach needs a return type of unit option. We can use the Some branch to return the pattern itself and the None branch can be used to specify that the input doesn’t match this pattern.

One can argue about the over-engineering of this approach; but personally, I find this a way more simplistic approach than the inlined Guard Clauses in the Match Expression.

Our book looks now like this:

String50

Next up, is the author’s name. It reasonable to think that the length of the name will be no longer than 50 chars.

We can specify all these rules in our model the same way as we did with the pages:

Notice that we now have two branches that cover our type. By extracting the rules into Partial Patterns, we have made it clear, in our Constructor Function, that we need a string that isn’t “null” or empty and is a maximum of 50 characters long.

Now, how would we specify this in C#? Because we do not have an option type by default, only a less stronger Nullable<T> type; we normally use exceptions.

Note that we can reuse the pre-conditions for the empty string and the length across our application in the F# version, while we must redefine them for every class in C# (except off course we extract this functionality in some “utility” classes.

Now, our book type looks like this:

ISBN13

The last type is the most interesting and the reason why I would use Active Patterns for my Domain Model Validation.

If we have some more complex type for example an ISBN13 number; how would we model that? First of all, let’s specify some requirements:

  • Number must have length of 13
  • Last number is checksum

The checksum is calculated by evaluating the following steps:

  1. Take the 12 first chars
  2. Multiply the even numbers in the sequence with 3
  3. Take the sum of all the results
  4. Modulo 10 the result
  5. Substract 10 if the outcome isn’t zero
  6. Final result must be the same as 13th number

I came up with this:

What I like about this, is the declarativity of the checksum calculation and the fact that you can see immediately what rules we have in our ISBN validation.

Note that I changed the Active Pattern for the length of the string by passing in a function; this way I can reuse it for my String50 type and for this one AND can you see more clearly what exactly we're trying to validate with the string's length (greater than, equal to, ...).

Now, I wanted to check this with C#. To achieve the same level of simplicity; we would extract each rule in it’s own method:

If we extract each rule in a method, I think we get that same simplicity. But we should send some arguments with the rules not just for reusability in other models but for readability as well.

Take for example the Regular Expression rule. It’s much simpler to just send the pattern with the rule than to come up with some name for the method (or Active Pattern) that would satisfy what you’re trying to verify.

Note that the C# version isn’t done yet and must be refactored since there’s a lot going on which can’t be comprehend as quickly as the F# version (but that's just my opinion).

Before you say anything about LINQ, I explicitly used and imperative approach because otherwise we would use functional programming again and when I compare functional with imperative I always try to be functional and imperative in the extreme so I can quickly see what's the actual difference is.

 Testing

Of course, to be complete let’s write some properties for our newly created types. I found not every type to be that obvious to write properties for so it might be a good exercise for you as well.

PositiveInt Properties

First, let us look at the positive integer type. This was the simplest type to model and is also the simplest type to test. I came up with these two properties for the two branches:

String50 Properties

The next type must have a length of 50 chars to be a valid type. Following properties came to mind:

ISBN13 Properties

Now, the last type is probably the most interesting. We must generate valid ISBN numbers to check if the checksum acts properly. I came up with a Test Oracle as another way to express the checksum so I’ll could filter with this expression to generate valid ISBN13 numbers:

I love the way FsCheck allows me to write such properties with such little effort. Now I have a way to generate random, valid ISBN13 numbers. Notice that I didn't check the other Active Pattern branch, perhaps this is a good exercise for you? All other cases should result in None.

Small side note: the assertion is now valid (accessible) because I wrote the types and properties in the same file. When this isn't the case, we could test for any type (with wildcards) wrapped inside a Some case, instead of actually creating an ISBN13 or any other type. That way, we could change the values for that type without changing our test. For the sake of this exercise, I thought it was clearer to assert the type this way.

Love to hear your opinion!

Conclusion

In this post, we looked at how F#'s feature Active Patterns can help build a clear, declarative solution for the Validation of Domain Models. By using a Partial Pattern for each Business Rule, we can clearly see how the input is restricted to verify each rule.

In an object-oriented approach, you would normally create a class to wrap the domain model and specify the business rules inside the constructor while in functional programming, this can be done by privatizing the Value Constructor and create a new Constructor Function which uses Active Patterns to specify each business rule.

Thanks for reading!

Categories: Technology
Tags: F#
written by: Stijn Moreels

Posted on Thursday, September 28, 2017 12:46 PM

Stijn Moreels by Stijn Moreels

“Property-Based Testing”, ever heard of it? It’s a very popular topic in the functional community. The opposite of this approach is the well-known “Example-Based Testing”. People think in examples and that’s why it’s so popular; also in the non-functional community. This is/was the way we write/wrote tests.
“Given a static, constant example; the output should be this”
But is that the best we can do?

Introduction

Property-Based Testing is about generalizing the input so we can make statements about the output; without specifying exactly what the input or output should be, only should look like.

I’m not going to give you the full-introduction because there are already so much good resources about this topic, (also in different languages).

But what I will do, is give you an introduction to FsCheck in a C# environment. FsCheck is written in F# but has a C#-friendly API. I’m going to use the FsCheck.Xunit package for this blog post.

FsCheck

For a full-introduction of FsCheck itself, I highly recommend the documentation of FsCheck; with a good explanation about the framework. Although they give a good idea of how the framework is built, I find it hard to find examples of how it can be used concretely; especially if you’re using the xUnit variant.

Several blog posts are using F# to make properties with FsCheck, but with C# the posts are rather rare…

Fact to Property

Let’s start from the xUnit example they present on their documentation:

If you know xUnit, you know that ‘Fact’ is the way xUnit marks methods as test-methods and the static class ‘Assert’ is used to assert on the result.

Now, I’ll give you the same example but written with some FsCheck properties:

What are the differences?

  • The ‘Fact’ attribute is changed to ‘Property’ attribute
  • Return type is ‘Property’ instead of ‘void
  • Assert’ class isn’t used, but the condition is returned and transformed by the ‘ToProperty()’ call to a ‘Property
  • The inputs of the method under test aren’t hard-coded anymore

This last difference is probably the most important one.
I highly recommend you read the resources if you haven’t heard about PDT because I won’t list all the benefits of Property-Based Testing. I hope that you see that by using this approach, I can’t maliciously fake the actual implementation anymore, while in the first example I could have done this.

We’ve added two parameters to the test method that FsCheck will fill-in for us with some random values. This will contain negative, zero and positive values all in the range of an Int32 data type. All valid integers so to say. FsCheck will, by default, run 100 tests with random values for the inputs of the test.

FsCheck has several extension methods on boolean values, like the one above. Let’s look at some more.

Conditional & Lazy Properties

Sometimes, we want to restrict the input to make sure you’re always end up with the same output. A simple example is the mathematical division. You can’t divide by zero, so to have the same result we must make sure that the given input isn’t below zero.

What’s different?

  • We added the ‘When()’ call to specify that we can’t divide by zero (this makes sure we don’t have to call ‘ToProperty()’ again)
  • We extracted the method, which we wanted to test, in its own delegate. Note that FsCheck has extension methods on any delegate that returns a boolean.

That is a good example of the Conditional Property; but why do we need to extract the call to ‘Divide’? Because otherwise FsCheck will evaluate this immediately (even with ‘y’ being zero) which would result in a ‘DivideByZeroException’ and FsCheck will treat any exception being thrown as a test failure. That’s why.

By extracting this, we’re telling FsCheck that we’re only interested in the results IF the condition holds. In our case: ‘y’ must be zero.
That’s convenient!

With this simple example, we’ve shown how we express conditions in our properties to make sure we’re always in a given set of inputs, and shown how we can create Lazy Properties which are useful to only evaluate the test if the condition we’ve set holds. This also can be useful if the actual test takes some time and we don’t want to lose time while evaluating a test which result isn’t of interest for us.

Exception Properties

In functional programming, I’ll try not to use any exceptions in my code; but in imperative languages this is the way to express something went wrong. We also write tests that trigger those exceptions that we throw by giving invalid inputs.

The xUnit package also has some methods on the Assert class called “Throws”, “ThrowsAny”, ... How can we express this in FsCheck?

The documentation says that this isn’t actually supported in C# (you can see it at the lower-case method); but writing it this way works.

Observed Properties

The best possible alternative for this feature, is the ‘usermessage’ you can send with the ‘Assert’ class in the xUnit package. We send a string with the assert so we can later see which assertion has failed.

FsCheck takes this a step further.

Trival Properties

FsCheck has a way to count the cases for which a condition is met. In our previous example, can we count how many generated values are negative values?

In our test output, we can see that the positive and negative values are almost split in half:

Ok, passed 100 tests (47% trivial).

Try to run them again and see how this test output change.

Classified Properties

Sometimes, we want more than one condition to check about our input and maybe add some custom message for each category of input. According to me this is the closest thing to the ‘Assert’’s ‘usermessage’.

FsCheck has a way to express this by classifying properties.

In our output, we’re now seeing:

Ok, passed 100 tests.
63% Smaller than '1000'.
37% Smaller than '1000', Bigger than '10'.

See, how the categories can also be combined and are shown to the user in a friendly way.

Collected Properties

We’ve seen some examples how we can express some categories for our test inputs by specifying conditions on them and giving them a name. But sometimes we’re just interested in the actual input value itself and how it changes during the test run.

This will result in this test output:

Ok, passed 100 tests.
8% "Values together: 0".
5% "Values together: 8".
5% "Values together: 1".
4% "Values together: 3".
4% "Values together: -12".
3% "Values together: 38".
3% "Values together: 2".
3% "Values together: -4".
3% "Values together: -14".
3% "Values together: -1".
2% "Values together: 9".
2% "Values together: 7".
2% "Values together: 5".
2% "Values together: 32".
2% "Values together: 21".
...

This way, we can clearly see how the test inputs changes over time.

Combined Observation Properties

As a final observation property, we can also combine several of the previous observed properties into one property that combines all the results:

This will result in this test output:

Ok, passed 100 tests.
7% "Values together: 3", Smaller than '1000'.
5% "Values together: 2", Smaller than '1000'.
5% "Values together: 0", Smaller than '1000'.
4% "Values together: 13", Smaller than '1000'.
4% "Values together: 1", Smaller than '1000'.
3% "Values together: -8", Smaller than '1000'.
3% "Values together: -4", Smaller than '1000'.
3% "Values together: -15", Smaller than '1000'.
3% "Values together: -12", Smaller than '1000'.
2% "Values together: 9", Smaller than '1000'.
2% "Values together: 8", Smaller than '1000'.
2% "Values together: 7", Smaller than '1000'.
2% "Values together: 27", Smaller than '1000', Bigger than '10'.
2% "Values together: 22", Smaller than '1000'.
2% "Values together: 1", Smaller than '1000', Bigger than '10'.
2% "Values together: -56", Smaller than '1000'.
2% "Values together: -3", Smaller than '1000'.
2% "Values together: -11", Smaller than '1000'.
2% "Values together: -10", Smaller than '1000'.
...

Combined Properties

The previous properties all had the same thing in common: they are  testing a single condition. What if we want to test multiple conditions? And how do we distinguish each property from one another?

Sometimes, we want to test two conditions. Combining them in a ‘AND’ expression. FsCheck also has this as extension method:

We can also add a ‘Label’ which is the same as the ‘usermessage’ in the ‘Assert’ class in the xUnit package: it pops up when the condition isn’t met.

By using this approach, we always know which property has failed.

Note that I now use a ‘NonNegative’ type instead of a regular int. This is also part of the FsCheck framework and allows me to make sure I always get a positive integer without specifying it in a Conditional Property. As you have seen, FsCheck will try any value that acts as a valid type; so, if I would add a condition to my property stating that I want a positive integer, I’ll get roughly the half of the test runs. This way, by using the ‘NonNegative’ I’m sure that I still get my 100 test runs without skewing the input so much I get merely any test runs.

Of course, we can also combine our properties in an ‘OR’ expression with the extension method ‘Or()’.

 Types

We’ve already seen an example with the previous properties where I used the ‘NonNegative’ type. FsCheck has several types that you can use to stricken our input. Some interesting ones:

  • PositiveInt represent an integer bigger than zero
  • NonZeroInt represent an integer which isn’t zero
  • NonNegativeInt represent an integer which isn’t below zero
  • IntWithMinMax represent an integer that can contain the int.Min and int.Max values
  • NonNull<T> wraps a type to prevent null being generated
  • NonEmptyArray<T> represent an array which isn’t empty
  • NonEmptySet<T> represent a set which isn’t empty
  • NonEmptyString represent a string which isn’t empty
  • StringNoNulls represent a string without null characters (‘\000’)
  • NormalFloat represent a float which isn’t infinite or NaN
  • Interval represent an integer interval
  • IPv4Address represents an IPv4 Address
  • IPv6Address represents an IPv6 Address

And many more... Don’t hesitate to come up with your own generic types that you can contribute to FsCheck!

We can also generate our own domain models with invalid and valid ones and use FsCheck to generate them for use; but that would lead us to another topic about generators.

Conclusion

In this post, we’ve seen how Property-Based Testing isn’t just a functional concept but an idea we can use in any language. FsCheck is inspired from the QuickCheck variant in Haskell, there’s also the ScalaCheck in Scala, JavaQuickCheck for Java, ClojureCheck for Clojure, JSVerify for JavaScript, … and so many more.

I’m not saying that you can abandon all your Example-Based Tests. Just like I stated in the beginning of this post: people think in examples. So, I think the combination of Example-Based Tests and Property-Based Tests is the sweet spot. By examples we can show the next person concrete ways of how to use your API and with properties you ensure that the implementation is the right one tested with any boundary conditions.

Thanks for reading!

Categories: Technology
Tags: Code Quality
written by: Stijn Moreels

Posted on Tuesday, September 26, 2017 9:28 PM

Stijn Moreels by Stijn Moreels

Using F# and Property-Based Testing to solve the Coin Change Kata really helped me to get more insight in the Property-Based Testing technique; I hope it will help you also.

Introduction

The one way to become an expert in something is to practice; and Programming Katas are a very good approach to keep practicing your programming skills.

In this post, I will solve the Coin Change Kata with F# and use Property-Based Testing (with FsCheck) to drive the design.
For me, this was a lesson in writing properties and not so much solving the kata. It was a fun exercise. I thought it would be useful to share my code with you.
If you haven’t any experience with Property-Based Testing or F#, I recommend you look first at those topics.

Coin Change Kata

Description

Ok, there are several different descriptions of this Kata; so, I’ll show you what I want to accomplish first.

“Given an amount and a series of Coin Values, give me the best possible solution that requires the least amount of Coins and the remaining value if there is any”

So, by looking at the definition of the Coin Kata; I need two inputs and two outputs:

Signature

The first thing I did before describing my properties, is defining my signature of my function. My first mistake was I thought I could use integers all over the place. Something like this:

int list -> int -> int * int list

But we can’t have negative coin values, so I started with making a coin type. In the Kata, there are several amounts they use so I chose to use the same:

Note that, by describing the coin values in this way, I have restricted the input values of the coins. This makes Illegal States Unpresentable (from Yaron Minsky).

And so my signature, after type interference, is the following:

Coin list -> int -> int * Coin list

Strictly speaking this is not the right signature, because we are still handling negative amounts, but for the sake of this exercise; I will leave this as an exercise for you.

Properties

First Property: Ice Breaker

So, let’s start coding. The first property should be some kind of Ice Breaker property. I came up with the following:

“Change amount with nothing to change gives back the initial amount”

This is the property when we do not have any coin values, so we just get back the same amount as remaining value. Note that I use ‘byte’ as a input value so I make sure I have a positive value, and for the sake of this exercise. The maximum byte value is enough for this demonstration.

We can easily implement this:

We can play the Devil’s Advocate and intentionally use a fake implementation, for example:

Which will still pass.

Second Property: Boundaries

The next property I wrote was the other way around: what if I haven’t got any amount to change?

“Change zero amount result in original coin values”

Note that we have FsCheck to generate us the random list of our Coins. We don’t care what coins we’re about the use for the change and that’s why we can use FsCheck to generate some for us.

I think this is a good implementation example of how Test Ignorance can be accomplished with Property-Based Testing.

And our implementation:

Now we can’t fill the list so we’re back with the first implementation which makes the two properties pass.

Third Property: Find the Constants

I’m not quite sure this is a proper example of this; because you could state this property for other values as well with some effort and it’s possibly also covered with a latter property. Although, this was the next property I wanted to write because it drives me more in the actual implementation of the function and it’s a constant in this implementation.

“Change is always One if there’s no other coin values”

We can implement this property (and respect the others) with this implementation:

When I have only ‘One’ coins, the change for a random amount is always a list of ‘One’ coins that has the same length of the initial amount to-be changed. I can of course play the Devil’s advocate and change the remaining amount to 42 for example (because 42 is the answer to life):

And so, we can stricken our property to also assert on the remaining amount:

Because of FsCheck this is hardly an issue. I added some Labels (from FsCheck) to clearly state in the output WHAT failed in the property. This is good thing for Defect Localization.

Also note that playing the Devil’s Advocate makes sure that I implement the right implementation and that my properties this state in the most strictly solution.

Fourth Property: Some Things Never Change

For the fourth property, I thought even further about the result and came up with this property. The constant that I found was that whatever I change into coins, the initial to-be-changed amount should always be the sum of the remaining change and the changed coins.

“Sum of changed coins and remaining amount is always the initial to-be-changed amount”

What this property needs, is a non-empty list of coins because we otherwise re-testing the already written property of the empty coins. This is also no issue for FsCheck, with Conditional Properties we can easily define this with the List.length coins <> 0 ==> lazy expression.

This will make sure that the other part of the function only gets evaluated, and so verified if the condition is met.

The rest of the function is the mapping of all the coins into values, sum this and add the remaining amount to this. All this together should be the same as the initial amount.

This is the first time I need to get the actual value of coins, so a made a function for this:

How do we know how much coins we get in a given amount? That’s a division of the amount by that coin value. We need several coin values and so we must also do the division by the other coin values; so, we need the remaining value of the division. That’s a modulo of the amount by that coin value.

We need to do this for all the different coins we have.

Does this pattern sounds familiar?

We have an initial value, we need to loop over a list, and do something with a given value that can be passed to the next loop iteration.

In an imperative language, that’s the for-loop we’re stating:

Something like this (sort of).

But, we’re in a functional language now; so, what’s the alternative? Fold!

Here is some implementation using fold:

One of the things I like to do is to specify the different arguments on its own instead of inlining them (in this case into the List.fold function). I think this increases Readability and shows more the Code’s Intent: that the core and return value is the result of a List.fold operation.

This reminds me of the Formatting Guidelines I described in a previous post that the return value of a method should be placed on a different line to increase readability and highlights “The Plot” of the method.

This is very similar; we want to show the what we’re doing as “The Plot” of the function by specifying the argumented-functions on separate.

Also note that we can use the function valueOfCoin that we needed in our Property. People not familiar with TDD and the Test-First mindset sometimes say that they don’t like to see if the test is the only place where some functionality is used; but if you use TDD the test is the first client that will use those functionalities!

Fifth Property: Final Observation

We’re almost there; there’s just one last thing we didn’t do right in our implementation. The Kata stated that we must find “the best possible solution” for the amount in change. We now have an implementation that finds “some” solution but not the “best” solution. Why? Because we don’t use the order in which the different coin values are passed in; we just loop over them. We need the best solution for the least amount of coins.

How do we get from “some” solution to the “best” solution? Well, we need to check first with the highest coin values and then gradually to the least coin value.

How do we specify this in a Property? I must admit that it did not come to me very fast, so I think this was a good exercise in Property-Based Testing for me. This was the Property I came up with:

“Non-One Coin value is always part of the change when the amount is that Coin value”

Why do we need a non-one Coin value? Why do we need a non-empty Coin list? Because we otherwise testing an already specified property.

That’s why we use the Conditional expression: (nonOneCoin <> One && List.length coins <> 0) ==> lazy.

Now, the other part of the Property. We need to check if the given random list of coins (with a non-one Coin in it) result that the non-one Coin is part of the change we get if the amount to-be-changed is the value of the non-one Coin.

That’s seems reasonable. If I want the change the value 50 in coins and I have the Coin value 50, I want that as return value. That would be the solution if I need the least amount of coins. I don’t care if a have Coins of 50 and 25 for example, the order of the different Coin values doesn’t matter; just give me the change with the least amount of coins.

Note that we first use the Gen.shuffle function to shuffle the random list of coins with the non-One Coin. After that, we’re sure that we have a list with a non-One coin. If I would specify this condition inside the Conditional expression of FsCheck, I would have a lot of tests cases that are skipped because the condition wouldn’t be met. If I set the condition on a signal Coin value; I will have a lot more test cases.

The chance that I get a Coin that isn’t One is much higher than I get a list that contains a non-One coin I guess. But not only that; I get more Code’s Intent in my Property if I state my non-one Coin value like this I guess.

We finally pipe into the snd function that gives us the second element of the tuple so we can use it in our assertion to check if the nonOneCoin value exists in the resulted list of coins.

How do we implement this?

We sort the Coins by their Coin value. Note how we again can use the already defined valueOfCoin function.

Conclusion

As I said before: this wasn’t exactly an exercise in solving the Coin Change Kata but rather in specifying Properties to drive this implementation. I noticed that I must think on a higher level about the implementation instead of hard-coding the test values.

I don’t know which values FsCheck will provide me and that’s OK; I don’t need to know that. I just need to constrain the inputs so that I can predict the output without specifying exactly what that output should look like. Just specifying some Properties about the output.

Hopefully you found this a nice read and have enjoyed the way we write Properties in this example. Maybe now you’re inspired to write Properties for your own implementations. The full code can be found at my GitHub.

FsCheck can also be used from a C# environment instead of F# so you don’t have to be a F# expert to write Properties. It’s a concept of looking at tests and how we constrain inputs to predict outputs.

Thank you.

Categories: Technology
Tags: F#
written by: Stijn Moreels