Databases
StackOverflow2013
Postsdbo
POFunctional style early exit from depth-first recursion
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POFunctional style early exit from depth-first recursion
    primarykey
    data
    text
    <p>I have a question about writing recursive algorithms in a functional style. I will use Scala for my example here, but the question applies to any functional language.</p> <p>I am doing a depth-first enumeration of an <em>n</em>-ary tree where each node has a label and a variable number of children. Here is a simple implementation that prints the labels of the leaf nodes.</p> <pre><code>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&lt;-r.ns;c&lt;-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) </code></pre> <p>Now say that sometimes I want to be able to give up on parsing oversize trees by throwing an exception. Is this possible in a functional language? Specifically is this possible without using mutable state? That seems to depend on what you mean by "oversize". Here is a purely functional version of the algorithm that throws an exception when it tries to handle a tree with a depth of 3 or greater.</p> <pre><code>def dfs[T](r:Node[T], d:Int = 0):Seq[T] = { require(d &lt; 3) if (r.ns.isEmpty) Seq(r.label) else for (n&lt;-r.ns;c&lt;-dfs(n, d+1)) yield c } </code></pre> <p>But what if a tree is oversized because it is too broad rather than too deep? Specifically what if I want to throw an exception the <em>n</em>-th time the <code>dfs()</code> function is called recursively regardless of how deep the recursion goes? The only way I can see how to do this is to have a mutable counter that is incremented with each call. I can't see how to do it without a mutable variable.</p> <p>I'm new to functional programming and have been working under the assumption that anything you can do with mutable state can be done without, but I don't see the answer here. The only thing I can think to do is write a version of <code>dfs()</code> that returns a view over all the nodes in the tree in depth-first order.</p> <pre><code>dfs[T](r:Node[T]):TraversableView[T, Traversable[_]] = ... </code></pre> <p>Then I could impose my limit by saying <code>dfs(r).take(n)</code>, but I don't see how to write this function. In Python I'd just create a generator by <code>yield</code>ing nodes as I visited them, but I don't see how to achieve the same effect in Scala. (Scala's equivalent to a Python-style <code>yield</code> statement appears to be a visitor function passed in as a parameter, but I can't figure out how to write one of these that will generate a sequence view.)</p> <p><strong>EDIT</strong> Getting close to the answer.</p> <p>Here is an function that returns a <code>Stream</code> of nodes in depth-first order.</p> <pre><code>def dfs[T](r: Node[T]): Stream[Node[T]] = { (r #:: Stream.empty /: r.ns)(_ ++ dfs(_)) } </code></pre> <p>That is almost it. The only problem is that <code>Stream</code> memoizes all results, which is a waste of memory. I want a traversable view. The following is the idea, but does not compile.</p> <pre><code>def dfs[T](r: Node[T]): TraversableView[Node[T], Traversable[Node[T]]] = { (Traversable(r).view /: r.ns)(_ ++ dfs(_)) } </code></pre> <p>It gives a "found <code>TraversableView[Node[T], Traversable[Node[T]]]</code>, required <code>TraversableView[Node[T], Traversable[_]]</code> error for the <code>++</code> operator. If I change the return type to <code>TraversableView[Node[T], Traversable[_]]</code>, I get the same problem with the "found" and "required" clauses switched. So there's some magic type variance incantation I haven't lit upon yet, but this is close.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USW.P. McNeill
    1. USW.P. McNeill
    plurals
    1. PL
      singulars
      1. LTLinked
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POFunctional style early exit from depth-first recursion
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POFunctional style early exit from depth-first recursion
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POFunctional style early exit from depth-first recursion
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload