Дерево: Дополнительное количество посылок

Question

У меня есть структура data в Haskell, которая позволяет мне построить дерево.

data MultTree b = DataNode b | IndexNode Int Int (MultTree b) (MultTree b) (MultTree b) deriving (Show) 

В этом случае возможно только в том IndexNode, что нужно три MultTree's в качестве параметров.

Как я могу сделать IndexNode в состоянии получить 0, 1, 2 или 3 MultTree's? Выполнение IndexNode с использованием только разных параметров не работает.

Таким образом, в конце концов, я хотел бы создать дерево подобное:

t2 :: MultTree Int 
t2 = IndexNode 3 42 (IndexNode 3 15 (3) (11) (12)) (IndexNode 19 42 (42) (23)) 

Answer 1

Определите свой тип, содержащий от нуля до трех вещей:

data From0To3 a = Zero | One a | Two a a | Three a a a 
    deriving (Show) 
data MultTree b = DataNode b | IndexNode Int Int (From0To3 (MultTree b)) 
    deriving (Show) 

t2 :: MultTree Int 
t2 = IndexNode 3 42 
    (Two (IndexNode 3 15 
      (Three (DataNode 3) (DataNode 11) (DataNode 12))) 
      (IndexNode 19 42 
      (Two (DataNode 42) (DataNode 23)))) 

В соответствии с просьбой, вот как рассекают такое дерево. Например, следующее вычисляет высоту дерева.

height :: MultTree a -> Int 
height (DataNode _)   = 1 
height (IndexNode _ _ Zero) = 1 
height (IndexNode _ _ (One t1)) = 
    1 + height t1 
height (IndexNode _ _ (Two t1 t2)) = 
    1 + (height t1 `max` height t2) 
height (IndexNode _ _ (Three t1 t2 t3)) = 
    1 + (height t1 `max` height t2 `max` height t3) 

При написании такого рода сопоставления с образцом, я настоятельно рекомендую включить предупреждения (-Wall), так что GHC скажет нам, если мы забываем обрабатывать случай.

Answer 2

сделать каждый один на Maybe:

data MultTree b = DataNode b 
       | IndexNode Int Int (Maybe (MultTree b)) (Maybe (MultTree b)) (Maybe (MultTree b)) 

Вы все еще должны предоставить все аргументы, но узел с одним ребенком может быть, например, IndexNode 3 6 Nothing (Just (DataNode "hi")) Nothing.

В качестве альтернативы, вы можете просто указать, что IndexNodeпринимает список из MultTree значений а, и только позволяют IndexNode быть создан смарт-конструктор, который проверяет количество MultTree значений добавляется к нему.

data MultTree b = DataNode b | IndexNode Int Int [MultTree b] 

mkIndexNode :: Int -> Int -> [MultTree b] -> MultTree b 
mkIndex x y nodes | length nodes > 3 = error "Too many nodes" 
        | otherwise = IndexNode x y nodes 

Вы можете заменить эту ошибку своим предпочтительным методом обработки частичных функций. (Maybe, Either и т.д.)