Project: the way out

Sweep the bay, decide with a pipeline of pure functions built by composition, map, filter and fold, then drive out.

A13.8Functional programmingA level35 min

BugBot is parked in a bay, walled in on three sides. It has to look around, work out which way is open, and drive out, stopping a safe distance short of whatever is beyond. You could write that as one loop full of variables. In this project you write it the functional way: the robot's side effects (sensing, turning, driving) stay in a thin layer at the edges, and every decision in between is made by pure functions built from partial application, composition, map, filter and fold.

The brief

• Sweep (side effects): take 8 distance readings, one every 45 degrees, starting facing the way the robot starts and turning right 45 degrees after each reading, so the robot ends facing its start direction. Return them as a tuple of (heading, cm) pairs, where heading is 0, 45, 90 and so on up to 315.
• Decide (pure): work out how much room each direction has, which is the reading minus a safety margin of 15 cm. Print the headings with more than 25 cm of room, and fold the rooms to find the direction with the most.
• Act (side effects): turn right to that heading and drive forward by its room.

Decompose it

the way out
├── edge: sweep()             8 readings -> ((0, cm), (45, cm), ...)
├── core: pure functions
│   ├── offset, compose       small curried pieces
│   ├── room_of               a reading -> its room, built by composition
│   ├── with_room             (heading, cm) -> (heading, room), mapped over the sweep
│   ├── open                  filter: room > 25
│   └── roomier               fold: keep the pair with more room
└── edge: act                 turn right to the best heading, drive its room

Everything in the core can be tested with made-up readings, without a robot. Only sweep and the last two commands touch the world.

Step 1: the sweep

The sweep is the one place readings come in. It returns an immutable tuple, so nothing later can change the data it collected. It is a side-effecting function by nature, so a loop here is fine; the functional style is about keeping such code small and separate.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def sweep():
    readings = ()
    for i in range(8):
        readings = readings + ((i * 45, distance()),)   # a new tuple each time
        turn_right(30, angle=45)
    return readings

print(sweep())

Run this in the simulator

On the task's mat, facing into the bay, the readings are about:

So the answer should be heading 90, with about 46 cm of room, and it is the only direction with more than 25. Work this out before you code, so you know what the program should print.

Step 2: build the pieces

Test each pure function on its own with values you choose:

def offset(amount):
    return lambda x: x + amount

def compose(g, f):
    return lambda x: g(f(x))

def cm_of(reading):
    return reading[1]

room_of = compose(offset(-15), cm_of)    # cm_of first, then subtract the margin
print(room_of((90, 61.0)))               # 46.0
print(room_of((0, 26.0)))                # 11.0

Run this in the simulator

room_of is never written with def; it is the composition of two smaller functions, one of them made by partial application. Its type is (heading, cm) → real.

Step 3: map, filter, fold

With made-up readings, still no robot:

from functools import reduce

def offset(amount):
    return lambda x: x + amount

def compose(g, f):
    return lambda x: g(f(x))

room_of = compose(offset(-15), lambda r: r[1])

test = ((0, 26.0), (90, 61.0), (180, 40.0))
rooms = tuple(map(lambda r: (r[0], room_of(r)), test))
wide = tuple(filter(lambda r: r[1] > 20, rooms))
best = reduce(lambda a, b: a if a[1] >= b[1] else b, rooms)
print(rooms)
print(wide)
print(best)

Run this in the simulator

This gives ((0, 11.0), (90, 46.0), (180, 25.0)), then ((90, 46.0), (180, 25.0)), then (90, 46.0). When the fold compares two equal rooms, >= keeps the earlier one, so a tie always goes to the direction swept first.

Step 4: act

The robot finishes the sweep facing heading 0, so turning right by the best heading faces it that way. Turning right 90 then driving 46 cm takes it out of the bay. Guard against a sweep that finds no room at all: do not drive a negative distance.

Test plan

Task: the way out

Get BugBot out of the bay, following the brief. Every part of the program is defined here:

• MARGIN = 15 (cm) and OPEN_CM = 25 (cm) are constants.
• sweep() takes no arguments and returns a tuple of 8 (heading, cm) pairs, heading 0, 45, ..., 315 and cm the distance() reading taken facing that way, turning right 45 degrees at speed 30 after each reading.
• offset(amount) returns a function of one number x that gives x + amount; compose(g, f) returns a function of one value x that gives g(f(x)).
• room_of is compose applied to offset(-MARGIN) and a function that returns a pair's cm: given a (heading, cm) pair it returns the room in cm.
• Map over the sweep to get (heading, room) pairs. Filter them to those with room greater than OPEN_CM and print their headings in sweep order, separated by spaces, as open: <headings>.
• Fold the (heading, room) pairs to the one with the most room (the earlier one on a tie) and print best: <heading> with <room> cm of room, with the room rounded to one decimal place.
• Turn right by the best heading at speed 30, and if the room is more than 0, drive forward by the room at speed 50.

Use map, filter and reduce; do not use max, min or sorted. The robot must not touch anything.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()
from functools import reduce

MARGIN = 15
OPEN_CM = 25

def sweep():
    readings = ()
    return readings

readings = sweep()
print("open:")

Challenges

1. Replace the fold with a recursive function roomiest(pairs) that uses only head, tail and a test for the empty tuple.
2. The sweep is the only impure part. Write a pure function plan(readings) that returns (heading, room) for the move to make, so the whole decision can be tested in one call without a robot.
3. Change with_room so it keeps the reading too, (heading, cm, room). Which other functions have to change, and which do not? What does that tell you about the types of the functions?