Naturals Search

I came across this interesting pattern a while ago, while taking my first substantial steps in Haskell, and thought I’d blog it.

It’s a logarithmic time search over the Naturals, for any predicate where we can tell if a number’s too big. I use it here to implement square-root:

We define an ITree as a tree of integers. Each node can either be a leaf, containing an Integer, or a node containing an Integer and two sub-trees:

data ITree = IL Integer | IN Integer ITree ITree

This tells us how to show an ITree so that we can use printf-debugging:

instance Show ITree where
  show (IL x) = "(" ++ show x ++ ")"
  show (IN x l r) = "(" ++ show x ++ " " ++ show l ++ " " ++ show r ++ ")"

This is an ITree, and in fact is the only one we need. It is constructed lazily, and has the following shape:

  1
 / \
1   2
   / \
  2   4
     / \
    3   \
   / \   \
  3  4    \
           8
          / \
         6   \
        / \   .
       /   \   .
      5     7   .
     / \   / \
    5   6 7   8

The idea is that the right-most branches count up in powers of 2 forever. The branches coming off on the left contain a leaf for each of the numbers between this power of 2 and the previous (eg. the branch coming off 8 contains leaves for 5, 6, 7 and 8). These are spread out by splitting into above/below the average value which we stick on the node.

iTree = let biTree l h | l == h    = IL l
                       | otherwise = let m = avgI l h in
                                         IN m (biTree l m) (biTree (m + 1) h)
            from x = IN (2^x) (biTree (2^(x-1) + 1) (2^x)) (from (x+1)) in
            IN 1 (IL 1) $ IN 2 (IL 2) $ from 2

This function finds the largest number which doesn’t trigger the given tooHigh function. It does this by traversing iTree: it keeps going right until tooHigh becomes True, then it snakes down the left sub-tree, hugging the tooHigh boundary until it hits a leaf.

find tooHigh = let f (IN x l r) = if tooHigh x
                                     then f l
                                     else f r
                   f (IL x)     = x in
                   f iTree

This is a simple example which uses iTree to find the integer square root of a number.

sqrtI :: Integer -> Integer
sqrtI n | n <= 1    = 1
sqrtI n | otherwise = find $ (> n) . (^ 2)

Here’s a QuickCheck property to verify that it’s correct.

prop_sqrtI n = let root = sqrtI n
                   lower = (root - 1)^2
                   higher = (root + 1)^2 in
                   n > 0 ==> lower <= n && higher >= n

Anyone know what this iTree structure is called?