Поиск в ширину

[lomeo]

Клёвая реализация сабжа от 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]]

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

отсюда.

Comments

[lionet.livejournal.com]

Ошибка, там t а не b в конце.

[lomeo.livejournal.com]

Не понял твоего замечания. Если самую последнюю b заменить на t, то где рекурсия, т.е. собственно обход дерева?

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

[gliv.livejournal.com]

О, замечательно! :)
Клевая реализация ... Там ошибка есть ... Если поправить, то уже не будет так красиво
Напомнило "могу печатать 1200 символов в минуту, но такая фигня получается" ;)

[lomeo.livejournal.com]

Я ошибку поздно заметил :-)

[thesz.livejournal.com]

Напомню про Omega monad transformer: http://hackage.haskell.org/package/control-monad-omega

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

[lomeo.livejournal.com]

Я думал об этом с самого начала, но не вижу как это сделать - у дерева больше чем два уровня вложенности.

[thesz.livejournal.com]

Эта штука будет работать даже на бесконечном списке бесконечных списков. ;)

[lomeo.livejournal.com]

Это-то понятно, для этого омега и нужна. Но бесконечный список бесконечных списков - это всего два уровня вложенности, а у дерева их может быть больше. Я не вижу как использовать тут омегу.

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

[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 не работает.

[lomeo.livejournal.com]

Здорово, спасибо!

[lomeo.livejournal.com]

Кстати, раз уж mplus, то вместо fail "" лучше mzero использовать.

[thesz.livejournal.com]

Да я уж пива выпил. ;)

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

[lomeo.livejournal.com]

Например

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