почему это был бесконечный тип? (Происходит проверка: невозможно построить бесконечный тип: a ~ Tree a) - PullRequest
Новая
       61

почему это был бесконечный тип? (Происходит проверка: невозможно построить бесконечный тип: a ~ Tree a)

1 голос
/ 12 июля 2020 
data Tree a = Branch a a | Leaf deriving (Show)

construct :: (Integral a) => [a] -> Tree a
construct [] = Leaf
construct (x:[]) = Leaf                -- _____error________
construct (l:r:xs) = if l>r then Branch l (construct $ r:xs) 
                            else Branch (construct $ l:xs) r

* Occurs check: cannot construct the infinite type: a ~ Tree a
* In the second argument of `Branch', namely `(construct $ r : xs)'
  In the expression: Branch l (construct $ r : xs)
  In the expression:
    if l > r then
        Branch l (construct $ r : xs)
    else
        Branch (construct $ l : xs) r
* Relevant bindings include
    xs :: [a] (bound at C:\Stuff\code\New folder (2)\try.hs:69:16)
    r :: a (bound at C:\Stuff\code\New folder (2)\try.hs:69:14)
    l :: a (bound at C:\Stuff\code\New folder (2)\try.hs:69:12)
    construct :: [a] -> Tree a

почему это был бесконечный тип? Этот «бесконечный тип» является вводом или выводом?

, а также, если я изменю construct (x:[]) = Leaf на construct (x:[]) = x, то ошибка возникает в этом x. Почему?

1 Ответ

7 голосов
/ 12 июля 2020

Давайте начнем с начала: 

data Tree a = Branch a a | Leaf deriving(Show)

Это «дерево» по определению будет содержать ровно два a значения (в Branch) или ни одного (Leaf) . Я не уверен, почему это называется деревом. Похоже, вы не собирались этого делать. Возможно, вы хотели 

data Tree a = Branch (Tree a) (Tree a) | Leaf a deriving(Show)

, которое представляет собой дерево со значениями a в листьях. Или, в качестве альтернативы, 

data Tree a = Branch a (Tree a) (Tree a) | Leaf deriving(Show)

, которое представляет собой дерево со значениями a во внутренних узлах.

В любом случае, давайте рассмотрим вашу проблему: 

construct :: (Integral a) => [a] -> Tree a
construct (l:r:xs) = if l>r then Branch l (construct $ r:xs) else ...

Здесь , l имеет тип a. Кроме того, construct $ r:xs дает значение типа Tree a. Следовательно, они имеют разные типы: a vs Tree a.

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

 a ~ Tree a

, но это сразу же терпит неудачу, поскольку единственным решением будет несуществующий бесконечный тип 

a = Tree (Tree (Tree ...))

Наконец, чтобы исправить ваш код, вам нужно будет изменить тип вашего дерева так, чтобы оно действительно было деревом. После этого вам нужно будет адаптировать код construct к новому типу.

Если я изменю construct (x:[]) = Leaf на construct (x:[]) = x, то ошибка возникает в этом x. Почему?

Поскольку x имеет тип a, однако подпись construct обещает Tree a, следовательно, требует a ~ Tree a, как и в предыдущем случае.

...