## digitalmars.D - For Chuck Allison: possible homework in D

• Philippe Sigaud (49/49) Jun 06 2014 I was watching Chuck Allison talk yesterday, and wondered what
• MattCoder (5/8) Jun 07 2014 Yes this is interesting idead. -But If I remember well, he said
• SomeDude (4/9) Jun 07 2014 Also write D programs for the Computer Language Shootout, in an
• FreeSlave (14/14) Jun 08 2014 The good exercise would be implementing some traversal (walk)
• Chris (18/68) Jun 09 2014 I did that for a project at work. A generic tree with specific
"Philippe Sigaud" <philippe.sigaud gmail.com> writes:
```I was watching Chuck Allison talk yesterday, and wondered what
could be a possible homework in D. Maybe other people here have
some ideas, maybe Bearophile will point to RosettaCode, I don't
know. But here is a possible idea:

Trees.

Since you taught them about ranges/lists and functional
mapping/filtering/folding on them, maybe an opening towards trees
could be interesting. Trees are present everywhere as a
structure: documents, initialization files, even source code.
Defining a generic, polymorphic, tree node is easy in D:

struct Tree(T)
{
T value;
Tree[] children;
}

There. Not much more complicated than T[], right?
Have them play with factory functions, assembling trees together
and so on. Writing a way to print a tree on the console is also
fun.

Then, show them how to map a function on a tree, to get a
different tree with the same shape:

Tree!int tree1 = ...

Tree!string tree2 = treeMap!((int i)=> to!string(i))(tree1);

Then, ask them why there is no (easy) way to filter a tree :)

And, reduce. Reducing a tree is very powerful. Getting its
height, the number of  nodes. Show to them that the printing
function they wrote to get trees on screen is in fact a reduce.

And now for the fun part, what could be a real assignment (is
that the US word?): encode a document as a tree.

Maybe like this:

enum MarkUp { text, title, section, emphasis, ... }

struct DocNode
{
MarkUp nodeType;
string content;
DocNode[] children;
}

So a doc is a root node, probably a section, containing other
subsection, and so on.
And the assignment is: write different functions to output the
tree content as HTML, XML, DocBook, LaTex, Wikipedia mark-up or
markdown. Of course, that should use map/reduce :) Outputting
something that can be seen on their browser should interest them.

Of course, if at this stage they already know parsing (from the
compiler course), they can also create the tree by parsing an
input text in a simple markup language, and then converting into
another format, all of that using D. But maybe that's too
complicated?

Thoughts? Do other people here have homework ideas?
```
Jun 06 2014
"MattCoder" <idonthaveany mail.com> writes:
```On Saturday, 7 June 2014 at 06:48:39 UTC, Philippe Sigaud wrote:
... But here is a possible idea:
Trees...
...Thoughts? Do other people here have homework ideas?

Yes this is interesting idead. -But If I remember well, he said
to send him an e-mail with ideas. So I think you should point him

Matheus.
```
Jun 07 2014
Philippe Sigaud via Digitalmars-d <digitalmars-d puremagic.com> writes:
```On Sat, Jun 7, 2014 at 5:00 PM, MattCoder via Digitalmars-d
<digitalmars-d puremagic.com> wrote:

Yes this is interesting idead. -But If I remember well, he said to send him
an e-mail with ideas. So I think you should point him (through e-mail) about
this topic!

I will. I just wanted to see what other ideas people here could find.
```
Jun 07 2014
"MattCoder" <idonthaveany mail.com> writes:
```On Saturday, 7 June 2014 at 17:45:46 UTC, Philippe Sigaud via
Digitalmars-d wrote:
I will. I just wanted to see what other ideas people here could
find.

And I'm really glad that you did here, because as a D learner it
will be nice to see those ideas.

Matheus.
```
Jun 07 2014
"SomeDude" <lolilol mailmetrash.com> writes:
```On Saturday, 7 June 2014 at 06:48:39 UTC, Philippe Sigaud wrote:
I was watching Chuck Allison talk yesterday, and wondered what
could be a possible homework in D. Maybe other people here have
some ideas, maybe Bearophile will point to RosettaCode, I don't
know.

Thoughts? Do other people here have homework ideas?

Also write D programs for the Computer Language Shootout, in an
idiomatic way or as fast as possible (without resorting to pure C
or assembly).
```
Jun 07 2014
"FreeSlave" <freeslave93 gmail.com> writes:
```The good exercise would be implementing some traversal (walk)
algorithms for the generic tree structures. There are many tree
traversal algorithms (some kinds of depth search and
breadth-first search) and they may have range interface, so you
can use them just like other ranges and don't need to write
treeMap or treeFilter, because generic algorithms are already
suitable with ranges.

It may look like this:

foreach(node; tree.byBreadth) // byDepth. Maybe it needs some
more convenient names.
{
//use node
}

It's good way to show how D range concept is generic.
```
Jun 08 2014
Philippe Sigaud via Digitalmars-d <digitalmars-d puremagic.com> writes:
```Yes indeed, you can provide a range interface on a tree. That's a good idea!

But I suppose Chuck wants to teach his students generic notions such as
mapping or folding. Ranges are more a D-specific thing.

Also, what's interesting is that when  mapping a tree, you can keep its
'shape', whereas providing a range flattens the tree into a linear
construct.
```
Jun 08 2014
"Chris" <wendlec tcd.ie> writes:
```On Saturday, 7 June 2014 at 06:48:39 UTC, Philippe Sigaud wrote:
I was watching Chuck Allison talk yesterday, and wondered what
could be a possible homework in D. Maybe other people here have
some ideas, maybe Bearophile will point to RosettaCode, I don't
know. But here is a possible idea:

Trees.

Since you taught them about ranges/lists and functional
mapping/filtering/folding on them, maybe an opening towards
trees could be interesting. Trees are present everywhere as a
structure: documents, initialization files, even source code.
Defining a generic, polymorphic, tree node is easy in D:

struct Tree(T)
{
T value;
Tree[] children;
}

There. Not much more complicated than T[], right?
Have them play with factory functions, assembling trees
together and so on. Writing a way to print a tree on the
console is also fun.

Then, show them how to map a function on a tree, to get a
different tree with the same shape:

Tree!int tree1 = ...

Tree!string tree2 = treeMap!((int i)=> to!string(i))(tree1);

Then, ask them why there is no (easy) way to filter a tree :)

And, reduce. Reducing a tree is very powerful. Getting its
height, the number of  nodes. Show to them that the printing
function they wrote to get trees on screen is in fact a reduce.

And now for the fun part, what could be a real assignment (is
that the US word?): encode a document as a tree.

Maybe like this:

enum MarkUp { text, title, section, emphasis, ... }

struct DocNode
{
MarkUp nodeType;
string content;
DocNode[] children;
}

So a doc is a root node, probably a section, containing other
subsection, and so on.
And the assignment is: write different functions to output the
tree content as HTML, XML, DocBook, LaTex, Wikipedia mark-up or
markdown. Of course, that should use map/reduce :) Outputting
something that can be seen on their browser should interest
them.

Of course, if at this stage they already know parsing (from the
compiler course), they can also create the tree by parsing an
input text in a simple markup language, and then converting
into another format, all of that using D. But maybe that's too
complicated?

Thoughts? Do other people here have homework ideas?

I did that for a project at work. A generic tree with specific
DOM implementation. It's a simple concept, yet interesting,
especially when you get a chance to eliminate JS's shortcomings.

I split it up though. I have a generic Tree(T) that takes child
nodes of various types like this:

struct / class Element(T) {
T name;
T[T] attributes;
// ...
string toString() {
return ...;
}
}

So each element manages / can look at its own data, and the
Tree(T) is just an interface that manages these elements and
exposes methods like "getElementsByTagName" etc. I don't know, if
this the best approach but it works fine for me atm.
```
Jun 09 2014
Philippe Sigaud via Digitalmars-d <digitalmars-d puremagic.com> writes:
``` struct / class Element(T) {
T name;
T[T] attributes;
// ...
string toString() {
return ...;
}
}

Why did you chose the same type for keys and values? And shouldn't
'name' always be a string?
```
Jun 09 2014
"Chris" <wendlec tcd.ie> writes:
```On Monday, 9 June 2014 at 10:01:25 UTC, Philippe Sigaud via
Digitalmars-d wrote:
struct / class Element(T) {
T name;
T[T] attributes;
// ...
string toString() {
return ...;
}
}

Why did you chose the same type for keys and values? And
shouldn't
'name' always be a string?

For a HTML Element it should always be a string (e.g. tagname =
"p"). However, it could also be of type wchar[], dchar[], char[].
For HTML Elements I usually have T[T] (string[string]), but
you're right, in other contexts it could be size_t[string],
string[int] etc. I only use it for a web server app. But to make
it more flexible is not too complicated. If I used it in a truly
generic context (DOM, latex and whatnot), I would design the type
system more carefully. But that would have been a waste of time,
since it's primary application is to return a html string. There
were more urgent issues.
```
Jun 09 2014
Philippe Sigaud via Digitalmars-d <digitalmars-d puremagic.com> writes:
```I see, thanks.
```
Jun 09 2014