Ugly code to find optimal search trees

gistfile1.hs

{-
http://noamlewis.wordpress.com/2013/02/12/penalty-search-problem-revisited-dynamic-programming-control-parallel-to-the-rescue/

-}

import Data.MemoCombinators

--f k = fromIntegral k

data CostTree
  = Leaf   !Int
  | Branch !Int !Integer CostTree CostTree
  deriving Show

treeCost :: CostTree -> Integer
treeCost (Leaf _) = 0
treeCost (Branch _ c _ _) = c

instance Eq CostTree where
  a == b = treeCost a == treeCost b
instance Ord CostTree where
  a <= b = treeCost a <= treeCost b

mkBranch :: Int -> Integer -> CostTree -> CostTree -> CostTree
mkBranch k c l r = Branch k (c + treeCost l + treeCost r) l r

-- cost to search the range i≤x≤j
cost :: (Int -> Integer) -> Int -> Int -> CostTree
cost f = tbl
  where
  tbl = memo2 integral integral cost'
  cost' :: Int -> Int -> CostTree
  cost' i j = if i >= j then Leaf i else
      minimum [ mkBranch k (fromIntegral (j-i) * f k) (tbl i k) (tbl (k + 1) j) | k <- [i..j-1] ]

{-
With constant cost: A001855

[fromIntegral (treeCost (cost (\x -> fromIntegral x) 1 i)) / fromIntegral i^2 / logBase 2 (fromIntegral i) | i <- [1..60]]

-}