Subscribe to The Madman Scribblings        RSS Feed
-----

Concept: Recursive Yield on to a Common Channel.

Icon 3 Comments
Concept: Recursive Yield on to a Common Channel.

Public Class Node(Of T)
 Public ReadOnly Value As T
 Public Property Left As Node(Of T)
 Public Property Righ As Node(Of T)




Let's implement a simple iterator the return all of the values of all the nodes.

Public Iterator Function VisitNode(Of T)( N As Node(Of T)) As IEnumerable(Of T)
  Yield N.Value
  If n.Left IsNot Nothing Then
    For Each visitedNode In VisitNode(N.Left)
      Yield visitedNode
    Next
  End If
  If n.Righ IsNot Nothing Then
    For Each visitedNode In VisitNode(N.Righ)
      Yield visitedNode
    Next
  End If
End Function




The Concept

Instead of repeatedly yielding values from a deeper level of recursion.
Why not pass some form of reference to the "Yielder" mechanism the ???
Now the iterator is O(n) rather then O(n2)

Public Iterator Function VisitNodes(Of T)(N As Node(Of T)) As IEnumerable(Of T)
 Dim _Visit = Recursive Iterator(ByRef channel As ?? ,_N  As Node(Of T))
                Yield On channel  _N.Value
                ' The value isnot yielded at the local scope of '
                ' the lambda _Visit '
                ' but on iterator: VisitNodes '
                If N.Left IsNot Nothing _Visit(channel, N.Left)
                If N.Righ IsNot Nothing _Visit(channel, N.Righ)
              End Iterator
 _Visit( AddressOf(VisitNodes.Iterator), N)
End Iterator



Restrictions

The iterator channel reference is locally scoped, akin to the functionality of the *cough* Goto {label name} *cough* and can not be pass out of the iterator method.




Open Challenge

Can any out there find away of achieving this without building a collection as you go and yielding them, or using the ForEach ... Yield method currently being used.

3 Comments On This Entry

Page 1 of 1

cfoley Icon

22 August 2012 - 10:11 AM
To be clear, do you want to do a preorder traversal without using recursion? My first instinct is to use a stack. Something like:

let N = root node
let S = empty stack
while N != null
  Yield N
  S.push N
  if N.hasLeftChild
    N = N.leftChild
  else if N.hasRightChild
    N = N.rightChild
  else if S.isEmpty
    N = null
  else
    N = S.pop


The concept is fairly language agnostic and I think if you implement it in VB your scoping issues will vanish.
0

cfoley Icon

22 August 2012 - 10:24 AM
Oops. That code I posted is clearly nonsense but the edit button won't work. I think this should do it:


let N = root node
let S = empty stack

while N != null
  Yield N

  if n.hasRightChild
    S.push N

  if N.hasLeftChild
    N = N.leftChild
  else if S.isEmpty
    N = null
  else
    N = S.pop.rightChild
0

AdamSpeight2008 Icon

22 August 2012 - 12:23 PM
Look at the F# version.

// Yield the values of a binary tree in a sequence. 
type Tree<'a> =
   | Tree of 'a * Tree<'a> * Tree<'a>
   | Leaf of 'a

// inorder : Tree<'a> -> seq<'a>    
let rec inorder tree =
    seq {
      match tree with
          | Tree(x, left, right) ->
               yield! inorder left
               yield x
               yield! inorder right
          | Leaf x -> yield x
    }   



It still doing a
 For Each item In theIEnumerableReturnFromFunction
  Yield item
 Next


Each level of recursion, has yield the result(s) of the previous on. Eg
1
12
123
1234
12345


15 yields for 5 item sequence.
Inefficient.

I'm say why can't some object reference you can pass as argument parameter to a method. Which allows you to say .. by the way yield your values through this channel or pipe. So the compiler doesn't have to create new state machine for each level of recursion. Akin to the Tail Call Optimisation in the IL that saves creating a new stack frame, which allow deeper level of recursion (infinite).

When it could be
1 2 3 4 5


5 yields for a 5 item sequence.

The compiler could write a much more efficient state-machine for you.
0
Page 1 of 1