VPF::Haskell - Бинарные деревья - Форум программистов

mad123

Дата 11.5.2011, 12:48 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 15
Регистрация: 25.1.2011

Репутация: нет
Всего: нет

Добрый день.
Помогите, пожалуйста, написать программу на Haskell.

Выделить метку вершины дерева, имеющую наибольшее число вхождений.

mad123

Дата 17.5.2011, 12:54 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 15
Регистрация: 25.1.2011

Репутация: нет
Всего: нет

Вот мне предложили решение

Код


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 l1@(_, c1) l2@(_, 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 l1@(_, c1) l2@(_, 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

помогите подправить

Это сообщение отредактировал(а) mad123 - 17.5.2011, 12:57

Void

Дата 17.5.2011, 14:03 (ссылка)

(голосов:1)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 1
Всего: 173

Цитата(mad123 @ 17.5.2011, 14:54

)

--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)

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

mad123

Дата 17.5.2011, 14:26 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 15
Регистрация: 25.1.2011

Репутация: нет
Всего: нет

Не получилось запустить.
Выдает следующее

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

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

Как это можно решить?

Void

Дата 17.5.2011, 14:40 (ссылка)

(голосов:1)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 1
Всего: 173

Цитата(mad123 @ 17.5.2011, 16:26

)

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

Hugs, насколько я понимаю? Тогда проще оставить первоначальный вариант. Я на GHC рассчитывал.

Это сообщение отредактировал(а) Void - 17.5.2011, 14:41

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

mad123

Дата 18.5.2011, 09:11 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 15
Регистрация: 25.1.2011

Репутация: нет
Всего: нет

Спасибо, разабрался!

Это сообщение отредактировал(а) mad123 - 18.5.2011, 09:28

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Функциональные языки: общие вопросы \| Следующая тема »