fragmentary ideas ䷿ intellectual what-nots ䷷ and haskell programming ䷴

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

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

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.

There are three identical functions in Data.Map for flattening a Map to a list of tuples in ascending order:

assocs = toList = toAscList

…but nothing to convert to a descending list.

This will be a blog about programming, mostly in the functional programming language Haskell. I’m starting it to publish my projects and experiments that I think others might find interesting. My goal is to express ideas clearly, and in a way that takes as little of my reader’s time as possible. I hope that I learn a lot from my readers in the process!

I am running a wordpress blog, using the fine Vostok theme created by Javier Cañada and Rubén Lozano, which can be downloaded here. Those guys also have a nice blog.