алгебраический тип данных для дерева

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

data Children a = NoChildren | Cons a (Children a) deriving (Show, Read, Ord, Eq)
data Tree a = EmptyTree | Node a (Children a) deriving (Show, Read, Ord, Eq)

теперь я пытаюсь создать такое дерево

let subtree1 = Node 67 NoChildren
let subtree2 = Node 86 NoChildren
let tree1 = Node 83 (subtree1 `Cons` (subtree2 `Cons` NoChildren))

он отлично работает до subtree2. дерево1 не создается. Выдается такая ошибка -

<interactive>:96:15:
    No instance for (Num (Tree Integer))
      arising from the literal `83'
    Possible fix: add an instance declaration for (Num (Tree Integer))
    In the first argument of `Node', namely `83'
    In the expression: Node 81 (subtree1 `Cons` (subtree2 `Cons` NoChildren))
    In an equation for `tree1':
      tree1 = Node 81 (subtree1 `Cons` (subtree2 `Cons` NoChildren))

Я вообще не понимаю эту ошибку. Почему он жалуется, что 83 - литерал. у subtree1 и subtree2 тоже были литералы, и они были в порядке...

Я решил проблему, выполнив следующие действия

data Tree a = EmptyTree | Node a [Tree a] deriving (Show, Read, Ord, Eq)

flatten [] = []
flatten x:xs = x ++ flatten xs

preorder EmptyTree = []
preorder (Node a []) = [a]
preorder (Node a children) = [a] ++ flatten (map preorder children)

tree haskell algebraic-data-types
person shashydhar    schedule 15.01.2013    source источник

Ответы (1)


arrow_upward
4
arrow_downward 

data Children a = NoChildren | Cons a (Children a)

означает, что ваш Children a изоморфен [a], и, следовательно, ваш

data Tree a = EmptyTree | Node a (Children a)

изоморфен

data List a = Empty | Nonempty a [a]

который снова изоморфен [a].

Вы хотите, чтобы сами дети были Trees, поэтому вы должны использовать

data Children a = NoChildren | Cons (Tree a) (Children a)

или простой

data Tree a = EmptyTree | Node a [Tree a]

Ошибка в том, что subtree1 имеет тип Tree a для некоторого a, принадлежащего Num (то же самое для subtree2). Затем, когда вы пишете

tree1 = Node 83 (subtree1 `Cons` (subtree2 `Cons` NoChildren))

предполагаемый тип tree1 - это Tree (Tree a) (для некоторого a, принадлежащего Num), и, следовательно,

83 :: Tree a

Но нет экземпляра Num для Trees.

person Daniel Fischer    schedule 15.01.2013
comment
спасибо за ответ и объяснение. Я использовал [Tree a], но это давало ужасную ошибку невозможности построения бесконечного типа. Я решил и это. - person shashydhar; 15.01.2013