A nice recursive algorithm for building a nearly-optimal binary search tree from an ordered list.:

1
2

data Tree a = Node a (Tree a) (Tree a)
            | End

The algorithm divides the input list into sublists of increasing length: 1,2,4,8… The first element of each sublist is the “keystone” of a subtree assembled with mkTree. :

1
2
3
4
5

fromSorted :: [a] -> Tree a
fromSorted = foldl mkTree End . divide 1
    where mkTree l (n:ns) = Node n l (fromSorted ns)
          divide _ [] = []
          divide c xs = take c xs : divide (c*2) (drop c xs)

Variations that used splitAt instead of the separate take and drop were no more efficient (perhaps because of sharing?) nor was using the strict foldl'.

Anyone have a clever alternative to the divide function defined here? Or a different approach to the problem? Would love to hear it.