ralph.ronnquist wrote:Then, how do you go the other way? I.e. how do you reduce into the smallest number of pairs, or at least find a sub list so that implied relationships are omitted from the list?
Well, I perceive that you know the answer already, so I thank you for letting us share in the fun. :)
Here is a function
untransD which removes the implied relationships. It does so by considering each edge
edge in
s which can be viewed as the pair
(src dst) (although dst is not needed here). The
clean fn answers the question "Is
edge implied?" That will be true when the reach of
src, after we remove
edge from
s, is the same is the reach of
src under
s.
Code: Select all
(define (untransD s)
(clean (fn (edge)
(let (src (edge 0)
remove (fn () (apply replace (args))))
(= (reach s src)
(reach (remove edge s) src))))
s))
Aside. For people not familiar with newLISP, note the
remove function (defined in the
let bindings). It appears as if it is only doing what the intrinsic
replace does; so, why not just say
(replace edge s) instead of
(remove edge s)? The reason for not doing that is subtle. The
replace primitive is destructive, and we don't want
s to change during the runtime of
untransD. Defining
remove as we've done here turns it into a non-destructive removal function (because of the calling model of newLISP: a copy gets passed the a function, not a reference).
But perhaps from a (software engineering) contracts point-of-view, we shouldn't rely on the order of the outputs of the
reach calls (i.e., its
stability). Even though we can see the code of
reach, we can also "play it safe" by assuming that we cannot see the implementation and thus replace the usage of
= with the usage of another equality predicate where the order doesn't matter. There may be a better way to do this, but here's one.
Code: Select all
(define (set-equal? A B)
(= (sort A) (sort B)))
The primitive
sort is also destructive; however, we don't need
A and
B (which are copies themselves) for anything else in the scope of this function (after we are done "smashing" them :). Happily, we can reuse
set-equal? in our testing.
First, let's recall what running
transD on the example input (
input) does.
Code: Select all
> input
((13 1) (9 19) (4 13) (4 12) (15 8) (3 15) (7 5)
(9 4) (11 0) (0 5))
> (transD input)
((0 5) (3 15) (3 8) (4 13) (4 1) (4 12) (7 5)
(9 19) (9 4) (9 13) (9 1) (9 12) (11 0)
(11 5) (13 1) (15 8))
Now, let's see
untransD in action.
Code: Select all
> (untransD (transD input))
((0 5) (3 15) (4 13) (4 12) (7 5) (9 19) (9 4)
(11 0) (13 1) (15 8))
Well, the order is different, but it sorta looks a lot like
input (by "eyeballing" it). So, how can we test this a little better? It seems that we should be able to say that
transD and
untransD are inverses of each other. Let's try that.
First, note that the example input itself is devoid of implied relationships.
Code: Select all
> (set-equal? input (untransD input))
true
That means the following identity should hold.
Code: Select all
> (set-equal? input (untransD (transD input)))
true
ralph.ronnquist wrote:newlisp is fun :)
Indeed! :)
(λx. x x) (λx. x x)