Чисто функциональный поиск в DAG

А в чём проблема? Например так:

(define (find-depth graph-node key found-callback)
  (when (graph-compare-key graph-node key)
    (found-callback graph-node))
  (foreach-adjacent-node (lambda (node)
                           (find-depth node key found-callback))
                         graph-node))

Функции graph-compare-key и foreach-adjacent-node считаются определёнными заранее.

Проблема в том, что у нас не дерево, а DAG -- несколько дуг могут вести в одну вершину. Поэтому чтобы не заходить в одну и ту же вершину по нескольку раз, нужно отмечать уже посещенные.

В императивном подходе это решается довольно в лоб, а в функциональном придётся вести структуру данных с уже посещенными вершинами -- либо список (тогда O(n^2)), либо btree (тогда O(nlogn)). Есть ли какие-то линейные по времени решения?

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

Формально да, раз циклов нет. Но тогда будет O(посещений), а не O(вершин). Можно придумать примеры когда это даст экспоненциальную сложность, например, последовательность "ромбов".

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.6526

читал?

Не читал.

Спасибо, на первый взгляд там как раз то, что надо.

Имхо, здесь ленивость как раз должна помогать.