Creation of custom iterators.

[Ben Ward]

Hi,

I've been writing a type for recursive tree structures, and several types that traverse that tree in various manners like breadth first or depth first. They have their own methods for getting the current tree node, moving to the next node, whether an end has been reached and so on. The contain fields for the nodes several steps ahead, those past etc. I wondered if I might make it so as these types might easier be used in loops by giving them the iterator protocol methods? I've not seen how to define custom operators, is it as simple as defining start next and done? How is the current value gotten? I guess its returned by next(). 

Thanks,

Ben.  

[Tim Holy]

for x in obj
# blah
end

will iterate if you've defined start, next, and done functions for which the
first argument has typeof(obj). In your case you'd presumably use a node as
obj, and the traversal would be recursively over all children of that node.

If you want a specific tree example, check out ProfileView.jl/src/tree.jl.

Best,
--Tim

[Ben Ward]

I'm not nessecerily trying it iterate over the children of a node. Rather I have defined a series of types that facilitate traversing a tree in various ways for my Phylogenetics.jl package, for example by depth first:

type TraverserCore
  Start::PhyNode
  Behind::Stack
  History::Array{PhyNode, 1}
  Current::PhyNode
end


type DepthFirstTraverser <: TreeTraverser
  Ahead::Stack
  Core::TraverserCore
  function DepthFirstTraverser(tree::Phylogeny)
    x = new(Stack(PhyNode), TraverserCore(tree.Root, Stack(PhyNode), PhyNode[], tree.Root))
    for i in x.Core.Current.Children
      push!(x.Ahead, i)
    end
    return x
  end
end


It has methods like:


function next!(x::DepthFirstTraverser)
  push!(x.Core.Behind, x.Core.Current)
  x.Core.Current = pop!(x.Ahead)
  for i in x.Core.Current.Children
    push!(x.Ahead, i)
  end
end


function getCurrent(x::TreeTraverser)
  return x.Core.Current
end


function hasReachedEnd(x::TreeTraverser)
  length(x.Ahead) > 0 ? false : true
end

Which seem similar to start, next, and done. I'd use them in a loop like so again from Phylogenetics.jl:

while true

    show(getCurrent(traverser))

    if hasReachedEnd(traverser)

      break

    end

    next!(traverser)

end

But I'd like to make it behave more like an iterator - so be able to define the iterator methods for it so I can do something like

for i = DepthFirstTraverser(myTree)
# BLARGH
end

And it will be translated accordingly. I think this is doable by defining the three methods, making use of the types the method already has.

The idea is to have a load of types that allow the user to code iteration over the tree in any possible way, easily, providing there is a TreeTraverser type for it.

Best,

Ben.

[Viral Shah]

This is the documentation:

http://docs.julialang.org/en/latest/stdlib/base/#iteration

You may also want to contribute to:

https://github.com/JuliaLang/Iterators.jl

-viral

[Tim Holy]

You can obtain different types of iteration simply by wrapping "obj" in
different thin-wrappers. For example, you can define

immutable SomeOtherWayOfTraversing{T}
obj::T
end

which is used as

for x in SomeOtherWayOfTraversing(obj)
# blah
end

and then write the specific start, next, done methods like this:

start{T}(iter::SomeOtherWayOfTraversing{T})

You can get totally different behavior this way from what would happen when you
just say "for x in obj...".


You might want to browse through more packages to see more examples. Here's
one:
https://github.com/timholy/Grid.jl/blob/600cbcf645a73525fb6d563d5a148b9d8b2668aa/src/counter.jl
but many other packages (DataFrames, Gtk, HDF5, etc) define iterators.

--Tim

[Ben Ward]

My traverser types are not exactly wrappers quite a simple as they contain FIFO and FILO structures that keep track of things - I struggle to imagine how else to have them. Do the three iterate methods necessarily need to have the second argument "state"? My types know they are done - hasReachedEnd() - because there are no more nodes to visit in their Ahead Queue/Stack. So would a done() that only requires the type be sufficient with no state input variable as in done(tier, state)?

Best,

Ben.

[Tim Holy]

Why can't you keep track of everything in the state variable, and make your
iterator-types trivial?

--Tim

[Ben Ward]

I had not considered this - so state variable is a complex type which would have say the Queue/Stack and current value, and the start, next and done methods update it?

[Tim Holy]

Did you check out the examples I suggested? :)

[Ben Ward]

Yesh I'm reading through Iterators.jl now to try and get my head around it.

[Ben Ward]

I've given this a go but it does not quite work as expected:

immutable DepthFirst

    tree::Phylogeny

end

function start(x::DepthFirst)

  state = Stack(PhyNode)

  push!(state, x.tree.Root)

  return state

end

function next(x::DepthFirst, state)

  current::PhyNode = pop!(state)

  for i in current.Children

    push!(state, i)

  end

  return current, state

end

function done(x::DepthFirst, state)

  return length(state) == 0 ? true : false

end

Then:

for i in DepthFirst(myTree)

i

end

results in:

ERROR: `start` has no method matching start(::DepthFirst)

 in anonymous at no file

I'm not sure why this is - I have a method defined start() for the utterable immutable DepthFirst trivial type. I'm clearly missing something here.

[Leah Hanson]

You need to either `import Base.start` or implement a function named `Base.start` instead of `start`. That change will make your `start` function extend the one from Base with new methods, rather than being a separate function that happens to be named `start`. (This is a super common confusion.)

-- Leah

[Ben Ward]

I see, if I put this into a module in a package will this still be nessecery? I read that when defining a module, base is implicitly imported.

[Tomas Lycken]

Yes; Base is implicitly imported, meaning that you can use any function in Base without having to explicitly import it. However, in order to extend the function with new methods, you do need to import it explicitly (using a statement like import Base.start, Base.next, Base.done or import Base: start, next, done). Otherwise, you’ll shadow the function in Base instead.

// T