Skip to content

Instantly share code, notes, and snippets.

@twanvl
Created February 13, 2013 13:39
Show Gist options
  • Save twanvl/4944663 to your computer and use it in GitHub Desktop.
Save twanvl/4944663 to your computer and use it in GitHub Desktop.
Ugly code to find optimal search trees
{-
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]]
-}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment