Как предотвратить циклы при использовании чисто функционального поиска по глубине

Question

У меня есть график, который реализован как список ребер, соединяющих произвольные узлы, с типами данных, определенными ниже.

type edge = int * int;; 
type graph = edge list;; 

Как выполнить чисто функциональный поиск по глубине, избегая застревания в цикле? Я не совсем уверен, как отслеживать все посещаемые узлы, оставаясь чисто функциональными. Ответ, вероятно, что-то тривиальное, что я почему-то не понимаю концептуально.

Answer 1

Функция поиска имеет параметр, который отслеживает посещаемые узлы. В FP одна из идей заключается в том, что вы можете продолжать звонить глубже и глубже (с хвостовыми вызовами). Таким образом, вы можете передать параметр по всем вызовам, добавляя новые узлы по мере продвижения.

Другим параметром могут быть узлы, которые вы планируете посетить позже. Для DFS это будет работать как стек.