lomeo: (лямбда)
[personal profile] lomeo
Клёвая реализация сабжа от [livejournal.com profile] antilamer:
data Tree a = Nil | Branch (Tree a) a (Tree a)

bfs t = [x | Branch _ x _ <- b]
  where
    b = t:[x | Branch l _ r <- b, x <- [l,r]]

Ленивость, все дела.

отсюда.

Date: 2011-12-21 04:36 pm (UTC)
From: [identity profile] lionet.livejournal.com
Ошибка, там t а не b в конце.

Date: 2011-12-21 05:11 pm (UTC)
From: [identity profile] lomeo.livejournal.com
Не понял твоего замечания. Если самую последнюю b заменить на t, то где рекурсия, т.е. собственно обход дерева?

Но там ошибка есть, да. Этот bfs не завершается :-( А если поправить, то уже не будет так красиво.

Date: 2011-12-21 07:22 pm (UTC)
From: [identity profile] gliv.livejournal.com
О, замечательно! :)
Клевая реализация ... Там ошибка есть ... Если поправить, то уже не будет так красиво
Напомнило "могу печатать 1200 символов в минуту, но такая фигня получается" ;)

Date: 2011-12-21 08:04 pm (UTC)
From: [identity profile] lomeo.livejournal.com
Я ошибку поздно заметил :-)

Date: 2011-12-21 08:59 pm (UTC)
From: [identity profile] thesz.livejournal.com
Напомню про Omega monad transformer: http://hackage.haskell.org/package/control-monad-omega

Специально для таких случаев.

Date: 2011-12-21 10:16 pm (UTC)
From: [identity profile] lomeo.livejournal.com
Я думал об этом с самого начала, но не вижу как это сделать - у дерева больше чем два уровня вложенности.

Date: 2011-12-21 10:36 pm (UTC)
From: [identity profile] thesz.livejournal.com
Эта штука будет работать даже на бесконечном списке бесконечных списков. ;)

Date: 2011-12-21 10:38 pm (UTC)
From: [identity profile] lomeo.livejournal.com
Это-то понятно, для этого омега и нужна. Но бесконечный список бесконечных списков - это всего два уровня вложенности, а у дерева их может быть больше. Я не вижу как использовать тут омегу.

В общем, если я чего не вижу - ткни носом.

Date: 2011-12-21 10:59 pm (UTC)
From: [identity profile] thesz.livejournal.com
elemTree :: Eq a => a -> Tree a -> Bool
elemTree e tree = or $ map (==e) $ runOmega $ flatten tree

flatten Nil = fail ""
flatten (Branch l a r) = return a `Monad.mplus` flatten l `Monad.mplus` flatten r
Действительно, совсем переставлять порядок в flatten (BRanch ...) не получается. flatten l `mplus` return a `mplus` flatten r не работает.

Date: 2011-12-21 11:19 pm (UTC)
From: [identity profile] lomeo.livejournal.com
Здорово, спасибо!

Date: 2011-12-21 11:20 pm (UTC)
From: [identity profile] lomeo.livejournal.com
Кстати, раз уж mplus, то вместо fail "" лучше mzero использовать.

Date: 2011-12-21 11:28 pm (UTC)
From: [identity profile] thesz.livejournal.com
Да я уж пива выпил. ;)

Haskell is the language of choice for drunken programmers! ;)

Date: 2011-12-21 05:13 pm (UTC)
From: [identity profile] lomeo.livejournal.com
Например
bfs t = [x | Branch _ x _ <- b [t]]
  where
    b [] = []
    b ts = ts ++ b [x | Branch l _ r <- ts, x <- [l,r]]

Profile

lomeo: (Default)
Dmitry Antonyuk

December 2015

S M T W T F S
  12345
6789101112
131415 16171819
20212223242526
2728293031  

Style Credit

Expand Cut Tags

No cut tags
Page generated Jul. 22nd, 2017 04:44 pm
Powered by Dreamwidth Studios