Haskell Family Tree - Exam Preparation

2
votes

I'm doing an exam soon and need help with an exam question about family trees. I've done trees previously but only of this format:

data Tree a = Empty | Leaf a | Node a (Tree a) (Tree a)

So basically a tree that either empty or leaf nodes, or a node that has 2 trees that follow it recursively. Now I've been given this question:

                                DAN=DORIS

               /                   |                          \
        JACK-PEGGY            CHRISTINE-PAUL                PHIL-JILL 
      /     |     \                                      /    /     |     \  
 JENNIFER LILLIAN TONY                              SCULA KENTON DAVID ELIZABETH

This shows that Dan married Doris and their children were Jack (who married Peggy), 
Christine (who married Paul) and Phil (who married Jill). The children of Jack and Peggy 
were Jennifer, Lillian and Tony. Christine and Paul had no children. Phil and Jill’s 
children were Shula, Kenton, David and Elizabeth. 
Assume that any name appears in the tree at most once. Neglect the possibility of 
second marriages. 

(i) Give a Haskell algebraic datatype definition for family trees, and show how the 
    above tree would be represented using your datatype
(ii) Using your datatype definition, write a Haskell function which, given the name 
     of a person and a family tree, returns the names of that person’s children, if 
     any.

Sorry that was the best I can draw of the tree shown in the paper - but its pretty obvious, Dan is married to Doris at the topmost, then has 3 kids Jack, Christine, and Phil, etc.

So the tree type I used can't be used here, I was wondering what type definition is it this time (basically question 2.(i), and any ideas for (ii)?

2
haskelltree
Why shouldn't the Tree you mention work? You could consider the couple as a single value and search for matches. - shree.pat18
but then what about when it reaches Jack and Peggy's children, don't they have 3 children and thats 3 subtrees where as the one I learned is 2. Phil and Jil have 4 sub trees as well, I'm relatively new to haskell so I need more guidance in this. - darkphoton

2 Answers

7
votes

The number of children in your tree is variable. The standard library type Data.Tree, models such trees roughly as:

data Tree a = Node a [Tree a]

This works for your case as well, except

  • you need to distinguish the case of a married couple (having any number of children) from a single person (with no children)
  • you may want to add an empty tree as well

So, without giving up too much, a tree can be of three forms: empty, married couple with any number of children, and single person with no children. Translate this last sentence from English to Haskell and you are done.

1
votes
import Data.Foldable as F

data Family a = Single a | Couple a a [Family a]
    deriving Show -- useful for ghci

isCouple :: Family a -> Bool
isCouple (Couple _ _ _) = True
isCouple _ = False

isFamily :: Eq a => a -> Family a -> Bool
isFamily n (Single a) = n == a
isFamily n (Couple a b _) = n == a || n == b

q1 :: Family String
q1 = Couple "Dan" "Doris" [Couple "Peggy" "Jack" [Single "Jennifer", Single "Lillian", Single "Tony"], Couple "Christine" "Paul" [], Couple "Phil" "Jill" [Single "Scula", Single "Kenton", Single "David", Single "Elizabeth"]]

q2 :: String -> Maybe [Family String]
q2 n = q2' n [q1]

q2' :: Eq a => a -> [Family a] -> Maybe [Family a]
q2' n f = case find (isFamily n) f of
    Just (Single _) -> Just []
    Just (Couple _ _ c) -> Just c
    _ -> case filter isCouple f of
        [] -> Nothing
        cs -> q2' n $ F.concatMap (\(Couple _ _ c) -> c) cs