Haskell. BinaryTree. Помогите найти ошибку в синтаксисе.

[Pulseofmalstrem]

Я в качестве практики самостоятельно реализовал тип данных бинарное дерево и даже начал писать для нужные лично мне функции, но компилятор ругается на такое оформление (хотя я точно сверил с учебником там все так же), помогите разобраться в чем же тут дело.

Используется синтаксис Haskell

module Main where

data BTree a = Nil | Node a (Btree a) (Btree a)
                     deriving (Eq, Show)

empty :: (Ord a) => Btree a
empty = Nil

node :: (Ord a) => a -> BTree a -> Btree a -> Btree a
node value lefttree righttree = Node value lefttree righttree

leaf :: (Ord a) => a -> Btree a
leaf a = Node a empty empty

getLeftTree :: (Ord a) => Btree a -> Btree a
getLeftTree Node _ lefttree _ = lefttree

getRightTree :: (Ord a) => Btree a -> Btree a
getRightTree Node _ _ righttree = righttree

root :: (Ord a) => Btree a -> a
root Node value _ _ = value

isNil :: (Ord a) => Btree a -> Bool
isNil Nil = True
isNil _ = False

isNonNil :: (Ord a) => Btree a -> Bool
isNonNil Node _ _ _ = True
isNonNil _ = False

insertTree :: a -> Btree a -> Btree a
insertTree x tree | isNil tree = leaf x
                  | x >= root tree = if isNonNil getRightTree tree then node(root tree, insertTree x getLeftTree(tree), getRightTree(tree))
                                                                   else node(root tree, getLeftTree tree, insertTree x getRightTree(tree))
                  | otherwise = if isNonNil getRightTree tree then node (x, insertTree root(tree) getLeftTree(tree), getRightTree tree)
                                                              else node (x, getLeftTree tree, insertTree root(tree) getRightTree(tree))



main :: IO()
main = print root (insertTree 100 insertTree 8 insertTree 50 empty)
 

На функцию main винимание не обращайте это банальный тестовый вариант для функции insertTree. Ошибку выдает в четвертой строке (после ключевого слова data)

[Xaositect]

А Вы ошибку внимательно прочитали? По-моему, там ясно написано:

    Not in scope: type constructor or class ‘Btree’
    Perhaps you meant ‘BTree’ (line 3)

То бишь Вы один раз написали BTree, а потом везде Btree.

[Pulseofmalstrem]

Xaositect в сообщении #1028258 писал(а):

А Вы ошибку внимательно прочитали? По-моему, там ясно написано:

    Not in scope: type constructor or class ‘Btree’
    Perhaps you meant ‘BTree’ (line 3)

То бишь Вы один раз написали BTree, а потом везде Btree.

Это обидно, конечно. Но там дальше еще одна ошибка: несоответствие кучи сигнтатур, буду думать.
Выловил, большую часть. Осталось еще одна...

-- 17.06.2015, 21:05 --

data  BTree a = Nil
              | Node a BTree a BTree a
                deriving (Eq, Show)

Ошибка следующая вылетает в несоответсвии типовой декларации - почему-то.

[Xaositect]

Процитируйте целиком ошибку, я же не знаю, как Вы там все исправили.

-- Ср июн 17, 2015 20:10:53 --

А, тут скобки нужны. Node a (BTree a) (BTree a)

[Pulseofmalstrem]

Xaositect

Цитата:

Expecting one more argument to 'BTree'
Expected a type, but 'Btree has kind * -> *
In the type 'Btree'
In the definition of data constructor 'Node'
In the data declaration for 'BTree'

[Xaositect]

Ну да, как я и сказал, там нужны скобки.
Если написать без скобок, Node a BTree a BTree a, то компилятор думает, что Node - это конструктор с 5 аргументами типов a, BTree, a, BTree, a. А BTree у нас не тип, а конструктор типов (* -> * в ошибке говорит как раз об этом). Надо ставить скобки, чтобы было 3 аргумента типов a, BTree a, BTree a, вот так: Node a (BTree a) (BTree a).

