понедельник, 7 февраля 2011 г.

Code-golf: Поиск в ширину и – в глубину с помощью Haskell

Написал короткий код на Haskell для поиска в ширину и поиска в глубину.

Для обоих видов поиска используется рекурсивная структура, которая в читабельном виде выглядит следующим образом:


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

3 комментария:

  1. Точнее, flip (>>=).
    В общем, вместо concatMap c n можно n>>=c

    ОтветитьУдалить
  2. @Константин Действительно, ведь список - это монада! Благодарю.

    ОтветитьУдалить