Computable Numbers in Haskell

Numbers are all In this post, we examine two examples set out in the classic paper by Turing. The first problem is to report the $n^{th}$ binary digit of 1⁄3. The second problem is to report the $n^{th}$ binary digit of $\sqrt{2}$. The 1936 paper On computable numbers, with an application to the Entscheidungsproble describes two machines to perform the tasks. In this post, we give in Haskell two programs for the same.

Bipartite Matching in Haskell

In this post, we implement in Haskell, the augmenting path method to find a maximum matching in a bipartite graph. We use function composition and recursion mostly. We obtain a simple implementation of an algorithm to compute maximum matching in a bipartite graph. As a side affect of this exercise, you should know about algorithms to compute terminal objects, and fix points in a category. Only a basic familiarity with Haskell is assumed here.

AVL Trees in Haskell

AVL Trees are binary search trees with a balance condition. The balance condition ensures that the height of the tree is bounded. The two conditions satisfied by an AVL tree are: order property: the value stored at every node, is larger than any value stored in the left subtree, and is smaller than any value stored in the right subtree. balance property: at every node the difference in the height of the right and the left subtrees is at most 1.

Splay Trees in Julia Lang

Let us implement Splay Trees in Julia which is, relatively new and popular, dynamically typed language with multiple dispatch. We model a node in the splay tree as an abstract data type. Each node contains a single integer data value and two references to the left and the right subtrees. The subtrees can be empty, as in the case of leaf nodes, and we model this by using the Nil type.