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

[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

[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! ;)