Real World Haskell Rozdział 3 ćwiczenia: drzewo binarne z 1 wartość konstruktor

Question

Rozdział 3 określa następujące rekurencyjną typ reprezentowania binarnego drzewa:

data Tree a = Node a (Tree a) (Tree a) 
      | Empty 
       deriving (Show) 

Ćwiczenie wymaga zaimplementować ten sam typ używając konstruktora pojedyncza wartość, przy użyciu typu „może” w odniesieniu do węzłów potomnych:

(z rozdziału 3 Ćwiczenie 2 na stronie 60)

„Określ typ drzewa, który ma tylko jeden konstruktor, jak naszym przykładzie Java Zamiast pustego. konstruktor, użyj typu Maybe w refe r do dzieci węzła. "

Rozwiązanie wymyśliłem jest następujący:

data AltTree a = AltNode a (Maybe (AltTree a)) (Maybe (AltTree a)) 
       deriving (Show) 

to jednak nie pozwala na drzewie zawierającym inne pustych drzew, takich jak:

AltNode 1 (AltNode 2 Nothing Nothing) (AltNode 3 Nothing Nothing) 

I nie jestem dlaczego "Czy nic" nie jest konstruktorem wartości typu "Być może"?

Answer 1

To nie jest konstruktor wartości Nothing, który powoduje błąd. Dwie rozgałęzione gałęzie do drzewa najwyższego poziomu powinny mieć typ Maybe (AltTree a), ale oba typy: (AltNode 2 Nothing Nothing) i (AltNode 3 Nothing Nothing) mają typ AltTree Int. Musisz użyć konstruktora wartości Just, aby utworzyć z nich wartości typu Maybe. Jak

AltNode 1 (Just (AltNode 2 Nothing Nothing)) (Just (AltNode 3 Nothing Nothing))