Implement new Concept Exercise: continuations

[ErikSchierboom]

This issue describes how to implement the continuations concept exercise for the F# track.

Getting started

Please please please read the docs before starting. Posting PRs without reading these docs will be a lot more frustrating for you during the review cycle, and exhaust Exercism's maintainers' time. So, before diving into the implementation, please read up on the following documents:

• The features of v3.
• Rationale for v3.
• What are concept exercise and how they are structured?

Please also watch the following video:

• The Anatomy of a Concept Exercise.

Goal

The goal of this exercise is to teach the student some advanced parts of the Concept of Recursion in F#. It will show how to work with non-trivial recursive types that have many cases and where cases' data refers to multiple values of the recursive type themselves. This will make it impossible to write trivially tail-recursive functions. The exercise should show that this is possible using continuations.

It would also be great if we could find a way to also demonstrate mutually recursive functions in the exercise, but if that does not work we can mention it in the documentation

Examples of recursive types that could be used here are binary trees (where nodes have two child trees), a file system or modelling mathematical or boolean expressions. The latter could look like this:

type BooleanExpression =
    | Constant of bool
    | And of BooleanExpression * BooleanExpression
    | Or of BooleanExpression * BooleanExpression
    | Not of BooleanExpression

Note that the above are just suggestions; if you have a better idea, please use it!

Learning objectives

• Know how to work with non-trivial recursive types.
• Know how to use continuations to write tail-recursive functions to handle non-trivial recursive types.
• Mutually recursive functions.

Out of scope

Nothing.

Concepts

The Concepts this exercise unlocks are:

• continuations: know how to work with non-trivial recursive types; know how to use continuations to write tail-recursive functions to handle non-trivial recursive types.
• mutually-recursive-functions: mutually recursive functions.

Prerequisites

This exercise's prerequisites Concepts are:

• higher-order-functions: know how to use higher-order functions.
• recursion: know how to define recursive functions and types.
• discriminated-unions: know how to work with discriminated unions.
• tuples: know how to use tuples as the recursive type will use them.

Any data types used in this exercise (e.g. strings) should also be added as prerequisites.

Resources to refer to

Hints

• Recursion in F#: exploration of recursion in F#, includes continuation passing.
• Advanced recursion techniques in F#: shows some advanced recursion techniques including continuation passing.
• Mutually recursive functions: shows how to define mutually recursive functions.

After

• Recursion in F#: exploration of recursion in F#, includes continuation passing.
• Advanced recursion techniques in F#: shows some advanced recursion techniques including continuation passing.
• Mutually recursive functions: shows how to define mutually recursive functions.

We could also mention the fact that C# does not have tail recursion, which can be very interesting for any C# developers that want to use recursive functions in their C# code.

Representer

This exercise does not require any specific representation logic to be added to the representer.

Analyzer

This exercise does not require any specific logic to be added to the analyzer.

Implementing

To implement this exercise, please follow these instructions.

Help

If you have any questions while implementing the exercise, please post the questions as comments in this issue.