Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Haskell
Перезагрузить страницу Требуется решение лабораторной работы
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
kaffetka1841 kaffetka1841 вне форума
Member
 
Сообщений: 22
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.12.2009
По умолчанию Требуется решение лабораторной работы - 09.12.2009, 18:22

Эта последняя, больше не будет, помогите с решением, эту лабу даже решать не пробовала, просто бесполезно. Если не трудно, то помогите, пожалуйста!!!

Лексические деревья (trie-деревья) используются для представле-
ния словарей. Каждый узел дерева содержит следующую информа-
цию: символ, булевское значение и список поддеревьев (у каждо-
го узла может быть произвольное количество дочерних деревьев).


Булевское значение, равное
True отмечает конец слова, читаемого, начиная с корня дерева. Таким
образом, в дереве представлены слова fa, false, far, fare, fact, fried,
frieze. Определите следующие функции:


• exists, которая проверяет, что заданное слово содержится в
trie-дереве.
• insert, которая по дереву и слову возвращает новое дерево,
в которое включено это слово. Если слово уже содержится в
дереве, оно должно возвращаться без изменений.
• completions, которая по заданной строке возвращает список
всех слов из дерева, началом которых служит указанная стро-
ка (например, для приведенного на рис. 1 дерева по строке
"fri" должен возвращаться список ["fried","frieze"].)
Ответить с цитированием
  (#2 (permalink)) Старый
calabi-yau calabi-yau вне форума
Member
 
Сообщений: 338
Сказал(а) спасибо: 0
Поблагодарили 10 раз(а) в 10 сообщениях
Регистрация: 28.09.2009
По умолчанию 11.12.2009, 12:03

Код:
import Control.Exception
import System.IO
import Data.List


data LTree = Node {
            char :: Char, end :: Bool, sub :: [LTree]
     } deriving Show

foldLTree :: LTree -> [String]
foldLTree d = let foldLTree' (Node char b sub') s 
                        | null sub' = word'
                        | otherwise = (
                                if b then word' else []
                          ) ++ concatMap (flip foldLTree' $ word') sub'                       
                    where word' = map (char:) s
              in  map reverse $ foldLTree' d [[]]



build :: String -> LTree
build str | null str  = undefined
          | otherwise = let build' (s:[]) = Node s False []
                            build' (s:sx) = Node s False [build sx]  
                        in build' str


build' :: [String] -> LTree
build' []     = error ""
build' (x:xs) = foldl (insert') (build x) xs


exist :: LTree -> String -> Bool
exist d str = any (str == ) $ foldLTree d

insert' :: LTree ->String -> LTree
insert' d [] = d
insert' d str@(s:st) | exist  d str = d
                     | char d /= s = error "Error: unspecified behaviour"
                     | otherwise = d {sub = (sub d) `update'` st}
    where update' :: [LTree] -> String -> [LTree]
          update' d str'@(s:st) = 
               case findIndex (\node -> char node == s) d of
                       Just index -> let (a, (b:bs)) = splitAt index d
                                     in a ++ (if (or [null $ sub b, null st]) 
                                                 then b {end = True}
                                                 else b) 
                                             {sub = (sub b) `update'` st} : bs                  
                       _          -> build str' : d
    
completions :: String -> LTree -> [String]
completions str d = filter (isPrefixOf str) $ foldLTree d

ltree = build' ["fa", "false", "far", "fare", "fact", "friend", "frize"]