[Pulseofmalstrem]

Xaositect
Спасибо все теперь заработало, с остальным справился сам. Благодарю за участие.

P.S. Haskell и функциональное программирование мне нравится все больше и больше.

[arseniiv]

Стоп, а строка root Node value _ _ = value (и подобные в getLeftTree и getRightTree) разве ошибку не даёт? Тут тоже нужны скобки: root (Node value _ _).

P. S. А-а, я вчитался, вы сами заметили, ясно.

Кстати, можно было бы использовать record syntax вот так:

Используется синтаксис Haskell

data BTree a = Nil | Node {
    root :: a,
    getLeftTree :: BTree a,
    getRightTree :: BTree a
} deriving (Eq, Show)

и тогда:
(1) три функции, которые вы писали выше, определятся автоматически;
(2) можно будет писать шаблоны вида Node { root = a, getRightTree = t }, что эквивалентно Node a _ t;
(3) можно будет получать значения с конструктором Node «обновлением» других значений [неудачное слово, но так иногда зовут; исходное значение остаётся неизменным как и обещали на обложке ] с тем же конструктором, копируя все поля кроме указанных: value { getLeftTree = Nil } будет иметь первое и третье поля такие же, какие у value, а второе будет равно Nil.

Видимо, в вашем учебнике record syntax позже рассматривается.

(Совсем далеко.)

Кстати, в будущем стоит избегать таких частичных функций типа вот этих или head, tail, fromJust и т. д.: типизация не защитит от случайной передачи в код с ними значения, на котором они не определены. Вместо них лучше использовать в соответствующем месте case (который, конечно, тоже можно нечайно сделать частичным…) или, в случае использования Maybe и Either как монад вычисления с возможной ошибкой, использовать do. Это так, на будущее.

[Pulseofmalstrem]

Кстати можете подсказать функцию, которая умеет считывать строку из цифирь с пробелами и возвращать список.
То есть выдавать такой ввод 1 10 13 25 -> [1, 10, 13, 25] в такой вот вывод?

[arseniiv]

Тут лучше использовать parser combinators, но вряд ли они будут понятны сразу же, а встроенной функции специально для этого нет. Можно прочитать строку вида "[1,10,13,25]" с помощью read "..." :: [Int], но заменять пробелы запятыми и добавлять скобки, чтобы прийти к этому от того, что есть, было бы плохой идеей.

[Pulseofmalstrem]

Нашел ошибку в логике!

[arseniiv]

Вот тут:

Pulseofmalstrem в сообщении #1028591 писал(а):

Используется синтаксис Haskell

pop tree | (isSingleBranch tree) = tree

вы забыли что-то удалить из возвращаемого значения, так что если сюда попадаем, потом не вылезаем из treeOutput.

[Pulseofmalstrem]

arseniiv

Я уже понял, нам нужно потомков отрезать.

[Pulseofmalstrem]

