Общее дерево в Haskell = розовое дерево? Постодер для розового дерева?

Я должен был создать структуру данных для дерева, где каждый узел имеет неопределенное количество ветвей. Я предполагаю, что это будет розовое дерево.

data GTree a = Node a [GTree a]

Теперь я должен написать функцию postorderG, которая даст мне список всех моих элементов в моем общем в последовательности постпорядка. Я написал это, но это не кажется правильным... Может ли кто-нибудь мне помочь?

postorderG :: GTree a -> [a]
postorderG (Node x l r) = postorder l ++ postorder r ++ [GTree x]

tree haskell postorder
person Gloria95    schedule 11.08.2018    source источник
comment
Конструктор Node имеет только два аргумента, поэтому ваша деструктуризация будет выглядеть как postorderG (Node x children). Я предлагаю вам взглянуть на concatMap и отметить, что postorderG имеет требуемый тип для первого аргумента.   -  person Lee    schedule 11.08.2018

Ответы (1)


arrow_upward
0
arrow_downward

GTree — это конструктор типа, а не конструктор данных; дерево будет создано с Node x [], а не GTree x.

Однако здесь вообще не нужно создавать дерево. Вам просто нужно значение, хранящееся в корне входного дерева для окончательного списка в возвращаемом значении.

postorderG :: GTree a -> [a]
postorderG (Node x ch) =  concatMap postorderG ch -- [a]
                          ++ [x]         -- [a], not [GTree a]

Если вы хотите, вы можете создать одноэлементное дерево для добавления к ch, применить postOrderG к каждому дочернему элементу и новому синглтону по порядку.

postorderG (Node x ch) = concatMap postorderG (ch ++ [Node x []])

Воспользовавшись монадой [] вместо использования concatMap, RHS будет выглядеть так:

(ch >>= postorderG) ++ [x]

or

(ch ++ [Node x []]) >>= postorderG
person chepner    schedule 12.08.2018