Purely Functional Tree Search in Haskell
Haskell is an absolute pleasure to write code in, and I've been trying to use it more and more. It's a language that rewards extended effort in a way that
C++ et. al. do not.
Consider the following program, illustrating a basic BFS/DFS search through a tree in Haskell. It illustrates a number of useful concepts - algebraic data types, type classes, and QuickCheck.
The code is straightforward (as Haskell code tends to be) - we define our basic tree structure, describe some type classes it belongs to, and traverse the tree.
Assume there was a bug in our code - for example, we replace an
|| with an
&& in our
search function, going from
Running this incorrect program, QuickCheck immediately identifies the minimal example for which this program fails.
See the chapter on QuickCheck and other forms of testing in Real World Haskell for more information.