A primeira pesquisa de profundidade funcional é adorável em gráficos acíclicos direcionados.

Nos gráficos com ciclos, no entanto, como evitamos recursões infinitas? Em uma linguagem processual, eu marcaria os nós ao atingi-los, mas digamos que não posso fazer isso.

Uma lista de nós visitados é possível, mas será lenta porque o uso de um resultará em uma pesquisa linear dessa lista antes de ocorrer novamente. Uma estrutura de dados melhor do que uma lista aqui obviamente ajudaria, mas esse não é o objetivo do jogo, porque eu estou codificando em ML - listas são rei, e qualquer outra coisa que eu tenha que escrever eu mesma.

Existe uma maneira inteligente de contornar esse problema? Ou terei que me contentar com uma lista visitada ou, se Deus não permitir, estado mutável?