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:

	(ns bst-with-pattern-matching.core
	(:require [clojure.core.match :refer [match]]))
	(defrecord BinarySearchTree [value left right])
	(defn singleton [value]
	(map->BinarySearchTree {:value value}))
	(defn insert [new-value tree]
	(match [tree]
	[nil] (singleton new-value)
	[{:value value :left left :right right}]
	(if (<= new-value value)
	(->BinarySearchTree value (insert new-value left) right)
	(->BinarySearchTree value left (insert new-value right)))))
	(defn from-list [values]
	(match [values]
	[([] :seq)] nil
	[([first-value & rest-values] :seq)]
	(reduce #(insert %2 %1) (singleton first-value) rest-values)))
	(defn in-order [tree]
	(match [tree]
	[nil] []
	[{:value value :left left :right right}]
	(concat (in-order left) [value] (in-order right))))

view raw bst-with-core-match.clj hosted with ❤ by GitHub

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:

	(ns bst-with-functions-with-pattern-matching.core
	(:use [defun :only [defun]]))
	(def ^:private value :value)
	(def ^:private left :left)
	(def ^:private right :right)
	(defn singleton [val] {:value val})
	(defun in-order
	([tree :guard nil?]
	[])
	([tree]
	(concat (in-order (left tree))
	[(value tree)]
	(in-order (right tree)))))
	(defun insert
	([val tree :guard nil?]
	(singleton val))
	([val tree]
	(if (<= val (value tree))
	(assoc tree :left (insert val (left tree)))
	(assoc tree :right (insert val (right tree))))))
	(defun from-list
	([elems :guard empty?]
	nil)
	([elems]
	(reduce #(insert %2 %1)
	(singleton (first elems))
	(rest elems))))

view raw bst-with-functions-with-pattern-matching.clj hosted with ❤ by GitHub

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:

	(ns bst-properties-based-testing.binary-search-tree-test
	(:use midje.sweet)
	(:require [bst-properties-based-testing.binary-search-tree :as binary-search-tree]))
	(facts
	"about binary search tree in-order traversal"
	(fact
	"sorts the elements of a tree without any sons"
	(binary-search-tree/in-order
	(binary-search-tree/from-list [3])) => [3])
	(fact
	"sorts the elements of a tree with left and right sons"
	(binary-search-tree/in-order
	(binary-search-tree/from-list [2 5 1])) => [1 2 5])
	(fact
	"sorts the elements of a complex tree created inserting values one by one"
	(let [tree (->> (binary-search-tree/singleton 4)
	(binary-search-tree/insert 6)
	(binary-search-tree/insert 5)
	(binary-search-tree/insert 8)
	(binary-search-tree/insert 2)
	(binary-search-tree/insert 3)
	(binary-search-tree/insert 1))]
	(binary-search-tree/in-order tree) => [1 2 3 4 5 6 8]))
	(fact
	"sorts the elements of a complex tree created from a list"
	(binary-search-tree/in-order
	(binary-search-tree/from-list [4 6 5 8 2 3 1])) => [1 2 3 4 5 6 8]))

view raw binary-search-tree-tests.clj hosted with ❤ by GitHub

And this was the binary search tree code:

	(ns bst-properties-based-testing.binary-search-tree)
	(defn singleton [val]
	{:value val})
	(def value :value)
	(def left :left)
	(def right :right)
	(defn insert [val tree]
	(let [add-node
	(fn [location node]
	(assoc tree location
	(if node (insert val node)
	(singleton val))))]
	(if (<= val (value tree))
	(add-node :left (left tree))
	(add-node :right (right tree)))))
	(defn from-list [[root & rest-nodes :as nodes]]
	(reduce #(insert %2 %1) (singleton root) rest-nodes))
	(defn in-order [tree]
	(if tree
	(concat (in-order (left tree))
	[(value tree)]
	(in-order (right tree)))
	[]))

view raw binary-search-tree-initial.clj hosted with ❤ by GitHub

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:

	(defproject bst-properties-based-testing "0.0.1-SNAPSHOT"
	:description "Cool new project to do things and stuff"
	:dependencies [[org.clojure/clojure "1.6.0"]]
	:profiles {:dev {:dependencies [[midje "1.6.3"]
	[org.clojure/test.check "0.7.0"]]}})

view raw binary-searc-tre-project.clj hosted with ❤ by GitHub

and added a new spec to the tests:

	(ns bst-properties-based-testing.binary-search-tree-test
	(:use midje.sweet)
	(:require [bst-properties-based-testing.binary-search-tree :as binary-search-tree]
	[clojure.test.check.clojure-test :refer [defspec]]
	[clojure.test.check.generators :as gen]
	[clojure.test.check.properties :as prop]))
	(def in-order-traversal-of-bst-sorts-elements-property
	(prop/for-all [v (gen/vector gen/int)]
	(= (binary-search-tree/in-order
	(binary-search-tree/from-list v))
	(sort v))))
	(defspec in-order-traversal-of-bst-sorts-elements
	100
	in-order-traversal-of-bst-sorts-elements-property)
	(facts
	"about binary search tree"
	(fact
	"creates a tree without any sons"
	(binary-search-tree/in-order
	(binary-search-tree/from-list [3])) => [3])
	(fact
	"creates a tree with left and right sons"
	(binary-search-tree/in-order
	(binary-search-tree/from-list [2 5 1])) => [1 2 5])
	(fact
	"creates a complex tree inserting values one by one"
	(let [tree (->> (binary-search-tree/singleton 4)
	(binary-search-tree/insert 6)
	(binary-search-tree/insert 5)
	(binary-search-tree/insert 8)
	(binary-search-tree/insert 2)
	(binary-search-tree/insert 3)
	(binary-search-tree/insert 1))]
	(binary-search-tree/in-order tree) => [1 2 3 4 5 6 8]))
	(fact
	"creates a complex tree from a list"
	(binary-search-tree/in-order
	(binary-search-tree/from-list [4 6 5 8 2 3 1])) => [1 2 3 4 5 6 8]))

view raw binary-search-tree-tests-with-property-based-tests.clj hosted with ❤ by GitHub

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):

	======================================================================
	Loading (bst-properties-based-testing.binary-search-tree-test)
	{:test-var "in-order-traversal-of-bst-sorts-elements",
	:result false,
	:seed 1437929928970,
	:failing-size 0,
	:num-tests 1,
	:fail [[]],
	:shrunk {:total-nodes-visited 0,
	:depth 0,
	:result false,
	:smallest [[]]}}
	>>> Output from clojure.test tests:
	FAIL in (in-order-traversal-of-bst-sorts-elements) (clojure_test.clj:18)
	expected: result
	actual: false
	1 failures, 0 errors.
	>>> Midje summary:
	All checks (4) succeeded.

view raw binary_search_tree_tests_output.sh hosted with ❤ by GitHub

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:

	(ns bst-properties-based-testing.binary-search-tree-test
	(:use midje.sweet)
	(:require [bst-properties-based-testing.binary-search-tree :as binary-search-tree]
	[clojure.test.check.clojure-test :refer [defspec]]
	[clojure.test.check.generators :as gen]
	[clojure.test.check.properties :as prop]))
	(def in-order-traversal-of-bst-sorts-elements-property
	(prop/for-all [v (gen/vector gen/int)]
	(= (binary-search-tree/in-order
	(binary-search-tree/from-list v))
	(sort v))))
	(defspec in-order-traversal-of-bst-sorts-elements
	100
	in-order-traversal-of-bst-sorts-elements-property)
	(facts
	"about binary search tree in-order traversal"
	(fact
	"sorts the elements of a tree without any sons"
	(binary-search-tree/in-order
	(binary-search-tree/from-list [3])) => [3])
	(fact
	"sorts the elements of a tree with left and right sons"
	(binary-search-tree/in-order
	(binary-search-tree/from-list [2 5 1])) => [1 2 5])
	(fact
	"sorts the elements of a complex tree created inserting values one by one"
	(let [tree (->> (binary-search-tree/singleton 4)
	(binary-search-tree/insert 6)
	(binary-search-tree/insert 5)
	(binary-search-tree/insert 8)
	(binary-search-tree/insert 2)
	(binary-search-tree/insert 3)
	(binary-search-tree/insert 1))]
	(binary-search-tree/in-order tree) => [1 2 3 4 5 6 8]))
	(fact
	"sorts the elements of a complex tree created from a list"
	(binary-search-tree/in-order
	(binary-search-tree/from-list [4 6 5 8 2 3 1])) => [1 2 3 4 5 6 8])
	(fact
	"sorts the elements of an empty tree created from an empty list"
	(binary-search-tree/in-order
	(binary-search-tree/from-list [])) => []))

view raw binary-search-tree-tests-with-new-failing-test.clj hosted with ❤ by GitHub

and modified the code to make it pass:

	(ns bst-properties-based-testing.binary-search-tree)
	(defn singleton [val]
	{:value val})
	(def value :value)
	(def left :left)
	(def right :right)
	(defn insert [val tree]
	(let [add-node
	(fn [location node]
	(assoc tree location
	(if node (insert val node)
	(singleton val))))]
	(if (<= val (value tree))
	(add-node :left (left tree))
	(add-node :right (right tree)))))
	(defn from-list [[root & rest-nodes :as nodes]]
	(if (empty? nodes)
	nil
	(reduce #(insert %2 %1) (singleton root) rest-nodes)))
	(defn in-order [tree]
	(if tree
	(concat (in-order (left tree))
	[(value tree)]
	(in-order (right tree)))
	[]))

view raw binary-search-tree-corrected.clj hosted with ❤ by GitHub

Now the tests were all passing:

	Loading (bst-properties-based-testing.binary-search-tree-test)
	{:test-var "in-order-traversal-of-bst-sorts-elements", :result true, :num-tests 100, :seed 1437930264045}
	>>> Output from clojure.test tests:
	0 failures, 0 errors.
	>>> Midje summary:
	All checks (5) succeeded.

view raw binary_search_tree_tests_correct_output.sh hosted with ❤ by GitHub

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):

	require './binary_search_tree'
	describe BinarySearchTree do
	it "creates a tree without any sons" do
	tree = BinarySearchTree.new(3)
	expect(tree.in_order()).to eq [3]
	end
	it "creates a tree with left and right sons" do
	tree = BinarySearchTree.new(2)
	tree.insert(5)
	tree.insert(1)
	expect(tree.in_order()).to eq [1, 2, 5]
	end
	it "creates a complex tree inserting values one by one" do
	tree = BinarySearchTree.new(4)
	tree.insert(6)
	tree.insert(5)
	tree.insert(8)
	tree.insert(2)
	tree.insert(3)
	tree.insert(1)
	expect(tree.in_order()).to eq [1, 2, 3, 4, 5, 6, 8]
	end
	it "creates a complex tree from a list" do
	tree = BinarySearchTree.create_from_list([4, 6, 5, 8, 2, 3, 1])
	expect(tree.in_order()).to eq [1, 2, 3, 4, 5, 6, 8]
	end
	end

view raw binary_search_tree_spec.rb hosted with ❤ by GitHub

And this is the final version of the code:

	class BinarySearchTree
	def initialize(value)
	@value = value
	end
	def insert(new_value)
	if new_value < value
	self.left_tree = add_value_at(left_tree, new_value)
	else
	self.right_tree = add_value_at(right_tree, new_value)
	end
	end
	def self.create_from_list(numbers)
	tree = BinarySearchTree.new(numbers.first)
	numbers.drop(1).reduce(tree) do |tree, value|
	tree.insert(value)
	tree
	end
	end
	def in_order()
	sorted_list = tree_in_order left_tree
	sorted_list.push(value)
	sorted_list.concat(tree_in_order right_tree)
	end
	private
	attr_accessor :left_tree, :right_tree
	attr_reader :value
	def tree_in_order tree
	if tree
	tree.in_order()
	else
	[]
	end
	end
	def add_value_at(tree, new_value)
	if tree
	tree.insert(new_value)
	tree
	else
	BinarySearchTree.new(new_value)
	end
	end
	end

view raw binary_search_tree.rb hosted with ❤ by GitHub

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:

	(ns largest-series-product)
	(defn digits [string-of-digits]
	(map #(Integer/parseInt (str %))
	string-of-digits))
	(defn slices [size string-of-digits]
	(partition size 1 (digits string-of-digits)))
	(defn- compute-largest-product [size string-of-digits]
	(->> string-of-digits
	(slices size)
	(map (partial apply *))
	(apply max)))
	(defn- invalid-input? [size string-of-digits]
	(let [too-small-input? #(> size (count string-of-digits))
	empty-input? #(clojure.string/blank? string-of-digits)]
	(or (empty-input?) (too-small-input?))))
	(defn largest-product [size string-of-digits]
	(if (invalid-input? size string-of-digits)
	1
	(compute-largest-product size string-of-digits)))

view raw largest_series_product.clj hosted with ❤ by GitHub

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:

	(ns hexadecimal
	(:require [clojure.string :as str]))
	(def ^:private ints-by-hex-digit
	(zipmap ["0" "1" "2" "3" "4" "5" "6" "7" "8" "9" "a" "b" "c" "d" "e" "f"]
	[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15]))
	(defn- hex-digits [hex]
	(drop 1 (str/split (str/lower-case hex) #"")))
	(def ^:private hex-digit->int-digit
	(partial get ints-by-hex-digit))
	(defn- valid-hex? [hex-digits]
	(every? (complement nil?)
	(map hex-digit->int-digit hex-digits)))
	(defn- pow [base exp]
	(reduce * (repeat exp base)))
	(defn- hex-in-position->int
	[position hex-digit]
	(* (hex-digit->int-digit hex-digit)
	(pow 16 position)))
	(defn- reversed-hex-digits->int
	[reversed-hex-digits]
	(if (valid-hex? reversed-hex-digits)
	(reduce + (map-indexed hex-in-position->int
	reversed-hex-digits))
	0))
	(defn hex-to-int [hex]
	(->> hex
	hex-digits
	reverse
	reversed-hex-digits->int))

view raw hexadecimal.clj hosted with ❤ by GitHub

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:

	(ns difference-of-squares)
	(def ^:private naturals
	(drop 1 (range)))
	(def ^:private sum
	(partial reduce +))
	(defn- square [n]
	(* n n))
	(def ^:private square-all
	(partial map square))
	(defn square-of-sums [n]
	(->> (take n naturals)
	sum
	square))
	(defn sum-of-squares [n]
	(->> (take n naturals)
	square-all
	sum))
	(defn difference [n]
	(- (square-of-sums n)
	(sum-of-squares n)))

view raw difference_of_squares.clj hosted with ❤ by GitHub

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:

	(ns binary-search-tree)
	(defn singleton [val]
	{:value val})
	(def value :value)
	(def left :left)
	(def right :right)
	(defn insert [val tree]
	(let [add-node
	(fn [location node]
	(assoc tree location
	(if node (insert val node)
	(singleton val))))]
	(if (<= val (value tree))
	(add-node :left (left tree))
	(add-node :right (right tree)))))
	(defn from-list [[root & rest-nodes]]
	(reduce #(insert %2 %1) (singleton root) rest-nodes))
	(defn to-list
	([tree] (to-list [] tree))
	([acc tree]
	(cond
	(and (left tree) (not (right tree)))
	(conj (to-list acc (left tree)) (value tree))
	(and (not (left tree)) (right tree))
	(to-list (conj acc (value tree)) (right tree))
	(and (left tree) (right tree))
	(to-list (conj (to-list acc (left tree)) (value tree)) (right tree))
	:else (conj acc (value tree)))))

view raw binary_search_tree.clj hosted with ❤ by GitHub

This is the second one using concat:

	(ns binary-search-tree)
	(defn singleton [val]
	{:value val})
	(def value :value)
	(def left :left)
	(def right :right)
	(defn insert [val tree]
	(let [add-node
	(fn [location node]
	(assoc tree location
	(if node (insert val node)
	(singleton val))))]
	(if (<= val (value tree))
	(add-node :left (left tree))
	(add-node :right (right tree)))))
	(defn from-list [[root & rest-nodes]]
	(reduce #(insert %2 %1) (singleton root) rest-nodes))
	(defn to-list [tree]
	(if tree
	(concat (to-list (left tree))
	[(value tree)]
	(to-list (right tree)))
	[]))

view raw binary_search_tree-2.clj hosted with ❤ by GitHub

And the last one using the tree-seq function that I discovered looking at other solutions in Exercism:

	(ns binary-search-tree)
	(defn singleton [val]
	{:value val})
	(def value :value)
	(def left :left)
	(def right :right)
	(defn insert [val tree]
	(let [add-node
	(fn [location node]
	(assoc tree location
	(if node (insert val node)
	(singleton val))))]
	(if (<= val (value tree))
	(add-node :left (left tree))
	(add-node :right (right tree)))))
	(defn from-list [[root & rest-nodes]]
	(reduce #(insert %2 %1) (singleton root) rest-nodes))
	(def ^:private children (juxt left value right))
	(defn- leaf? [node]
	(not (or (map? node) (nil? node))))
	(defn to-list [tree]
	(filter leaf? (tree-seq map? children tree)))

view raw binary_search_tree-3.clj hosted with ❤ by GitHub

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:

	(ns accumulate)
	(defn accumulate [func coll]
	(let [accumulate-rec
	(fn [acc [first-elem & rest-elems]]
	(if (nil? first-elem)
	acc
	(recur (conj acc (func first-elem))
	rest-elems)))]
	(accumulate-rec [] coll)))

view raw accumulate-rec.clj hosted with ❤ by GitHub

Another one using reduce:

	(ns accumulate)
	(defn accumulate [func coll]
	(reduce #(conj %1 (func %2)) [] coll))

view raw accumulate.clj hosted with ❤ by GitHub

And another one using a sequence comprehension:

	(ns accumulate)
	(defn accumulate [func coll]
	(for [x coll] (func x)))

view raw accumulate-for.clj hosted with ❤ by GitHub

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