Recursive Generators

Example

Let’s take a look at an example.

Let’s say we have a robot and want to give it directions. We might want to test things such as whether it can go through a room without hitting obstacles, whether it can cover all areas, and so on. But before we can test our bot, we’ll need to be able to create and plan an itinerary for it. Let’s say our robot works on a grid with coordinates and can go left, right, up, or down. A simple generator might look like this:

path() -> list(oneof([left, right, up, down])).

This would be fine if we wanted to eliminate things like “going left then right” or “going up then down” where moves cancel each other out. A ?LET() would probably work well. We’d just scan the list, and every time two opposite directions are taken, drop them from the list.

But what if we wanted to generate a path such that the robot never crosses a part of its path it has already covered? Doing so with a ?SUCHTHAT might not be super-efficient, and ?LET() would certainly be difficult to navigate. To solve this problem, we’d use ...