У меня есть вопрос о написании рекурсивных алгоритмов в функциональном стиле. Я буду использовать Scala для моего примера здесь, но этот вопрос относится к любому функциональному языку.

Я делаю перечисление в глубинуn-дерево, где каждый узел имеет метку и переменное число дочерних элементов. Вот простая реализация, которая печатает метки конечных узлов.

case class Node[T](label:T, ns:Node[T]*)
def dfs[T](r:Node[T]):Seq[T] = {
    if (r.ns.isEmpty) Seq(r.label) else for (n<-r.ns;c<-dfs(n)) yield c
}
val r = Node('a, Node('b, Node('d), Node('e, Node('f))), Node('c))
dfs(r) // returns Seq[Symbol] = ArrayBuffer('d, 'f, 'c)

Теперь скажите, что иногда я хочу отказаться от разбора больших деревьев, создав исключение. Это возможно на функциональном языке? В частности это возможно без использования изменяемого состояния? Похоже, это зависит от того, что вы подразумеваете под «негабаритным». Вот чисто функциональная версия алгоритма, который выдает исключение, когда пытается обработать дерево глубиной 3 или более.

def dfs[T](r:Node[T], d:Int = 0):Seq[T] = {
    require(d < 3)
    if (r.ns.isEmpty) Seq(r.label) else for (n<-r.ns;c<-dfs(n, d+1)) yield c
}

Но что, если дерево слишком большое, потому что оно слишком широкое, а не слишком глубокое? В частности, что, если я хочу бросить исключениеn-времяdfs() функция вызывается рекурсивно, независимо от того, насколько глубока рекурсия? Единственный способ понять, как это сделать, - это иметь изменяемый счетчик, который увеличивается с каждым вызовом. Я не вижу, как это сделать без изменяемой переменной.

Я новичок в функциональном программировании и работаю в предположении, что все, что вы можете сделать с изменяемым состоянием, можно обойтись, но я не вижу здесь ответа. Единственное, что я могу думать, это написать версиюdfs() который возвращает представление всех узлов дерева в порядке глубины.

dfs[T](r:Node[T]):TraversableView[T, Traversable[_]] = ...

Тогда я мог бы наложить свой предел, сказавdfs(r).take(n), но я не вижу, как написать эту функцию. В Python я бы просто создал генераторyieldВ то время как я посещал их, я не вижу, как добиться того же эффекта в Scala. (Эквивалент Scala в стиле Pythonyield оператор, похоже, является функцией посетителя, переданной в качестве параметра, но я не могу понять, как написать одну из них, которая будет генерировать представление последовательности.)

РЕДАКТИРОВАТЬ Приближаясь к ответу.

Вот функция, которая возвращаетStream узлов в глубину первого порядка.

def dfs[T](r: Node[T]): Stream[Node[T]] = {
    (r #:: Stream.empty /: r.ns)(_ ++ dfs(_))
}

Это почти все. Единственная проблема в том, чтоStream запоминает все результаты, что является пустой тратой памяти. Я хочу просматриваемый вид. Следующая идея, но не компилируется.

def dfs[T](r: Node[T]): TraversableView[Node[T], Traversable[Node[T]]] = {
    (Traversable(r).view /: r.ns)(_ ++ dfs(_))
}

Это дает "найденоTraversableView[Node[T], Traversable[Node[T]]], требуетсяTraversableView[Node[T], Traversable[_]] ошибка для++ оператор. Если я изменю тип возврата наTraversableView[Node[T], Traversable[_]]Я получаю ту же проблему с переключенными пунктами "найдено" и "обязательно". Так что есть какое-то заклинание магии дисперсии типов, о котором я еще не говорил, но это близко.