Функциональная глубина первого поиска хороша в ориентированных ациклических графах.

В графах с циклами, однако, как мы можем избежать бесконечной рекурсии? На процедурном языке я бы отмечал узлы, когда я их ударил, но, скажем, я не могу этого сделать.

Список посещенных узлов возможен, но будет медленным, потому что его использование приведет к линейному поиску этого списка перед повторением. Очевидно, что лучшая структура данных, чем список, может помочь, но это не является целью игры, потому что я кодирую в ML - списки - король, и все остальное мне придется написать самому.

Есть ли умный способ обойти эту проблему? Или мне придется обходиться списком посещений или, не дай бог, изменчивым состоянием?