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.