www.digitalmars.com         C & C++   DMDScript  

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

reply "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
next sibling parent reply "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 
(through e-mail) about this topic!

Matheus.
Jun 07 2014
parent reply 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
parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent reply "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
parent 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
prev sibling parent reply "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
parent reply 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
parent reply "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
parent Philippe Sigaud via Digitalmars-d <digitalmars-d puremagic.com> writes:
I see, thanks.
Jun 09 2014