main = do {
    print $ exist ltree "far";

    (print $ foldLTree $ ltree `insert'` "friday")
        `Control.Exception.catch` 
            (print . (show :: Control.Exception.SomeException -> String)); -- ловим наше исключение. см выше.

    print $ completions "fr" ltree;
}
Ответить с цитированием
  (#3 (permalink)) Старый
kaffetka1841 kaffetka1841 вне форума
Member
 
Сообщений: 22
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.12.2009
По умолчанию 11.12.2009, 18:06

спасибо=)
Ответить с цитированием
  (#4 (permalink)) Старый
kaffetka1841 kaffetka1841 вне форума
Member
 
Сообщений: 22
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.12.2009
По умолчанию 12.12.2009, 21:25

calabi-yau, а для чего нам нужно
import Control.Exception
import System.IO
import Data.List
Ответить с цитированием
  (#5 (permalink)) Старый
AD AD вне форума
Member
 
Сообщений: 575
Сказал(а) спасибо: 7
Поблагодарили 3 раз(а) в 3 сообщениях
Регистрация: 15.07.2009
По умолчанию 13.12.2009, 00:53

Цитата:
calabi-yau, а для чего нам нужно
import Control.Exception
import System.IO
import Data.List
Насколько я понимаю, для того, чтобы можно было пользоваться стандартными функциями исключений, ввода/вывода, и списковыми структурами Хаскеля.
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
kaffetka1841 kaffetka1841 вне форума
Member
 
Сообщений: 22
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.12.2009
По умолчанию 15.12.2009, 00:25

Эту лабу можно тоже адаптировать без всяких сложностей типо import Control.Exception
import System.IO
import Data.List и $ reverse и т.д Ну если это возможно..
Ответить с цитированием
  (#7 (permalink)) Старый
Vladimir the Red Sunny Vladimir the Red Sunny вне форума
Member
 
Сообщений: 4,232
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 15.05.2003
По умолчанию 15.12.2009, 01:05

Сдавайте так. Скажете, что ночей не спали, учили Хаскель вместо сна, еды и секса! У препода же сердце не каменное...
Ответить с цитированием
  (#8 (permalink)) Старый
kaffetka1841 kaffetka1841 вне форума
Member
 
Сообщений: 22
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.12.2009
По умолчанию 15.12.2009, 09:38

Факт в том, что мы это не проходили, это будет на следующем семестре, и эта программа больше похожа па питон, чем на хаскель...
Ответить с цитированием
  (#9 (permalink)) Старый
calabi-yau calabi-yau вне форума
Member
 
Сообщений: 338
Сказал(а) спасибо: 0
Поблагодарили 10 раз(а) в 10 сообщениях
Регистрация: 28.09.2009
По умолчанию 15.12.2009, 12:46

Цитата:
Эту лабу можно тоже адаптировать без всяких сложностей типо import Control.Exception
import System.IO
import Data.List и $ reverse и т.д Ну если это возможно..
Адаптированно, но потенциально небезопасно (эх, у нас если программа падала на тестовых данных - автоматом переcдача, даже код не смотрели )!
Код:
data LTree = Node Char Bool [LTree] deriving Show


foldLTree :: LTree -> [String]
foldLTree d = let foldLTree' (Node char b sub') s 
                        | null sub' = word'
                        | otherwise = (
                                if b then word' else []
                          ) ++ concatMap (\s -> foldLTree' s word') sub'                       
                    where word' = map (++[char]) s
              in foldLTree' d [[]]


build :: String -> LTree
build str | null str  = undefined
          | otherwise = let build' (s:[]) = Node s True  []
                            build' (s:sx) = Node s False [build sx]  
                        in build' str


build' :: [String] -> LTree
build' []     = error ""
build' (x:xs) = let fold' f a []     = a
                    fold' f a (x:xs) = fold' f (f a x) xs
                in fold' (insert') (build x) xs



exist :: LTree -> String -> Bool
exist d str = let any' [] = False
                  any' (x:xs) | x == str  = True
                              | otherwise = any' xs
              in any' (foldLTree d)

insert' :: LTree -> String -> LTree
insert' d [] = d
insert' d@(Node char b sub) str@(s:st) 
            | exist d str = d
            | char /= s = error "Error: unspecified behaviour" -- в отсутствии перехвата исключений - падаем на месте.
            | otherwise = update d str
   where update :: LTree -> String -> LTree
         update (Node char b sub) (s:st) =
                let updList' [] xs = [build xs]
                    updList' (x@(Node char _ _):xs) str@(s:_) 
                        | char == s = update x str : xs
                        | otherwise = x : updList' xs str
                in case st of [] -> (Node char True sub)
                              _  -> (Node char b (updList' sub st))

   
completions :: LTree -> String -> [String]
completions d str = let fl f [] = []
                        fl f (x:xs) | f x = x : fl f xs
                                    | otherwise = fl f xs
                    in fl (isPrefix str) (foldLTree d)
    where isPrefix [] _ = True
          isPrefix (x:xs) (y:ys) | x == y = isPrefix xs ys
                                 | otherwise = False
Код:
*Main> let ltree = build' ["fa", "false", "far", "fare", "fact", "friend", "frize"]

*Main> exist ltree "far"
True

*Main> insert' ltree "frr"
Node 'f' False [Node 'a' True [Node 'l' False [Node 's' False [Node 'e' True []]],Node 'r' True [Node 'e' True []],Node 'c' False [Node 't' True []]],Node 'r' False [Node 'i' False [Node 'e' False [Node 'n' False [Node 'd' True []]],Node 'z' False [Node 'e' True []]],Node 'r' True []]]

*Main> completions ltree "fr"
["friend","frize"]
Ответить с цитированием
  (#10 (permalink)) Старый
kaffetka1841 kaffetka1841 вне форума
Member
 
Сообщений: 22
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.12.2009
По умолчанию 17.12.2009, 22:53

первый код напоминает питон, это так?
Ответить с цитированием
  (#11 (permalink)) Старый
kaffetka1841 kaffetka1841 вне форума
Member
 
Сообщений: 22
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.12.2009
По умолчанию 18.12.2009, 00:32

Можешь мне адаптировать этот код:


Код:
data LTree = Node | Char | Bool |[LTree] deriving Show




exist :: LTree -> String -> Bool
exist  str =  [] = False
                   (x:xs) | x == str  = True
                              | otherwise =  xs
             

insert :: LTree -> String -> LTree
insert  [] = []
insert (Node char) str (s:st) 
            | exist  str = 
            | otherwise = update dstr
 
completions :: LTree -> String -> [String]
completions  str =  [] = []
                         (x:xs) | x = x : xs
                                    | otherwise =  xs
     

ltree = build ["fa", "false", "far", "fare", "fact", "friend", "frize"]
Ответить с цитированием
  (#12 (permalink)) Старый
calabi-yau calabi-yau вне форума
Member
 
Сообщений: 338
Сказал(а) спасибо: 0
Поблагодарили 10 раз(а) в 10 сообщениях
Регистрация: 28.09.2009
По умолчанию 18.12.2009, 09:57

Пост #9, не?
Ответить с цитированием
Ads
  (#13 (permalink)) Старый
kaffetka1841 kaffetka1841 вне форума
Member
 
Сообщений: 22
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.12.2009
По умолчанию 19.12.2009, 00:58

что?
Ответить с цитированием
  (#14 (permalink)) Старый
Die_hard Die_hard вне форума
Member
 
Сообщений: 14
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 29.10.2010
По умолчанию 11.11.2010, 21:41

calabi-yau, А можно как-нибудь исправить код в сообщении №9, чтобы я смог нормально его запустить в WinHugs?! а то, как только пытаюсь загрузить файл с этим кодом, получаю ошибку такого содержания:
ERROR file:.\t1.hs:6 - Syntax error in declaration (unexpected `}', possibly due to bad layout)
быть может всё дело в звёздочках?! что они вообще означают?! отступ?!
Ответить с цитированием
  (#15 (permalink)) Старый
calabi-yau calabi-yau вне форума
Member
 
Сообщений: 338
Сказал(а) спасибо: 0
Поблагодарили 10 раз(а) в 10 сообщениях
Регистрация: 28.09.2009
По умолчанию 11.11.2010, 22:20

Цитата:
Сообщение от Die_hard Посмотреть сообщение
быть может всё дело в звёздочках?! что они вообще означают?! отступ?!
причуды форумного движка и да, отступ. вот это решение немного лучше.


Don't fear the Monad
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Требуется программист для интересной работы, без отрыва от основной работы. D_i_m_a_S Задания за деньги 2 13.11.2011 20:34
Поиск на ГПС, задача НИМ. Требуется неоптимальное решение Ground Prolog 7 11.10.2011 20:07
Решение примера требуется помощь Тимур03 Вопросы начинающих программистов 3 13.07.2011 09:57
Требуется написание лабораторной работы Fomb Вопросы начинающих программистов 2 22.06.2011 12:53
Требуется решить задачи по лабораторной работе di@blo Delphi 1 10.05.2011 13:31
Требуется помощь в решение задачи на Python Женгя Python 2 21.01.2011 20:42
Написание лабораторной работы Gock Visual Basic 6 13.01.2010 03:31
Требуется решение задач со списками klava Lisp 2 21.12.2009 21:14
Нужна помощь в решинии лабораторной работы Anonymous Prolog 7 05.12.2004 00:04
MSSQL 2000 и DBExpress решение дипломной работы Andrew07 Delphi 1 25.05.2004 23:04
Требуется решение задачи Anonymous Prolog 2 23.04.2004 10:04
Решение научной работы создание CHM-файлов Anonymous Visual C++ 2 10.12.2003 16:32



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов