The previous blog post gave us our first aspect to look for in a problem, meaningful structure in our valid input blob. Let’s look at some concrete examples.
The important thing about a metric space is that you are able to create some sort of distance function. However, this isn’t the only thing that we are going to care about when determining whether a problem is easy to deal with. The point of having your valid input blob be a metric space is that it provides your intuition something to work with. So just being able to from some metric space with some distance function doesn’t necessarily mean you are encountering a comprehensible problem. The distance function has to be known and internalized and make the problem more sensible.
type IntList =
| ICons of int * IntList
| INil
let someFunc (x : IntList) = …In this example, the IntList data structure can be used to define the valid input blob of the function someFunc. We can define several different meaningful distance functions for IntList; the one you choose is going to be the one that is relevant to the work being done in the someFunc function.
let d1 x y = abs( count( x ) – count ( y ) )
let d2 x y = abs( max( x ) – max( y ) )
let d3 x y = sqrt( sqr( d1( x, y ) ) + sqr( d2( x, y ) ) )
…The function that best helps you mentally organize different instances of IntList with respect to someFunc is the one that you’re going to want to select.
Some functions aren’t going to have meaningful distance functions though.
public interface Input
{
Input Generate();
int Distance( Input other );
}
public static class SomeClass
{
public static void SomeFunc( Input i ) { ... }
}
void function( Input i )
{
var input = i.Generate();
SomeClass.SomeFunc( input );
}In this example we have a completely opaque object that implements the interface Input. The Generate method creates a new instance of the Input interface, but we do not have any way to know what the new actual implementing class is. Theoretically, you could create a Distance function that tells you how far apart any two instances of Input are from each other in system memory. This would be a valid metric space, but it wouldn’t help you mentally organize the behavior of the SomeClass.SomeFunc method.
There is a Distance method provided on the Input interface. But again without knowing what it means, we can’t organize our thoughts around it. You might be able to call Distance on every pair of Input instances you come across. From this you might be able to derive understanding on the behavior of the Input objects, but you would never know when a new implementor of Input would show up and destroy what you thought you understood about Input.
If SomeClass.SomeFunc reacts identically to every instance of Input that is passed to it as a parameter, then we can create a distance function that always returns zero. Conceptually all values of Input are the same with respect to SomeClass.SomeFunc. However, if this isn’t the case, then SomeClass.SomeFunc becomes a problem that is difficult to deal with.
Okay, lets move on from metric spaces and look at a new aspect to manage our problems.
