Haskell - Бинарные деревья

 
0
 
Functional languages
ava
mad123 | 11.05.2011, 13:48
Добрый день.
Помогите, пожалуйста, написать программу на Haskell.

Выделить метку вершины дерева, имеющую наибольшее число вхождений. 
Comments (5)
ava
mad123 | 17.05.2011, 12:54 #
Вот мне предложили решение

data BinTree a = Nil
               | Node a (BinTree a) (BinTree a)
                 deriving (Eq, Show)

maxLabel :: (Eq a) => BinTree a -> Maybe a
maxLabel Nil = Nothing
maxLabel tree = Just ml
    where (ml, _) = foldl1 maxLabelOcc . countLabels . labels $ tree
          maxLabelOcc [email protected](_, c1) [email protected](_, c2) =
              if c1 > c2 then l1 else l2

          labels :: BinTree a -> [a]
          labels Nil = []
          labels (Node x l r) = x : labels l ++ labels r

          countLabels :: (Eq a) => [a] -> [(a, Int)]
          countLabels list = map cnt list
              where cnt x = (x, foldl (\acc el -> acc + if x == el then 1 else 0) 0 list)


Я его подправил, но что-то не то =(


data BinTree a = Nil  | Node a (BinTree a) (BinTree a) | Leaf a

maxLabel :: (Eq a) => BinTree a -> Maybe a
maxLabel Nil = Nothing
maxLabel tree = Just ml
    where (ml, _) = foldl1 maxLabelOcc . countLabels . labels $ tree
          maxLabelOcc [email protected](_, c1) [email protected](_, c2) =
              if c1 > c2 then l1 else l2

          labels :: BinTree a -> [a]
          labels Nil = []
          --labels (Leaf x) = x
          labels (Node x l r) = x : labels l ++ labels r

          countLabels :: (Eq a) => [a] -> [(a, Int)]
          countLabels list = map cnt list
              where cnt x = (x, foldl (\acc el -> acc + if x == el then 1 else 0) 0 list)

tree = Node "alpha" (Leaf "alpha") (Node "beta" (Leaf "gamma") (Leaf "delta"))

main = print $ maxLabel tree


помогите подправить
ava
Void | 17.05.2011, 14:03 #
Цитата (mad123 @  17.5.2011,  14:54 findReferencedText)
--labels (Leaf x) = x

labels (Leaf x) = [x]

В остальном всё правильно.

Ну ещё я бы переписал maxLabelOcc и countLabels поизящнее на ФВП. countLabels квадратичная, но на одном Eq по-другому не сделаешь.
import Data.List (maximumBy)
import Data.Function (on)

data BinTree a = Nil | Node a (BinTree a) (BinTree a) | Leaf a

maxLabel :: (Eq a) => BinTree a -> Maybe a
maxLabel Nil = Nothing
maxLabel tree = Just ml
    where (ml, _) = maxLabel . countLabels . labels $ tree
          maxLabel = maximumBy (compare `on` snd)

          labels :: BinTree a -> [a]
          labels Nil = []
          labels (Leaf x) = [x]
          labels (Node x l r) = x : labels l ++ labels r

          countLabels :: (Eq a) => [a] -> [(a, Int)]
          countLabels list = map cnt list
              where cnt x = (x, length $ filter (== x) list)
ava
mad123 | 17.05.2011, 14:26 #
Не получилось запустить.
Выдает следующее

ERROR file:.\Main3.hs - Can't find imported module "Data.Function"

Как я понимаю не удалось подключить модуль.

Как это можно решить?
ava
Void | 17.05.2011, 14:40 #
Цитата (mad123 @  17.5.2011,  16:26 findReferencedText)
ERROR file:.\Main3.hs - Can't find imported module "Data.Function"

Hugs, насколько я понимаю? Тогда проще оставить первоначальный вариант. Я на GHC рассчитывал.
ava
mad123 | 18.05.2011, 09:11 #
Спасибо, разабрался!
Please register or login to write.
Firm of day
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Contributors
  Void   mad123
advanced
Submit