Sortie précoce de style fonctionnel de la récursion en profondeur.

Question

J'ai une question sur l'écriture d'algorithmes récursifs dans un style fonctionnel. J'utiliserai Scala pour mon exemple ici, mais la question s'applique à tout langage fonctionnel.

Je suis en train de faire une énumération en profondeur d'une n -Arbre linéaire où chaque nœud possède une étiquette et un nombre variable d'enfants. Voici une implémentation simple qui imprime les étiquettes des nœuds feuilles.

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)

Supposons maintenant que je veuille parfois pouvoir renoncer à l'analyse d'arbres trop grands en lançant une exception. Est-ce possible dans un langage fonctionnel ? Plus précisément, est-ce possible sans utiliser d'état mutable ? Cela semble dépendre de ce que vous entendez par "surdimensionné". Voici une version purement fonctionnelle de l'algorithme qui lève une exception lorsqu'il tente de traiter un arbre d'une profondeur de 3 ou plus.

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
}

Mais que faire si un arbre est surdimensionné parce qu'il est trop large plutôt que trop profond ? Plus précisément, que se passe-t-il si je veux lancer une exception la n -pour la première fois, le dfs() est appelée récursivement, quelle que soit la profondeur de la récursion ? La seule façon que je vois de faire cela est d'avoir un compteur mutable qui est incrémenté à chaque appel. Je ne vois pas comment le faire sans une variable mutable.

Je suis nouveau dans la programmation fonctionnelle et j'ai travaillé en supposant que tout ce que vous pouvez faire avec un état mutable peut être fait sans, mais je ne vois pas la réponse ici. La seule chose à laquelle je pense est d'écrire une version de dfs() qui renvoie une vue sur tous les noeuds de l'arbre par ordre de profondeur.

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

