Бинарное дерево поиска haskell

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

поэтому я пытаюсь спроектировать функциональные входы и найти, но я не уверен, с чего начать. Есть идеи?


haskell binary-search-tree
person padawan    schedule 04.11.2011    source источник
comment
Вам следует ознакомиться с «Чисто функциональными структурами данных» Криса Окасаки cs.cmu.edu/~ rwh/theses/okasaki.pdf У него есть отличные идеи о том, как реализовать все виды структур данных в Haskell. Подсказка: это будет связано с рекурсией.   -  person Erik Hinton    schedule 04.11.2011
comment
Это домашнее задание? Кроме того, я думаю, что реальный учебник имел бы больше смысла, чем книга или диссертация Окасаки.   -  person ivanm    schedule 04.11.2011
comment
@ivanm, он позже расширил диссертацию до вводного учебника с упражнениями и всем остальным.   -  person dfeuer    schedule 14.02.2015

Ответы (2)


arrow_upward
2
arrow_downward

Я понятия не имею, по каким критериям нужно сортировать дерево, поэтому использую только 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.

Случай, когда у вас есть полный узел, выглядит более сложным, но это как раз из-за сопоставления с образцом, идея очень проста: если запись «меньше», вам нужно заменить левый дочерний вариант версией, которая содержит запись, если это «больше», вам нужно заменить правого ребенка.

Если и узел, и запись имеют одинаковый «размер», у вас есть три варианта: сохранить старый узел, заменить его новым (с сохранением дочерних элементов) или выдать ошибку (что кажется самым чистым решением, поэтому я сделал это здесь).

person Landei    schedule 04.11.2011

arrow_upward
2
arrow_downward

Простое обобщение ответа Ландея:

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, вам нужно определить экземпляр Ord для Entry.

person Dan Burton    schedule 04.11.2011