Продолжая работу, продвинулся еще чуть дальше (да тяжело идет постоянно встречаю тупики), я сумел оптимизировать немножко функцию вставки, и немножко подкорректировать функцию удаления (теперь бесконечной рекурсии нет, однако при выводе случается тупик, так как функция root упирается в пустоту.

Используется синтаксис Haskell

module Main where

data BTree a = Nil |  Node a (BTree a) (BTree a)
                      deriving (Eq, Show)
root :: BTree Int -> Int
root (Node a _ _) = a

getLeftBranch :: BTree Int -> BTree Int
getLeftBranch (Node _ b _) = b

getRightBranch :: BTree Int -> BTree Int
getRightBranch (Node _ _ c) = c

isNil :: BTree Int -> Bool
isNil Nil = True
isNil _ = False

isNonNil :: BTree Int -> Bool
isNonNil (Node _ _ _) = True
isNonNil _ = False

isLeaf :: BTree Int -> Bool
isLeaf (Node _ Nil Nil) = False
isLeaf _ = False

empty ::  BTree Int
empty = Nil

leaf :: Int -> BTree Int
leaf a = Node a Nil Nil

deepTree :: BTree Int -> Int
deepTree tree | (isNil tree) = 0
              | (isLeaf tree) = 1
              | otherwise = if deepTree (getRightBranch tree) >= deepTree (getLeftBranch tree) then 1 + deepTree (getRightBranch tree)
                                                                                               else 1 + deepTree (getLeftBranch tree)

insertTree :: Int -> BTree Int -> BTree Int
insertTree x tree | (isNil tree) = leaf x
                  | deepTree (getLeftBranch tree) <= deepTree (getRightBranch tree) = if x >= root tree then Node (root tree) (insertTree x (getLeftBranch tree)) (getRightBranch tree)
                                                                                                        else Node x (insertTree (root tree) (getLeftBranch tree)) (getRightBranch tree)
                  | otherwise = if x >= root tree then Node (root tree) (getLeftBranch tree) (insertTree x (getRightBranch tree))
                                                  else Node x (getLeftBranch tree) (insertTree (root tree) (getRightBranch tree))

pop :: BTree Int -> BTree Int
pop tree | (isLeaf tree) = empty
         | (isNil (getRightBranch tree)) = Node (root (getLeftBranch tree)) (pop (getLeftBranch tree)) (empty)
         | (isNil (getLeftBranch tree)) = Node (root (getRightBranch tree)) (empty) (pop (getRightBranch tree))
         | otherwise = if root (getLeftBranch tree) <= root (getRightBranch tree) then Node (root (getLeftBranch tree)) (pop (getLeftBranch tree)) (empty)
                                                                                  else Node (root (getRightBranch tree)) (empty) (pop (getRightBranch tree))

fromListtoTree :: [Int] -> BTree Int -> BTree Int
fromListtoTree [] tree = tree
fromListtoTree (x:xs) tree = fromListtoTree xs (insertTree x tree)

treeOutput :: BTree Int -> IO()
treeOutput tree | (isNil tree) = print ""
                | otherwise =  do print (root tree)
                                  treeOutput (pop tree)

main :: IO()
main = treeOutput (fromListtoTree [1, 2, 3, 4, 5, 6, 7] (empty))

И я честно не понимаю, где ошибка. На бумаге мой алгоритм работает, я пытался донести до Haskell следующие декларации (где в коде ошибка):

deepTree tree : Глубина пустого дерева - 0
Глубина непустого дерева - 1 + глубина "самого глубокого потомка"

insertTree x tree: Когда вставляем х в пустоту, то ответ листовая вершина с х.
Когда вставляем х в непустое дерево, то если х больше значения внутри дерева, тогда ответ дерево внутри которого прежнее значение, вставка х в потомка с наименьшей глубиной, и оставшийся потомок, иначе ответ есть дерево внутри которого х, один потомок которого есть вставка значения, хранившегося в этой веришине в потомка наименьшей глубины, и другой нетронутый потомок..

pop tree: Когда выбрасываем значение вершины листовой вершины - получаем пустоту.
Когда выбрасываем значение вершины из вершины, имеющей лишь 1 потомка - ответ есть дерево, внутри которого значение единственного потомка, а потомок такого дерева - изначальный потомок с выкинутой веришиной.
Когда выбрасываем значение из узла, то ответом является дерево внутри которого значение наименьшего из потомков, а его потомки - один нетронутый потомок и потомок с отброшенной веришиной.

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

P.S. Заранее благодарю за помощь, извините что я такой тугодум.

[Xaositect]

У Вас isLeaf неправильный.

А частичные функции все-таки зло, потом, когда разберетесь с монадами Maybe/Either, Вы это поймете.