Je pourrais alors imposer ma limite en disant dfs(r).take(n) mais je ne vois pas comment écrire cette fonction. En Python, je créerais simplement un générateur par yield à mesure que je visite les nœuds, mais je ne vois pas comment obtenir le même effet en Scala. (L'équivalent en Scala d'un style Python yield semble être une fonction visiteur passée en paramètre, mais je n'arrive pas à trouver comment écrire une de ces fonctions qui génère une vue de séquence).

EDITAR On se rapproche de la réponse.

Voici une fonction qui renvoie un Stream de nœuds dans l'ordre de la profondeur.

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

C'est presque tout. Le seul problème est que Stream mémorise tous les résultats, ce qui est un gaspillage de mémoire. Je veux une vue traversable. L'idée est la suivante, mais elle ne compile pas.

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

Il donne un message "trouvé TraversableView[Node[T], Traversable[Node[T]]] nécessaire TraversableView[Node[T], Traversable[_]] erreur pour le ++ opérateur. Si je change le type de retour en TraversableView[Node[T], Traversable[_]] J'ai le même problème avec les clauses "found" et "required" interverties. Il y a donc une incantation magique de type variance que je n'ai pas encore trouvée, mais c'est presque ça.

Answer 1

C'est possible : il suffit d'écrire un peu de code pour itérer parmi les enfants de la manière souhaitée (au lieu de s'appuyer sur for ).

Plus explicitement, vous devrez écrire du code pour itérer dans une liste d'enfants et vérifier si la "profondeur" a franchi votre seuil. Voici quelques Haskell code (je suis vraiment désolé, je ne parle pas couramment le Scala, mais cela peut probablement être facilement translittéré) :

http://ideone.com/O5gvhM

Dans ce code, j'ai essentiellement remplacé la fonction for pour une version récursive explicite. Cela me permet d'arrêter la récursion si le nombre de noeuds visités est déjà trop important (i.e., limit n'est pas positif). Lorsque j'effectue une récursion pour examiner l'enfant suivant, je soustrais le nombre de nœuds que l'enfant suivant n'a pas atteint. dfs de l'enfant précédent visité et la définir comme limite pour l'enfant suivant.

Les langages fonctionnels sont amusants, mais ils représentent un grand pas en avant par rapport à la programmation impérative. Ils vous obligent vraiment à prêter attention au concept de état parce que tout cela est atrocement explicite dans les arguments quand on est fonctionnel.

EDITAR: Je m'explique un peu plus.

J'ai fini par convertir l'algorithme "print just the leaf nodes" (qui était l'algorithme original de l'OP) en "print all nodes". Cela m'a permis d'avoir accès au nombre de noeuds que l'appel secondaire a visité à travers la longueur de la liste résultante. Si vous voulez vous en tenir aux noeuds de la feuille, vous devrez transporter le nombre de noeuds que vous avez déjà visités :

http://ideone.com/cIQrna

EDIT encore Pour clarifier cette réponse, je mets tout le code Haskell sur ideone, et j'ai translittéré mon code Haskell en Scala, donc cela peut rester ici comme la réponse définitive à la question :

case class Node[T](label:T, children:Seq[Node[T]])

case class TraversalResult[T](num_visited:Int, labels:Seq[T])

def dfs[T](node:Node[T], limit:Int):TraversalResult[T] =
    limit match {
        case 0     => TraversalResult(0, Nil)
        case limit => 
            node.children match {
                case Nil => TraversalResult(1, List(node.label))
                case children => {
                    val result = traverse(node.children, limit - 1)
                    TraversalResult(result.num_visited + 1, result.labels)
                }
            }
    }

def traverse[T](children:Seq[Node[T]], limit:Int):TraversalResult[T] =
    limit match {
        case 0     => TraversalResult(0, Nil)
        case limit =>
            children match {
                case Nil => TraversalResult(0, Nil)
                case first :: rest => {
                    val trav_first = dfs(first, limit)
                    val trav_rest = 
                        traverse(rest, limit - trav_first.num_visited)
                    TraversalResult(
                        trav_first.num_visited + trav_rest.num_visited,
                        trav_first.labels ++ trav_rest.labels
                    )
                }
            }
    }

val n = Node(0, List(
    Node(1, List(Node(2, Nil), Node(3, Nil))),
    Node(4, List(Node(5, List(Node(6, Nil))))),
    Node(7, Nil)
))
for (i <- 1 to 8)
    println(dfs(n, i))

Sortie :

TraversalResult(1,List())
TraversalResult(2,List())
TraversalResult(3,List(2))
TraversalResult(4,List(2, 3))
TraversalResult(5,List(2, 3))
TraversalResult(6,List(2, 3))
TraversalResult(7,List(2, 3, 6))
TraversalResult(8,List(2, 3, 6, 7))

P.S. Il s'agit de ma première tentative en Scala, donc ce qui précède contient probablement du code horriblement non-idiomatique. Je suis désolé.

Answer 2

Vous pouvez convertir la largeur en profondeur en transmettant un index ou en prenant la queue :

def suml(xs: List[Int], total: Int = 0) = xs match {
  case Nil => total
  case x :: rest => suml(rest, total+x)
}

def suma(xs: Array[Int], from: Int = 0, total: Int = 0) = {
  if (from >= xs.length) total
  else suma(xs, from+1, total + xs(from))
}

Dans ce dernier cas, vous avez déjà quelque chose pour limiter votre largeur si vous le souhaitez ; dans le premier, il suffit d'ajouter un width ou quelque chose comme ça.

Answer 3

Ce qui suit implémente une recherche en profondeur paresseuse sur les noeuds d'un arbre.

import collection.TraversableView
case class Node[T](label: T, ns: Node[T]*)
def dfs[T](r: Node[T]): TraversableView[Node[T], Traversable[Node[T]]] =
  (Traversable[Node[T]](r).view /: r.ns) {
    (a, b) => (a ++ dfs(b)).asInstanceOf[TraversableView[Node[T], Traversable[Node[T]]]]
  }

Ceci imprime les étiquettes de tous les noeuds dans l'ordre de la profondeur.

val r = Node('a, Node('b, Node('d), Node('e, Node('f))), Node('c))
dfs(r).map(_.label).force
// returns Traversable[Symbol] = List('a, 'b, 'd, 'e, 'f, 'c)

Ceci fait la même chose, en abandonnant après que 3 nœuds aient été visités.

dfs(r).take(3).map(_.label).force
// returns Traversable[Symbol] = List('a, 'b, 'd)

Si vous ne voulez que des nœuds feuilles, vous pouvez utiliser filter et ainsi de suite.

Notez que la clause de pliage de la dfs nécessite une fonction explicite asInstanceOf cast. Voir "Erreur de variance de type en Scala lors d'un foldLeft sur des vues Traversable" pour une discussion sur les problèmes de typage de Scala qui rendent cela nécessaire.