Haskell, создавая двоичное дерево поиска из списка

Question

Может кто-нибудь сказать мне, почему этот код не производит то, что я хочу.

data BST = MakeNode BST String BST 
      | Empty 


add :: String -> BST -> BST 
add new Empty = (MakeNode Empty new Empty) 
add string tree@(MakeNode left value right) 
    | string > value = MakeNode left value (add string right) 
    | string < value = MakeNode (add string left) value right 
    | otherwise = tree 

выход

"John" 
    "Doug" 
     "Charlie" 

"Алиса"

listToBST :: [String] -> BST 
listToBST = foldr add Empty 

Answer 1

Я попробовал это, и это, кажется, хорошо для меня. Это может помочь, если вы представили пример ввода, для которого он не работает.

Я думаю, проблема может заключаться в том, что сравнение строк не работает так, как вы ожидаете («123» < «7», потому что «1» < «7»). Если я прав, вы можете использовать Ints вместо Strings или даже лучше, класс Ord всех типов, которые можно заказать с помощью (<).

Answer 2

Если мы создадим и выполняем функцию, которая берет BST и возвращает список в отсортированном порядке, смоделируется после сортировки. нуб, тогда ваше дерево прекрасно, как говорит нам quickcheck. QuickCheck очень прост в использовании.

import Data.List 
import Test.QuickCheck 

data BST = MakeNode BST String BST 
     | Empty 
deriving (Show) 


add :: String -> BST -> BST 
add new Empty = (MakeNode Empty new Empty) 
add string tree@(MakeNode left value right) 
    | string > value = MakeNode left value (add string right) 
    | string < value = MakeNode (add string left) value right 
    | otherwise = tree 

test = ["alice", "blup", "test", "aa"] 

manual_test = inorder (foldr add Empty test) == sort (nub test) 
prop_inorder = property inorder_test 
    where inorder_test :: [String] -> Bool 
      inorder_test xs = inorder (foldr add Empty xs) == sort (nub xs) 
-- return sorted nodes 
inorder :: BST -> [String] 
inorder (Empty) = [] 
inorder (MakeNode l x r) = inorder l ++ (x : inorder r) 

Просто загрузите ghci, а затем запустите quickCheck prop_inorder.

Другие полезные функции:

reverseOrder :: BST -> [String] 
reverseOrder Empty = [] 
reverseOrder (MakeNode l x r) = reverseOrder r ++ (x : reverseOrder r) 

asList :: BST -> [String] 
asList Empty = [] 
asList (MakeNode l x r) = x : (asList l ++ asList r) 

А также думать о том, чтобы ваше дерево более общее, параметризуя больше:

data BST a = Empty | MakeNode (BST a) a (BST a) 

Вы можете сделать это, чем экземпляр функтора, Монады, откидное и всевозможные удобные модели.