Mam pytanie dotyczące pisania algorytmów rekurencyjnych w stylu funkcjonalnym. W tym przykładzie użyję Scali, ale pytanie dotyczy dowolnego języka funkcjonalnego.

Robię wyliczenie pierwszej głębokościn-ary drzewo, w którym każdy węzeł ma etykietę i zmienną liczbę dzieci. Oto prosta implementacja, która drukuje etykiety węzłów liści.

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)

Teraz powiedz, że czasami chcę być w stanie zrezygnować z przerabiania nadmiernych drzew, rzucając wyjątek. Czy to możliwe w języku funkcjonalnym? W szczególności, czy jest to możliwe bez użycia zmiennego stanu? To wydaje się zależeć od tego, co rozumiesz przez „oversize”. Oto czysto funkcjonalna wersja algorytmu, który zgłasza wyjątek, gdy próbuje obsłużyć drzewo o głębokości 3 lub większej.

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
}

Ale co, jeśli drzewo jest zbyt duże, ponieważ jest zbyt szerokie, a nie zbyt głębokie? W szczególności, jeśli chcę rzucić wyjątekn-tym razemdfs() funkcja jest wywoływana rekurencyjnie niezależnie od tego, jak głęboko rekursja się odbywa? Jedynym sposobem, aby zobaczyć, jak to zrobić, jest posiadanie zmiennego licznika, który jest zwiększany przy każdym wywołaniu. Nie widzę, jak to zrobić bez zmiennej zmiennej.

Jestem nowicjuszem w programowaniu funkcjonalnym i pracuję pod założeniem, że wszystko, co możesz zrobić ze stanem zmiennym, można zrobić bez, ale nie widzę tutaj odpowiedzi. Jedyne, co mogę myśleć, to napisać wersjędfs() który zwraca widok na wszystkie węzły w drzewie w pierwszej kolejności.

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

Wtedy mógłbym narzucić mój limit, mówiącdfs(r).take(n), ale nie widzę, jak napisać tę funkcję. W Pythonie stworzyłem generator wedługyieldWęzły podczas odwiedzania ich, ale nie widzę, jak osiągnąć ten sam efekt w Scali. (Odpowiednik Scali w stylu Pythonayield instrukcja wydaje się być funkcją gościa przekazaną jako parametr, ale nie mogę dowiedzieć się, jak napisać jedną z tych, które wygenerują widok sekwencji.)

EDYTOWAĆ Zbliżam się do odpowiedzi.

Oto funkcja, która zwraca aStream węzłów w pierwszym rzędzie głębokości.

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

To prawie to. Jedynym problemem jest toStream zapamiętuje wszystkie wyniki, co jest stratą pamięci. Chcę widok przechodni. Poniżej znajduje się idea, ale się nie kompiluje.

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

To daje „znalezioneTraversableView[Node[T], Traversable[Node[T]]], wymaganyTraversableView[Node[T], Traversable[_]] błąd dla++ operator. Jeśli zmienię typ powrotu naTraversableView[Node[T], Traversable[_]], Mam ten sam problem z przełączonymi klauzulami „znalezione” i „wymagane”. Więc jest jakaś magiczna inkantacja wariancji, na której jeszcze nie zapaliłem, ale jest blisko.