[Haskell-cafe] Trying to implement this code

Dmitry Vyal akamaus at gmail.com
Mon Apr 18 16:57:26 EDT 2005

Lizz Ross wrote:
> Hi im new to Haskell (really just learning).
> Im trying to code a function to take in a List of Strings (e.g.) [apple, orange,
> banana, orange, apple, orange] , and create 
> a binary search tree containing the Strings and integers (where the integers are
> the number of occurrences of each word.

I think you can use something like this to get statistics about repeats:

data (Ord a, Updateable a) => BinTree a =
     Leaf | Node (BinTree a) a (BinTree a)

class Updateable a where
     update :: a -> a

data Word_stat = Word_stat String Int deriving Show

instance Eq (Word_stat) where
     (==) (Word_stat s1 _) (Word_stat s2 _) = s1 == s2

instance Ord (Word_stat) where
     (Word_stat s1 _) < (Word_stat s2 _) = s1<s2

instance Updateable (Word_stat) where
     update (Word_stat s i) = Word_stat s (i+1)
-- inserts new element in the tree or updates existing one
ins_in_tree :: (Ord a, Updateable a) => BinTree a -> a -> BinTree a
ins_in_tree Leaf el = Node Leaf el Leaf
ins_in_tree (Node left cur right) el
     | el < cur = Node (ins_in_tree left el) cur right
     | el == cur = Node left (update cur) right
     | otherwise = Node left cur (ins_in_tree right el)
-- loads list of strings in the tree
ins_list :: [String] -> BinTree Word_stat
ins_list lst = foldl ins_in_tree  Leaf (map wrap lst)
     where wrap :: String -> Word_stat
	  wrap s = Word_stat s 1
--traverses the tree
flat_tree :: (Ord a, Updateable a) => BinTree a -> [a]
flat_tree Leaf = []
flat_tree (Node left el right) =
     (flat_tree left) ++ [el] ++ (flat_tree right)

-- function you probably need
summary :: [String] -> [Word_stat]
summary lst  = flat_tree $ ins_list lst

Am not sure about the relevance of this approach as i have very little
experience with Haskell and FP. So it would be great if someone offers
better solution.

Why doesnt translator automatically deduce constraints in type of
ins_in_tree and flat_tree functions so i need to explicitly define them?

More information about the Haskell-Cafe mailing list