Using pattern matching in the Binary Search Tree Clojure solution

A member of SCBCN coded a beautiful solution in F# for the Binary Search Tree kata.

I wanted to try using pattern matching to get to a similar solution in Clojure.

So I watched Sean Johnson's Pattern Matching in Clojure talk and read a bit the documentation of clojure/core.match.

My intention was to use defrecord matching, but I couldn't make it work.

Later I found out in an answer to this StackOverflow question, Pattern matching on records in Clojure, that this feature hadn't been implemented yet.

So I followed the advice given in StackOverflow of using map pattern matching and coded this version of the Binary Search Tree:

Even though is not as nice as the F# one, it reads very well and allowed me to get rid of the value, left and right private helpers and all ifs.

Then I tried another thing that Sean Johnson had mentioned in his talk.

I coded another Binary Search Tree solution using the defun macro which creates functions with pattern matching like in Erlang, or Elixir

This is the resulting code using defun:

which also reads very nice.

Interesting Talk: "Pattern Matching in Clojure"

Yesterday I watched this very interesting talk by Sean Johnson:

• Pattern Matching in Clojure

Applying property-based testing on my binary search tree implementation

Some weeks ago I did the the Binary Search Tree problem from Exercism in Clojure.

I used TDD using some of the sample tests that Exercism provided and some other that I added.

These were the tests, after deleting some redundant ones:

And this was the binary search tree code:

I was just testing a few cases.

To gain confidence in my solution and play a bit more with the exercise, I decided to apply a bit of property-based testing on it.

So I added the clojure/test.check dependency to my project:

and added a new spec to the tests:

The in-order-traversal-of-bst-sorts-elements spec is checking the in-order-traversal-of-bst-sorts-elements-property 100 times.

For each check, the generator creates a random vector of integers and checks if the result of calling in-order on the binary search tree created from the vector is equal to the sorted vector.

The macro clojure.test.check.clojure-test/defspec allows to integrate clojure/test.check with clojure.test, so that properties can run under the clojure.test runner.

Midje, the test framework I'm using, can also detect and run clojure.test tests.

Ok, after running the tests, this is what I got (formatted so it fits without a lot of scrolling):

There was a case that was failing.

A really nice thing about clojure/test.check is that it tells you the smallest case that makes your code fail. See the value of the :smallest key inside the map associated to the :shrunk key of the map in the output.

I had forgotten to write a test for the empty vector!

So I added a new failing test for that case:

and modified the code to make it pass:

Now the tests were all passing:

At this moment, I could have deleted all the unit tests and kept only the property-based ones, because the former were now redundant.

I chose not to do it, because I really like the readability of midje's facts.

In this case, I've used property-based testing to thoroughly check my solution after I had finished doing TDD. I wasn't wearing the TDD hat when I used it, I was just doing testing.

I think property-based testing and TDD can complement each other very nicely.

Another way to combine property-based testing and TDD is using the capability of clojure/test.check of giving you the smallest case that fails to help you choose the next test to drive your code.

Jan Stępień talked about this in his talk in last EuroClojure conference:

• Generative Testing: Properties, State and Beyond.

Another thing to consider is that the smallest case that makes the code fail given by property-based testing may not always correspond to the test that allows the code to grow in a small and easy to implement step.

I think that chances are that many times it might be, though.

Another thing to explore :)

Interesting Talk: "Interaction Driven Design"

I've just watched this great talk by Sandro Mancuso:

• Interaction Driven Design

This is an update and enhanced version of his previous talk: Crafted Design.

Interesting Talk: "Immutability, interactivity & JavaScript"

I've just watched this great talk by David Nolen:

• Immutability, interactivity & JavaScript

Kata: Binary Search Tree in Ruby

Yesterday in the Barcelona Software Craftsmanship coding dojo we did the Binary Search Tree kata.

Raúl Lorca and I paired using TDD in C# to get to a pretty OO solution.

We didn't finish the exercise. We got to create the binary search tree but we didn't have time to code the in-order depth-first traversal.

Well, it doesn't matter. The important thing is that we practiced TDD, recursion and OO by test-driving a recursive data structure.

Today, with a bit more of time, I did the the whole kata in Ruby.

These are the resulting tests, after deleting some I used as scaffolding to get to the final version of the code (check the commits if you want to see the evolution of the tests):

And this is the final version of the code:

To document the whole TDD process I committed the code after every passing test and every refactoring.

You can check the commits step by step here and all the code in this repository in GitHub.

I had done the same exercise in Clojure several weeks ago as part of the Exercism problems. Compare the code there with this one if you like.

Exercism: "Largest Series Product in Clojure"

I solved the Largest Series Product problem in Clojure.

This is my solution:

This Exercism problem is based on a Project Euler's exercise I solved some time ago.

You can nitpick my solution here and/or see all the exercises I've done so far in this repository.

Exercism: "Hexadecimal in Clojure"

I solved the Hexadecimal problem in Clojure.

As usual I extracted some helpers and played with partial and the thread last macro (->>) to try to make the solution more readable:

You can nitpick my solution here and/or see all the exercises I've done so far in this repository.

Interesting Talk: "Narcissistic Design: 10 Steps to Complex Code and Job Security"

I've just watched this great talk by Stuart Halloway:

• Narcissistic Design: 10 Steps to Complex Code and Job Security

Interesting Talk: "Serverside Isomorphic Javascript Rendering with ReactJS & Node"

I've just watched this very interesting short talk by David Walsh:

• Serverside Isomorphic Javascript Rendering with ReactJS & Node

Interesting Talk: "Variants are Not Unions"

I've just watched this great talk by Jeanine Adkisson:

• Variants are Not Unions

Exercism: "Difference Of Squares in Clojure"

I solved the Difference Of Squares problem in Clojure.

This exercise was very easy.

I played with partial and the thread last macro (->>) to try to make the solution more readable:

It turns out that I had done this exercise before.
You can see that version in Euler Project: Problem 6 in Clojure

You can nitpick my solution here and/or see all the exercises I've done so far in this repository.

Exercism: "Binary Search Tree in Clojure"

I solved the Binary Search Tree problem in Clojure.

I wrote three versions of the to-list function which makes a depth-first traversal of the tree returning the sequence of visited values.

This is my first version:

This is the second one using concat:

And the last one using the tree-seq function that I discovered looking at other solutions in Exercism: You can nitpick my solutions here and/or see all the exercises I've done so far in this repository.

Exercism: "Accumulate in Clojure"

I solved the Accummulate problem in Clojure.

This is an easy one in Clojure, the only restriction is that you can't use map.

I did 3 versions to practice:

A recursive one:

Another one using reduce:

And another one using a sequence comprehension: You can nitpick the solutions here and/or see all the exercises I've done so far in this repository.