haskell二进制搜索树

Question

module Main where

import Data.List
import Data.Function

type Raw = (String, String)

icards =  [("the", "le"),("savage", "violent"),("work", "travail"),
           ("wild", "sauvage"),("chance", "occasion"),("than a", "qu'un")]

data Entry = Entry {wrd, def :: String, len :: Int, phr :: Bool}
             deriving Show

-- French-to-English, search-tree section

entries' :: [Entry]
entries' = map (\(x, y) -> Entry y x (length y) (' ' `elem` y)) icards

data Tree a = Empty | Tree a (Tree a) (Tree a)

tree :: Tree Entry
tree = build entries'

build :: [Entry] -> Tree Entry
build []     = Empty
build (e:es) = ins e (build es)

ins :: Entry -> Tree Entry -> Tree Entry

...

find :: Tree Entry -> Word -> String

...

translate' :: String -> String
translate' = unwords . (map (find tree)) . words

所以我试着设计function ins并找到，但我不确定在哪里可以start.any想法？

Answer 1

我不知道应该根据什么标准对树进行排序，所以我只使用wrd。那么它看起来就像：

ins :: Entry -> Tree Entry -> Tree Entry
ins entry Empty = Tree entry Empty Empty
ins entry@(Entry w _ _ _) (Tree current@(Entry w1 _ _ _) left right) 
   | w == w1 = error "duplicate entry"
   | w < w1 = Tree current (ins entry left) right
   | otherwise = Tree current left (ins entry right)  

怎么去那里？

像往常一样，在使用递归时，您需要一个基本情况。这里非常简单:如果树是空的，只需将其替换为包含数据的节点。新节点没有子节点，因此我们使用Empty。

如果你有一个完整的节点，这种情况看起来比较困难，但这只是因为模式匹配，想法很简单:如果条目“小”，你需要用包含条目的版本替换左子节点，如果它“大”，你需要替换右子节点。

如果节点和条目都有相同的“大小”，你有三个选择:保留旧节点，用新节点替换它(保留子节点)，或者抛出一个错误(这似乎是最干净的解决方案，所以我在这里做了)。

Answer 2

简单概括一下兰代的答案：

ins :: Ord a => a -> Tree a -> Tree a
ins x Empty = Tree x Empty Empty
ins x (Tree x' l r) = case compare x x' of
  EQ -> undefined
  LT -> Tree x' (ins x l) r
  GT -> Tree x' l (ins x r)

为了在Tree Entry上工作，您需要为Entry定义一个Ord实例。