haskell binary search tree

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

so i'm trying to design function ins and find but i am not sure where to start.any ideas?

You should check out Chris Okasaki's Purely Functional Data Structures cs.cmu.edu/~rwh/theses/okasaki.pdf He has great ideas on how to implement all kinds of data structures in Haskell. Hint: it's going to involve recursion. — Erik Hinton
– Erik Hinton, Commented Nov 4, 2011 at 3:50
Is this homework? Also, I think an actual tutorial would make more sense than Okasaki's book or thesis. — ivanm
– ivanm, Commented Nov 4, 2011 at 5:59
@ivanm, he later expanded the thesis into an introductory textbook with exercises and all. — dfeuer
– dfeuer, Commented Feb 14, 2015 at 4:30

Landei · Accepted Answer · 2011-11-04 07:45:19Z

I have no idea by which criteria the tree should be sorted, so I use just wrd. Then it would look like:

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)

How to get there?

As always when using recursion, you need a base case. Here it is very simple: If the tree is empty, just replace it by a node containing your data. There are no children for the new node, so we use Empty.

The case if you have a full node looks more difficult, but this is just due to pattern matching, the idea is very simple: If the entry is "smaller" you need to replace the left child with a version that contains the entry, if it is "bigger" you need to replace the right child.

If both node and entry have the same "size" you have three options: keep the old node, replace it by the new one (keeping the children) or throw an error (which seems the cleanest solution, so I did it here).

Dan Burton · Accepted Answer · 2011-11-04 16:42:24Z

2

A simple generalization of Landei's answer:

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)

For this to work on Tree Entry, you will need to define an instance of Ord for Entry.

answered Nov 4, 2011 at 16:42

Dan Burton

53.9k28 gold badges122 silver badges207 bronze badges

Collectives™ on Stack Overflow

haskell binary search tree

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related