Subscribe to The Madman Scribblings
3 Comments
Posted by
AdamSpeight2008 
Concept: Recursive Yield on to a Common Channel.
Let's implement a simple iterator the return all of the values of all the nodes.
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)
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.
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.
Categories: Uncategorized
Share This Entry:
3 Comments On This Entry
Page 1 of 1
cfoley
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:
The concept is fairly language agnostic and I think if you implement it in VB your scoping issues will vanish.
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.
cfoley
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
AdamSpeight2008
22 August 2012 - 12:23 PM
Look at the F# version.
It still doing a
Each level of recursion, has yield the result(s) of the previous on. Eg
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
5 yields for a 5 item sequence.
The compiler could write a much more efficient state-machine for you.
// 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.
Page 1 of 1
|
|
| 