Haskell Task 2

import Text.Printf

data BinaryTree = EmptyTree
        | Node Integer BinaryTree BinaryTree

-- Добавление элемента
insert :: BinaryTree -> Integer -> BinaryTree
insert EmptyTree y = Node y EmptyTree EmptyTree
insert (Node value left right) y
        | (y == value) = Node value left right
        | (y > value) = Node value left (insert right y)
        | (y < value) = Node value (insert left y) right

-- Удаление элемента
remove :: BinaryTree -> Integer -> BinaryTree
remove EmptyTree _ = error "No such element"
remove (Node value left right) y
        | (y > value) = Node value left (remove right y)
        | (y < value) = Node value (remove left y) right
        | (y == value) = removeNode (Node value left right) y

removeNode :: BinaryTree -> Integer -> BinaryTree
removeNode (Node value EmptyTree EmptyTree) y = EmptyTree
removeNode (Node value left EmptyTree) y = left
removeNode (Node value EmptyTree right) y = right
removeNode (Node value left right) y =
        let nearest = nearestGE right value in
        Node nearest left (remove right nearest)

-- Создание пустого дерева
emptyTree :: BinaryTree
emptyTree   = EmptyTree

--Поиск элемента в дереве
containsElement :: BinaryTree -> Integer -> Bool
containsElement EmptyTree _ = False

containsElement (Node value left right) y
        | (y == value) = True
        | (y < value) = containsElement left y
        | (y > value) = containsElement right y

-- Поиск в дереве наименьшего элемента, который больше или равен заданному
nearestGE :: BinaryTree -> Integer -> Integer
nearestGE EmptyTree y = y-1 -- вернем заведомо неподходящее решение
nearestGE (Node x left right) y
        | (x == y) = y
        | (x < y) = nearestGE right y -- текущий узел заведомо не подходит, остается только искать вглубь
        | (x > y) = let result = nearestGE left y in
            if result >= y then min x result else x -- минимальное из найденных, но при этом корректное

-- Создание дерева из списка
treeFromList :: [Integer] -> BinaryTree
treeFromList list = foldl insert EmptyTree list

-- Создание списка из дерева
listFromTree :: BinaryTree -> [Integer]
listFromTree EmptyTree = []
listFromTree (Node x left right) = (listFromTree left) ++ x : (listFromTree right)

-- Вывод в формате Graphviz
treeToDot :: BinaryTree -> String
treeToDot (Node x left right) = printf "digraph BST {\n%s%s}\n" (showNode left "left" x) (showNode right "right" x);

showNode :: BinaryTree -> String -> Integer -> String
showNode EmptyTree name parent = printf "null_%d_%s [shape=point];\n%d -> null_%d_%s;\n" parent name parent parent name
showNode (Node x left right) name parent =
        (printf "%d -> %d;\n" parent x) ++ (showNode left "left" x) ++ (showNode right "right" x)

instance Show BinaryTree where
  show t = treeToDot t

-- "dot -Tps2 graph.dot -o graph.ps" for multipage
main = do
        let tree1 = treeFromList [7,3,11,5]
        putStrLn (show tree1)
        putStrLn (show (tree1 `insert` 4 `insert` 1))
        putStrLn (show (remove tree1 3))