# Naturals Search

Posted on by Chris Warburton

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?