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

Я пытаюсь создать функцию предварительного заказа для обхода IntTree.

Класс дерева выглядит следующим образом

data IntTree = Empty | Branch IntTree Int IntTree deriving (Show, Eq)

У меня два вопроса 1. Я получаю ошибки, как показано ниже.

E:\Haskell\Uebungsblatt_2_Aufgabe_2_a.hs:7:14: error:
    * Expected kind `* -> Constraint', but `IntTree' has kind `*'
    * In the type signature: preorder :: (IntTree c) => c -> [a]
  |
7 | preorder :: (IntTree c) => c->[a]

  |              ^^^^^^^^^
[Finished in 0.5s]

Я не понимаю, почему. Они произошли в этой следующей строке

preorder :: (IntTree c) => c->[a]

  1. Я думаю, что следующая строка неверна. Я думаю, что мне нужно написать другие выражения вместо "l: preorder a: preorder r:[]"

preorder Branch a l r = l : preorder a : preorder r:[]

Заранее благодарю за помощь!!

main :: IO ()    -- This says that main is an IO action.
main = return () -- This tells main to do nothing

data IntTree = Empty | Branch IntTree Int IntTree deriving (Show, Eq)


preorder :: (IntTree c) => c->[a]
preorder Empty = []
preorder Branch Empty x Empty = [x]
preorder Branch a l r = l : preorder a : preorder r:[]

haskell preorder
person Leonhard Felix    schedule 23.04.2019    source источник

Ответы (2)


arrow_upward
2
arrow_downward

На вопрос 1:

preorder :: (IntTree c) => c->[a]

Вы путаете классы и типы данных. IntTree был объявлен с data, поэтому это не класс типов, а обычный тип данных, такой как Bool или Int. Он используется так же:

preorder :: IntTree -> [a]

Во-вторых, вы не возвращаете список любого типа a (строчные буквы — это тип переменных), вы возвращаете именно список Int, потому что это то, что содержит дерево. Итак, вы должны сказать так:

preorder :: IntTree -> [Int]
person luqui    schedule 23.04.2019

arrow_upward
2
arrow_downward

По вопросу 1: подпись

preorder :: (IntTree c) => c->[a]

неверно: IntTree — это не класс типов, это простой тип, поэтому мы можем использовать его как есть.

preorder :: IntTree -> [Int]

Конечным типом должен быть Int, так как мы создаем список целых чисел, а не список [a] для любого a.

Для вопроса 2: : добавляет элемент в начало списка, он имеет тип

(:) :: a -> [a] -> [a]

Следовательно, он не объединяет два списка. Для этого используйте вместо

(++) :: [a] -> [a] -> [a]

as in

preorder (Branch a l r) = l : preorder a ++ preorder r

(Нет необходимости использовать ++ [] в конце)

person chi    schedule 23.04.2019
comment
О, черт возьми, вы добавили раздел вопроса 1. Мне понравился наш однозначный двойной ответ. - person luqui; 23.04.2019
comment
@luqui Я понял, что был вопрос 1 после того, как ответил на вопрос 2, поэтому я сначала пометил ответ как только Q2 и начал редактировать, чтобы завершить ответ. Да, разделенные ответы выглядели лучше, в каком-то эстетическом смысле :) - person chi; 23.04.2019
comment
Только что поправил после ваших советов. Но есть еще одна ошибка в следующей строке: preorder Empty = []. Ошибка E:\Haskell\Uebungsblatt_2_Aufgabe_2_a.hs:8:1: error: Equations for `preorder' have different numbers of arguments E:\Haskell\Uebungsblatt_2_Aufgabe_2_a.hs:8:1-19 E:\Haskell\Uebungsblatt_2_Aufgabe_2_a.hs:9:1-35 | 8 | preorder Empty = [] | ^^^^^^^^^^^^^^^^^^^^... [Finished in 0.5s] @chi @luqui - person Leonhard Felix; 23.04.2019
comment
@LeonhardFelix Вам нужно больше скобок: preorder Branch a l r = ... - это функция, которая принимает 4 аргумента, а вам нужно preorder (Branch a l r) = .... Я отредактировал свой ответ соответственно. - person chi; 23.04.2019
comment
@chi Большое спасибо - person Leonhard Felix; 23.04.2019