Дерево на haskell

 
0
 
Functional languages
ava
Татка | 12.12.2009, 09:47
я написала программу на haskell, но не могу до конца реализовать
подскажите пожалуйста
data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving (Read,Show)

readsTree :: (Read a) => ReadS (Tree a)
readsTree s = [(Branch l r, x) | ("<", t) <- lex s,
    (l, u) <- readsTree t,
    ("|", v) <- lex u,
    (r, w) <- readsTree v,
    (">", x) <- lex w ]
    ++
    [(Leaf x, t) | (x, t) <- reads s ]


или еще пробовала

data Tree a = Fork (Tree a) (Tree a) | Leaf a | Stump

join :: (Tree a) -> (Tree a) -> (Tree a)
join Stump t = t
join s Stump = s
join s t = Fork s t

readsTree xs = readsTree' Stump xs
readsTree' t [] = [(t, [])]
readsTree' t ('(':xs) = concat [readsTree' (join t u) ys | (u,ys) <- readsTree' Stump xs]
readsTree' t (')':xs) = [(t, xs)]
readsTree' t (x:xs) = concat [readsTree' (join t (Leaf y)) xs | (y, ys) <- reads [x]]

instance Read a => Read (Tree a) where
    readsPrec _ s = readsTree s


но не могу задать на ней дерево
Вот отдельно реализация глубины

data Tree a = Tip | Node a (Tree a) (Tree a)

height Tip = 0
height (Node _ xl xr) = 1 + max (height xl) (height xr)

main = do print(height(Node 1 (Tip)(Tip)))


при написании пользовалась
http://community.haskell.org/~ndm/parsing/
подскажите пожалуйста


Проблема в том, что дерево надо задавать с консоли или считывать из файла.  Две верхние  программы запускаются, но, когда я задаю функцию readsTree
выдает ошибку. Например, для второй программы: readsTree' (Stump) []. Может я не понимаю чего-то, подскажите, пожалуйста, как их запустить.


M
Void
Поправил форматирование. Используйте, пожалуйста, теги code, особенно для языков, где важны отступы.
Comments (2)
ava
Void | 12.12.2009, 12:04 #
Обе функции рабочие, вероятно, вы просто не указали явно тип (компилятор не может вывести его для read) или не разобрались с собственными правилами выделения лексем.
Первая функция требует пробелов между всеми элементами:
*Main> readsTree "< 1 | 2 >" :: [(Tree Int, String)]
[(Branch (Leaf 1) (Leaf 2),"")]
*Main> readsTree "< < 1 | < 2 | 3 > > | < 4 | 5 > >" :: [(Tree Int, String)]
[(Branch (Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3))) (Branch (Leaf 4) (Leaf 5)),"")]

Второй вариант может разбирать листья только из одного символа:
*Main> readsTree "(12)" :: [(Tree Int, String)]
[(Fork (Leaf 1) (Leaf 2),"")]
*Main> readsTree "((1(23))(45))" :: [(Tree Int, String)]
[(Fork (Fork (Leaf 1) (Fork (Leaf 2) (Leaf 3))) (Fork (Leaf 4) (Leaf 5)),"")]


Если задача просто считать дерево из файла, а не освоить (монадические) парсеры, то deriving Read уже делает всё что нужно:
*Main> read "Branch (Leaf 5) (Branch (Leaf 5) (Leaf 6))" :: Tree Int
Branch (Leaf 5) (Branch (Leaf 5) (Leaf 6))
ava
Татка | 12.12.2009, 15:22 #
Все работает! Спасибо большое за помощь smile 
Please register or login to write.
Firm of day
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Contributors
advanced
Submit