Exercise ideas: Game trees, Comma-Separated Trees, Collatz Trees

[sshine]

Game trees are trees that describe the possible choices in a turn-based game. The leaves are final states where either player has won, and each step up the tree describe the turn before where the other player (alternating at each level in the tree) has a number of choices corresponding to one sub-tree each.

An exercise would consist of describing a game between two persons (Alice and Bob?) in a story-like fashion, a (possibly illustrated?) description of game trees, and a task to 1) build the game tree between Alice and Bob for the given game, and 2) given a game tree, pick the best move.

The exercise can be unit-tested for small game trees and property-tested for larger game trees.

As for the specific game, popular choices are Nim and Tic-tac-toe. We might also pick something else.

Motivation: In my opinion, the Haskell track lacks tree-based exercises. (Ping @petertseng)

[sshine]

Another tree-based exercise that resembles the already existent "Tree Building" exercise is Comma-Separated Trees.

It has a blend of whitespace-sensitive parsing and constructing a tree from CSV-like values. It isn't too difficult to write a custom parser for it, and it poses some interesting, non-standard challenges for parser combinator libraries.

It could work as either a refactoring or a hard from-scratch exercise.

[rpottsoh]

Should this be closed because #1424?

[sshine]

@rpottsoh: Not at all. :-) I'm still collecting ideas. I'll submit a PR to one of them when I've completed the track implementation of one of them. (It's one of those things that are a little harder to timebox, I think.)

[sshine]

Inspired by XKCD 710, and to supplement the Collatz Conjecture exercise, here are Collatz Trees:

The exercise's goal is to construct a tree like the one in the XKCD drawing. The tree is binary, since you can only ever arrive at a Collatz number from an odd or an even number. And the tree has a fixed structure, so the only variation is how much of the tree to generate. This makes it an excellent candidate for lazy data structures.

An animation of a Collatz Tree can be found here.

[coriolinus]

Oh, that sounds fun! How's this for test cases: provide a derivation path, expect the item at that position in the tree. Case: [] -> 1 Case: ["even"] -> 2 Case: ["odd"] -> nil Case: ["even", "even"] -> 4 Case: ["even", "even", "even"] -> 8 Case: ["even", "even", "even", "even"] -> 16 Case: ["even", "even", "even", "even", "odd"] -> 5

…

On Thu, Jan 17, 2019 at 11:14 AM Simon Shine ***@***.***> wrote: Inspired by XKCD 710 <https://xkcd.com/710/>, and to supplement the Collatz Conjecture exercise, here are Collatz Trees: [image: collatz_conjecture] <https://user-images.githubusercontent.com/50879/51311112-79815f80-1a48-11e9-839b-01dfa0396bec.png> The exercise's goal is to construct a tree like the one in the XKCD drawing. The tree is binary, since you can only ever arrive at a Collatz number *n* from an odd or an even number. And the tree has a fixed structure, so the only variation is how much of the tree to generate. This makes it an excellent candidate for lazy data structures. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#1388 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AHdeThYXWUET9FoFm8BaINPhIXuIMlJPks5vEE0egaJpZM4YWnF0> .

[Smarticles101]

An animation of a Collatz Tree can be found here.

Oh my gosh it's beautiful lol.

[sshine]

I'm still hunting for a good first tree-based exercise for the Haskell track.

The following is a bit too mathy, but very simple:

Calkin-Wilf trees (2000) enumerate the positive rationals:

[iHiD]

For context, would you mind explaining what language techniques you imagine these sorts of exercises teaching? Maybe with examples from a couple of different types of languages? Thanks :)

[sshine]

TL;DR: I imagine that these exercises will mainly teach tree-based recursion and pattern matching.

---

In Haskell I'd like to cover the standard Data.Tree and potentially one of the Functor, Foldable or Traversable type classes (generalised recursion schemes), depending on the exercise. That is: You don't need to define your own multi-way tree type, and you don't need to define the recursive function yourself. In OCaml / SML I expect to cover only algebraic types and pattern matching, since their libraries don't have generic tree types or generic recursion schemes on them.

The purpose of this issue has so far been collecting tree-based exercise ideas until one strikes me as an ideal first exercise. So far the ones I've found are too mathy (MinMax trees, Collatz trees, Calkin-Wilf trees) and Comma-Separated trees involve parsing, so for Haskell that'd mean covering both trees and parser combinators in one go, which is not ideal at all.

Our existing tree-building exercise has two drawbacks: It's too difficult, and it's a refactoring exercise. And the existing binary-search-tree exercise has one drawback: It implements a common data structure available in the standard library.

[sshine]

Here's an idea for a good introductory multi-way tree exercise: Family trees. A simple but flexible model of a family tree has n children and 0, 1 or 2 parents (unspecified who's who), where a parent has three fields: name, birth year and death year, all optional.

Step 1: Model a family tree. If your language has a preferred way to express multi-way trees, use this. The exercise's module exports the abstract constructors necessary for the next step.

Step 2: Define certain operations on this family tree. This could be

find :: FamilyTree -> (Person -> Bool) -> [Person]

such that one could write find isAlive or find (diedBefore 1900).

Story: To be written, but there's a theme.

---

Thoughts prior to this formulation:

• Simple family trees can be focused at descendants or ancestors; when focusing on descendants, one can use a binary tree and cannot include siblings; when focusing on ancestors, one must use multi-way trees and cannot include multple ancestor lines. Less simple family trees would let you specify multi-way branching both ways, even less simple family trees would let you specify ancestors and descendants on both sides of a parental couple, and even less simple family trees require DAGs to handle some degree of in-breeding.

  I've suggested ancestor-based family trees because tracks that wish for a simple binary tree exercise already have binary-search-tree; this is an attempt to create a simple multi-way tree exercise. And I've kept from any of the less simple family tree models described.

• A simple find function takes as argument a Person predicate; I wouldn't call it filter, since it does not produce a family tree, but rather a list of persons from a family tree. Many useful family tree predicates include a local context, e.g.

    find :: FamilyTree -> (Person -> FamilyTree -> Bool) -> [Person]
  

  with the predicate function taking e.g. the parent FamilyTree of a Person as argument also. This is called a tree paramorphism and I've kept from these as well.