Maintenance room

This was the maintenance room for Flood Control Dam #3. Apparently, the room has been ransacked, for most of the valuable equipment is gone. On one wall is a group of buttons colored yellow, brown and red. The only doorway is southwest.
There is a wrench here.
There is a screwdriver here.

> take the wrench and the screwdriver

wrench: Taken.
screwdriver: Taken.

> press the yellow button

Click.

> go southwest
> turn the bolt with the wrench

The sluice gates open and water pours through the dam.

> drop the wrench

Dropped.

> go west

Reservoir South
You are south of what was formerly a lake. However, with the water level lowered, there is merely a shallow stream, easily crossed. Paths lead east, south, and southwest.

> go north

Code for this and the next couple episodes is at https://github.com/ericlippert/flathead/tree/blog10

I want to step away from the Z-machine for an episode or two here and build some entirely abstract helper mechanisms. I am going to need to be able to compute the transitive and reflexive closures of relations, and boy does that sound highfalutin.

Here's what I'm getting at.

Suppose we have a relationship between one thing and several others. Like, for example, a relationship between a person and their children. A person can have zero or more children. Each of those children can have zero or more children. And so on. By a relation, I mean a function that takes a person and gives me a list of their children. The transitive closure of a relation is the function where given a person, I want a flat list of not just their children, but also their children's children, and so on forever; the whole set of descendants.

The reflexive closure is strictly speaking a function that takes a person and gives me a list of their children, oh, and the list also contains the person even though the person is not their own child. But for my purposes I only care about the reflexive-and-transitive closure - that is, given a person I want a list containing that person, their children, all their children, and so on. So for the purposes of the next couple of articles, when I say "the reflexive closure", you can mentally substitute in "the reflexive and transitive closure".

Being able to generate a closure function given a relation is very useful in many domains; imagine for example the relation "derives from class"; the transitive closure of that relation is the set of all base classes of a given class. Closures of relations come up frequently in programming and so I like to have this tool in my toolbox.

We can model a relation as a function which takes a thing and returns a list of the related things. The problem I want to solve today appears to be slightly harder than the problem stated: given a list of things and a relation function, compute the transitive closure of the relation on all the things, and then take the union of all those lists, eliminating duplicates. That sounds like a harder problem than the problem of simply computing the transitive closure of a relationship on one thing, but" well, let's look at the code.

The first thing I am going to need is a function called merge which takes three lists. For reasons which will become apparent, the lists will be called related, set and stack. The desired action of the merge method is as follows: every member of the related list either is already member of set, or is not. If it is a member of set, it is discarded. If it is not a member of set then it is added to both set and stack. We return the resulting set and stack.

Naturally we wish to do this recursively. If the related list is empty then plainly the resulting set and stack are the ones we've just been given:

let rec merge related set stack = match related with | [] -> (set, stack)

That's our base case. If it is not empty then the related list must have a head and a tail.

If the head is a member of set then discard it; we recurse on the tail. (This is where the term "tail recursion" comes from, incidentally, because the most common form of tail recursion is to recurse on the tail of a list!)

If the head is not in the set then we push it onto both the set and stack and recurse.

Either way, we took an element off the related list and so are making progress towards the base case.

 | head :: tail -> if List.mem head set then merge tail set stack else merge tail (head :: set) (head :: stack)

All right, now that I have this helper method I can compute my transitive closure. I have a list of items and a relation; I wish to compute the transitive closures of the relation on all the items, and merge them all together. How am I going to do that?

We know that the standard pattern for making tail-recursive methods that construct lists is to make an auxilliary function that takes an accumulator. We're going to do exactly that. Our auxilliary function takes as its accumulator the transitive closure computed so far - the "set" - and as its second argument, a stack of elements. The action of our method is to take an element off the stack, obtain everything related to that item, and then merge those onto the set and the stack. We keep on doing that until the stack is empty:

let transitive_closure_many items relation = let rec aux set stack = match stack with | [] -> set | head :: tail -> let (new_set, new_stack) = merge (relation head) set tail in aux new_set new_stack inaux [] items

I know this one is a bit tricky but it is worthwhile to wrap your brain around it.

How do we know that the resulting set contains only unique elements? Because we checked for duplicates before pushing onto the set.

How do we know that we got the entire transitive closure? Every element in the closure was at some point pushed at least once onto the stack, we ended with an empty stack, and we pushed every unique element from the stack onto the set.

How do we know that this terminates? Well, if the closure is infinite, it doesn't. But if the closure is finite then eventually we will pop every element off the stack. (OCaml, like C#, has the ability to represent lazily-computed sequences of items. If we had a huge closure, or an infinite closure, then we could use a lazily computed sequence. But again, I am trying to crawl before I run here; I'm still very new at OCaml and I want to have the basics solid.)

Is this efficient?

No, not really. Suppose the closure eventually contains n elements. That call to List.mem is O(n), so the total cost is n-squared. I could have used an immutable set type that has more efficient lookup, but immutable sets in OCaml are actually ordered binary trees behind the scenes, and that then requires that I provide a total ordering on the set, and blah blah blah, this was just easier. None of the closures I'm going to produce are large. If I cared enough I'd rewrite this helper method to use a set or a hash table or some such thing, but I don't.

Now that we have this little method, the transitive closure of a relation on a single item is easy, as is the reflexive transitive closure:

let transitive_closure item relation = transitive_closure_many [item] relationlet reflexive_closure_many items relation = let t = transitive_closure_many items relation in List.fold_left (fun s i -> if List.mem i s then s else i :: s) t itemslet reflexive_closure item relation = reflexive_closure_many [item] relation

We've got this tool in our toolbox; next time on FAIC: we'll use it!