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.