Re: [Haskell-cafe] Construct all possible trees

[Andrew Coppin]

Andrew Coppin wrote: trees :: [Int] -> [Tree] trees = map fst . (\ts -> all_trees 1 (2 * length ts) ts) . map Leaf all_trees :: Int -> Int -> [Tree] -> [(Tree,[Tree])] all_trees n m ts  | n > m     = []  | otherwise = pick ts ++ sub_trees n m ts sub_trees :: Int -> Int -> [Tree] -> [(Tree,[Tree])] sub_trees n m ts = do  let n2 = n * 2  (t0,ts0) <- all_trees n2 m ts  (t1,ts1) <- all_trees n2 m ts0  return (Branch t0 t1, ts1) Idiot... The size of the deepest possible balanced tree with N leaves is log2 N. The deepest possible unbalanced tree has N nodes! For small N, it doesn't matter too much. But as N gets larger, the difference becomes... uh... large? (!) *sigh* I hate being wrong. :-(

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe