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?
