Here is my shot at Homework 8 of CIS-194 (from Spring '13). The problem is about a hierarchy of employees at a company (a tree), each node being of type
Employee, each described by a label (
empName :: String) and an integer value (
empFun :: Integer). We need to choose a subset of employees so that no two chosen employees have a parent-child relationship within the tree and the sum of
empFuns of the chosen employees is maximised.
Some of the outline and structure of this code is based on what was suggested by the document, but I am curious to know if the rest of it is consistent and idiomatic Haskell. I'm not sure what I'm expecting as feedback, but any is welcome.
module Party where import Data.List ( sort ) import Data.Tree ( Tree(Node) ) import Employee ( Employee(empFun, empName), Fun, GuestList(..) ) instance Semigroup GuestList where (GL a b) <> (GL c d) = GL (a ++ c) (b + d) instance Monoid GuestList where mempty = GL  0 glCons :: Employee -> GuestList -> GuestList glCons emp (GL a b) = GL (a ++ [emp]) (empFun emp) moreFun :: GuestList -> GuestList -> GuestList moreFun = max treeFold :: (a -> [b] -> b) -> Tree a -> b treeFold f (Node label subtree) = f label (map (treeFold f) subtree) nextLevel :: Employee -> [(GuestList, GuestList)] -> (GuestList, GuestList) nextLevel emp subList = (glCons emp (foldMap snd subList), foldMap (uncurry max) subList) maxFun :: Tree Employee -> GuestList maxFun tree = uncurry moreFun $ treeFold nextLevel tree getFormattedGL :: GuestList -> String getFormattedGL gl = unlines (("Total fun " ++ show (fun gl)) : sort (map empName (emps gl))) where fun (GL _ fun) = fun emps (GL emps _) = emps work :: [Char] -> String work = getFormattedGL . maxFun . read main :: IO () main = readFile "company.txt" >>= putStrLn . work