trees.hs

module Main where

import Control.Applicative
import Control.Concurrent.Find
import Control.DeepSeq
import Data.List
import Debug.Trace

data BinTree = Leaf | Branch Int BinTree BinTree deriving Eq

instance NFData BinTree where
  rnf Leaf = ()
  rnf (Branch i t1 t2) = rnf (i, t1, t2)

foldTree :: a -> (Int -> a -> a -> a) -> BinTree -> a
foldTree z _ Leaf = z
foldTree z f (Branch i t1 t2) = f i (foldTree z f t1) (foldTree z f t2)

sumTree :: BinTree -> Int
sumTree = foldTree 0 (\i t1 t2 -> i + t1 + t2)

treeDepth :: BinTree -> Int
treeDepth = foldTree 0 (\_ t1 t2 -> 1 + max t1 t2)

stepTree :: BinTree -> BinTree
stepTree Leaf = Branch 1 Leaf Leaf
stepTree t@(Branch i _ _) = Branch (i+1) t t

main :: IO ()
main = do
  res <- runFind $ ([0..] :: [Int]) ! (\depth -> trace (show depth) $ sumTree (foldl' (.) id (replicate depth stepTree) Leaf) > 1000000000)
  print res