Haskell

See “Computational Category Theory” by Rydeheard and Burstall for implementation, in ML, of the algorithms in elementary category theory. Following their lead, we present data types in Haskell that can be used to implement basic algorithms in category theory. We use a category in which addition (of integers) can be performed to ground the discussion. You will also need familiarity with types, type variables and classes in Haskell (see learnyouahaskell.com website) to proceed.

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.

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 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.

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.