digitalmars.D.learn - How do you implement a recursive walker of a tree with a lazy range?
- Andrej Mitrovic (50/50) Oct 29 2013 Instead of the usual opApply approach, how would you implement an auto
- Chris Cain (24/24) Oct 29 2013 Here's the code:
- bearophile (85/91) Oct 30 2013 I have used your nice idea to create another partial D solution
- Chris Cain (4/8) Oct 30 2013 Very cool! It's pretty close to being done. I'd have to give some
- Philippe Sigaud (2/3) Oct 30 2013 Does that syntax come with DMD 2.064? The (T) part, I mean.
- Dicebot (3/9) Oct 30 2013 Yes. http://dlang.org/changelog#eponymous_template
- Andrej Mitrovic (3/4) Oct 30 2013 Yes.
- Philippe Sigaud (9/14) Oct 30 2013 As Benjamin, I used an internal stack. But that was years ago, let me s...
- Andrej Mitrovic (4/6) Oct 30 2013 It allocates, I'm looking for a lazy range. I would be surprised that
- Benjamin Thaut (10/16) Oct 30 2013 I had this problem too. I just wrote my own range which uses a stack
- Chris Cain (15/20) Oct 30 2013 It allocates, but it's still a lazy range. It only allocates when
- Chris Cain (21/22) Oct 30 2013 Actually, let me clarify. You'd avoid *those* allocations.
Instead of the usual opApply approach, how would you implement an auto
return walker function *without* defining a special external struct
that holds all the logic? In other words, using existing Phobos
functionality only, composing functions like map and chain. Example
code which isn't correct:
-----
module test;
import std.algorithm;
import std.range;
import std.stdio;
struct Tree
{
string value;
Tree[] children;
/** Walk the entire tree. */
auto walk()
{
return map!(
// note the [] workaround to make it a range
a => chain([a], a.children)
)([this]); // note the [] workaround to make it a range
}
string toString()
{
return value;
}
}
void main()
{
auto tree =
Tree("root",
[
Tree("root.1",
[
Tree("root.1.1"),
Tree("root.1.2")
]),
Tree("root.2",
[
Tree("root.2.1"),
Tree("root.2.2")
]),
]
);
writeln(tree.walk);
}
-----
In case it's not displayed correctly I've pasted it here too:
http://dpaste.dzfl.pl/88409749
Can this be properly implemented using map?
Oct 29 2013
Here's the code:
----
InputRange!Tree walk()
{
return inputRangeObject(chain(
[this],
children.map!(a=>a.walk())().joiner()));
}
----
Result:
---
[root, root.1, root.1.1, root.1.2, root.2, root.2.1, root.2.2]
---
It's a bit confusing to explain how I came up with that, but
essentially you have to cleanly terminate the type inference
(hence why I used an inputRangeObject) and make sure you map the
walk function on all of the children. Mapping on the children
creates a range of ranges (essentially, it turns your range of
children into a range of results of walking, which are ranges),
so you must flatten it into a single range using a join. After
that, I prepended the [this] reference using a regular chain
similar to what you were doing.
I'm not confident that this is the most efficient way, but it
works.
Oct 29 2013
Chris Cain:
InputRange!Tree walk()
{
return inputRangeObject(chain(
[this],
children.map!(a=>a.walk())().joiner()));
}
I have used your nice idea to create another partial D solution
for this task:
http://rosettacode.org/wiki/Tree_traversal#D
import std.stdio, std.algorithm, std.range, std.conv, std.string;
struct Tree(T) {
T value;
Tree* left, right;
}
alias VisitRange(T) = InputRange!(const Tree!T);
VisitRange!T preOrder(T)(in Tree!T* t) {
enum self = mixin("&" ~ __FUNCTION__.split(".").back);
if (t == null)
return typeof(return).init.takeNone.inputRangeObject;
return [*t]
.chain([t.left, t.right]
.filter!(t => t != null)
.map!(a => self(a))
.joiner)
.inputRangeObject;
}
VisitRange!T inOrder(T)(in Tree!T* t) {
enum self = mixin("&" ~ __FUNCTION__.split(".").back);
if (t == null)
return typeof(return).init.takeNone.inputRangeObject;
return [t.left]
.filter!(t => t != null)
.map!(a => self(a))
.joiner
.chain([*t])
.chain([t.right]
.filter!(t => t != null)
.map!(a => self(a))
.joiner)
.inputRangeObject;
}
VisitRange!T postOrder(T)(in Tree!T* t) {
enum self = mixin("&" ~ __FUNCTION__.split(".").back);
if (t == null)
return typeof(return).init.takeNone.inputRangeObject;
return [t.left, t.right]
.filter!(t => t != null)
.map!(a => self(a))
.joiner
.chain([*t])
.inputRangeObject;
}
VisitRange!T levelOrder(T)(in Tree!T* t) {
enum self = mixin("&" ~ __FUNCTION__.split(".").back);
return typeof(return).init.takeNone.inputRangeObject;
// UNFINISHED
}
void main() {
alias N = Tree!int;
auto tree = new N(1,
new N(2,
new N(4,
new N(7)),
new N(5)),
new N(3,
new N(6,
new N(8),
new N(9))));
tree.preOrder.map!(t => t.value).writeln;
tree.inOrder.map!(t => t.value).writeln;
tree.postOrder.map!(t => t.value).writeln;
// Should print: [1, 2, 3, 4, 5, 6, 7, 8, 9]
tree.levelOrder.map!(t => t.value).writeln;
}
As you see levelOrder is not finished.
I don't know if there is a simple way to return that something
for empty input (simpler than
typeof(return).init.takeNone.inputRangeObject). I have used it to
avoid bugs caused by the successive map.writeln.
I don't know if there are nice ways to refactor this code to
shorten it some.
I'd like that function pointer self to be a D built-in feature. I
have used it because when you write such kind of code and you
copy&paste the implementations to create a new visit function
it's very easy to forget to update the name of the function to
call recursively.
A related task that is not yet using this idea:
http://rosettacode.org/wiki/Same_Fringe#Haskell
Bye,
bearophile
Oct 30 2013
"Chris Cain" <clcain uncg.edu> On Wednesday, 30 October 2013 at 12:55:41 UTC, bearophile wrote:I have used your nice idea to create another partial D solution for this task: http://rosettacode.org/wiki/Tree_traversal#D ... snip ...Very cool! It's pretty close to being done. I'd have to give some real thought to how a level-order traversal might be done lazily using D. But that's a good start.
Oct 30 2013
On Wed, Oct 30, 2013 at 1:55 PM, bearophile <bearophileHUGS lycos.com>wrote:alias VisitRange(T) = InputRange!(const Tree!T);Does that syntax come with DMD 2.064? The (T) part, I mean.
Oct 30 2013
On Wednesday, 30 October 2013 at 17:31:10 UTC, Philippe Sigaud wrote:On Wed, Oct 30, 2013 at 1:55 PM, bearophile <bearophileHUGS lycos.com>wrote:Yes. http://dlang.org/changelog#eponymous_templatealias VisitRange(T) = InputRange!(const Tree!T);Does that syntax come with DMD 2.064? The (T) part, I mean.
Oct 30 2013
On 10/30/13, Philippe Sigaud <philippe.sigaud gmail.com> wrote:Does that syntax come with DMD 2.064? The (T) part, I mean.Yes. Glad to see you here btw, do you have your own solution to the problem?
Oct 30 2013
On Wed, Oct 30, 2013 at 7:09 PM, Andrej Mitrovic <andrej.mitrovich gmail.comwrote:On 10/30/13, Philippe Sigaud <philippe.sigaud gmail.com> wrote:Ah, that's cool! I've been waiting for that one for years.Does that syntax come with DMD 2.064? The (T) part, I mean.Yes.Glad to see you here btw, do you have your own solution to the problem?As Benjamin, I used an internal stack. But that was years ago, let me see. https://github.com/PhilippeSigaud/dranges/blob/master/treerange.d#L185 or, for graphs: https://github.com/PhilippeSigaud/dranges/blob/master/graphrange.d#L25 Hmm, what I did there doesn't seem really lazy. I guess with today Phobos and DMD it's possible to have far less allocations. (that code dates from 2009-2011)
Oct 30 2013
On 10/30/13, Chris Cain <clcain uncg.edu> wrote:I'm not confident that this is the most efficient way, but it works.It allocates, I'm looking for a lazy range. I would be surprised that such a common task as iterating a tree is not possible without using classes and workarounds.
Oct 30 2013
Am 30.10.2013 15:58, schrieb Andrej Mitrovic:On 10/30/13, Chris Cain <clcain uncg.edu> wrote:I had this problem too. I just wrote my own range which uses a stack internally to remember the nodes that still need to be visited. When the algorithm hits a non leaf node it pushes the "right" node onto the stack and continues with the "left" node. Whenever the algorithm hits a leaf node it takes a node from the stack and continues with that. That results in a recusion typical depth-first iteration of the nodes. -- Kind Regards Benjamin ThautI'm not confident that this is the most efficient way, but it works.It allocates, I'm looking for a lazy range. I would be surprised that such a common task as iterating a tree is not possible without using classes and workarounds.
Oct 30 2013
On Wednesday, 30 October 2013 at 14:58:21 UTC, Andrej Mitrovic wrote:It allocates, I'm looking for a lazy range. I would be surprised that such a common task as iterating a tree is not possible without using classes and workarounds.It allocates, but it's still a lazy range. It only allocates when popFront is called. I looked around a bit more and found "only" in std.range that can do this without allocating: With the walk function like this: --- InputRange!Tree walk() { return inputRangeObject(chain( only(this), children.map!(a=>a.walk).joiner)); } --- you would avoid allocations.
Oct 30 2013
On Wednesday, 30 October 2013 at 16:50:33 UTC, Chris Cain wrote:you would avoid allocations.Actually, let me clarify. You'd avoid *those* allocations. inputRangeObject allocates a class. Unfortunately, I'm not certain it's possible to do this cleanly without such a thing using inputRangeObject because otherwise you'd have infinite recursion on the types. To limit it to a single allocation, perhaps you could have two functions, walk and innerWalk. The outer walk could allocate some memory on the heap (requiring knowledge of the maximum depth of the tree either by exploring the tree prior to walking it or having the tree hold parent pointers & depths) and the inner walk could take the memory as a parameter. Each recursion would just do mem[1..$] Technically, this should work as well. But it won't be as clean of a solution. It still wouldn't have "no" allocations, but it's the best I can do to limit them. Ultimately, if you want to do this lazily with no allocations and with maximum performance, I think you'll have to make a custom range struct holding the things you need. That said, it can be done with the standard library (and as I've shown, it can look pretty clean and simple) but it probably won't be maximum performance and have no allocations.
Oct 30 2013