Algorithm Ex1-3

c.hs

module Main where

data Tree a = Node  a [Tree a]

data BinTree a = Empty | Branch {
    value      :: a,
    leftChild  :: BinTree a,
    rightChild :: BinTree a
}

myTree :: [Tree Double]
myTree = [ Node 1.5 [Node 1.5 [Node 1[Node 100 []]]] , Node 35 [], Node 35 [], Node 35 []]

dp :: (Num a, Ord a) => BinTree a -> Int -> a
dp Empty _ = 0
dp _ 0 = 0
dp i j = max (max (dp (leftChild i) (j - 1) + value i) (dp (rightChild i) j)) (dp (rightChild i) (j - 1) + value i)

putRight :: BinTree a -> BinTree a -> BinTree a
putRight x Empty = x
putRight (Branch a b Empty) c = Branch a b c
putRight (Branch _ _ c) d = putRight c d
putRight _ _ = error "???"

forestToBinTree :: [Tree a] -> BinTree a
forestToBinTree = foldr (putRight . tree) Empty where
    tree (Node a sf) = Branch a (forestToBinTree sf) Empty

main :: IO ()
main = print (dp (forestToBinTree myTree) 4)