Rotating an 1D space with binary trees

Suppose you wanted to represent an 1D space in a pure functional language, i.e., with trees. Suppose that you also needed to shift the whole space left and right. An efficient way to do it would be to use a perfect binary tree to store locations, and bit-strings to represent paths. For example:

(((0 1) (2 3)) ((4 5) (6 7)))

The tree above would represent a space with 8 locations. Then, the path:

[1,0,0]

Would address the element '4'.

Now, how do you shift the space right? One way to do it would be to implement a 'get' function, which retrieves the element at a given path, and, then, constructing a new tree that, for each location N, retrieves the location N+1 of the original tree. That would work, but it isn't very efficient, since we require N log(N) operations. Moreover, it would require either cloning the tree N times, or passing it recursively, both of which add complexity in linear setups.

Fortunatelly, there is a more lean way to do it: we can rotate the tree rightwise with a single, O(N), recursive pass! The only issue is that this operates on the "bit-reversal permutation view" of the tree, so, it is hard to visualize that it actually achieves this. But by implementing an 'inv' function, we can see that this is indeed the case. The program below is a complete example. It "rotates" the original tree 8 times, and outputs:

N (N (N (L 0) (L 1)) (N (L 2) (L 3))) (N (N (L 4) (L 5)) (N (L 6) (L 7)))
N (N (N (L 7) (L 0)) (N (L 1) (L 2))) (N (N (L 3) (L 4)) (N (L 5) (L 6)))
N (N (N (L 6) (L 7)) (N (L 0) (L 1))) (N (N (L 2) (L 3)) (N (L 4) (L 5)))
N (N (N (L 5) (L 6)) (N (L 7) (L 0))) (N (N (L 1) (L 2)) (N (L 3) (L 4)))
N (N (N (L 4) (L 5)) (N (L 6) (L 7))) (N (N (L 0) (L 1)) (N (L 2) (L 3)))
N (N (N (L 3) (L 4)) (N (L 5) (L 6))) (N (N (L 7) (L 0)) (N (L 1) (L 2)))
N (N (N (L 2) (L 3)) (N (L 4) (L 5))) (N (N (L 6) (L 7)) (N (L 0) (L 1)))
N (N (N (L 1) (L 2)) (N (L 3) (L 4))) (N (N (L 5) (L 6)) (N (L 7) (L 0)))
N (N (N (L 0) (L 1)) (N (L 2) (L 3))) (N (N (L 4) (L 5)) (N (L 6) (L 7)))

Haskell example:

data Tree
  = N Tree Tree
  | L Int
  deriving Show

rotR :: Int -> Tree -> Tree
rotR 0 tree      = tree
rotR n (N mx my) = N (rotR (n-1) my) mx

swp :: Int -> Tree -> Tree
swp 0 tree = tree
swp n (N a b) = 
  let N ax ay = swp (n-1) a
      N bx by = swp (n-1) b
  in N (N ax bx) (N ay by)

inv :: Int -> Tree -> Tree
inv 0 tree = tree
inv n tree = 
  let N a b = swp (n-1) tree
  in N (inv (n-1) a) (inv (n-1) b)

main :: IO ()
main = do
  let tree = N (N (N (L 0) (L 1)) (N (L 2) (L 3))) (N (N (L 4) (L 5)) (N (L 6) (L 7)))
  let rots = iterate (rotR 3) (inv 3 tree)
  mapM_ (print . inv 3) $ take 9 rots

VictorTaelin/rotating_1d_space_with_binary_trees.md