Про деревья

[deni_ok]

Имеется тип

data Tree a = Nil | Branch (Tree a) a (Tree a)
Написать функцию

elemTree :: Eq a => a -> Tree a -> Bool
проверяющую наличие значения в дереве.

Первая приходящая в голову реализация не проходит следующий тест:

> let testTree n = Branch (testTree n) n (testTree (n+1))
> 3 `elemTree` (testTree 1)
True
Код теста специально сливается с

Comments

[antilamer]

о!!

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

:)

[lomeo]

Супер! Особенно x <- [l,r] неожиданно. Хороший способ для ручного concat.

[lomeo]

BTW, не вернёт никогда False :-(

[antilamer]

Почему?

[lomeo]

Потому что bfs не завершается: нет ограничивающего условия, b = .. <-b превращается в конце концов в b = b.

Проверь на elemTree 1 Nil, например.