Для обоих видов поиска используется рекурсивная структура, которая в читабельном виде выглядит следующим образом:
data Node a = Node {value::a, children::[Node a]}
Сами тексты соответственно выглядят:
bfs :: Node a -> [a]
bfs (Node a b) = bfs' [a] b
where bfs' res [] = res
bfs' res n = bfs' (res ++ (map value n)) $ concatMap children n
dfs :: Node a -> [a]
dfs node = dfs' [node] []
where dfs' [] result = result
dfs' (x:xs) result = dfs' (children x ++ xs) (result ++ [value x])
Ну, и в сжатом виде:
data N a=N{v::a,c::[N a]}
b(N a b)=d[a]b
d r[]=r
d r n=d(r++(map v n))$concatMap c n
d n=f[n][]
f(x:y)=f(c x++y).(++[v x])
f _=id
Где функция
b
– поиск в ширину, а функция d
– в глубину.Поиск в глубину пытался сократить по-разному, в т. ч., как видно, с помощью композиции функций (HaskellWiki – Point-free Style). Хотя, если развернуть композицию, вернув назад аргумент, объем кода будет идентичным:
d n=f[n][]
f(x:y)r=f(c x++y)$r++[v x]
f[]r=r
Если у кого-то есть идеи по дальнейшему возможному сокращению кода, либо вы хотите попробовать реализовать сжатые алгоритмы на вашем любимом языке, прошу предлагать свои варианты на новом сайте для любителей программирования и программных головоломок Code Golf – Stack Exchange:
Have
fun()
! ;-)
Для списков concatMap ≡(>>=)
ОтветитьУдалитьТочнее, flip (>>=).
ОтветитьУдалитьВ общем, вместо concatMap c n можно n>>=c
@Константин Действительно, ведь список - это монада! Благодарю.
ОтветитьУдалить