Optimizing samefringe

The essence of McCarthy's samefringe is "Two trees have the same fringe if they are eq, or if, when rotated all the way right, they have the same car and their cdrs have the same fringe.". This is points-free, and translates nicely into combinator style.

samefringe = hor eq (hand (and* .: consp) ((hand (eq .: car) (samefringe .: cdr)) .: rotate-right))
rotate-right = while (consp . car) (h cons caar (h cons cdar cdr))

.: is like compose, but wraps the second function around each of the first's arguments. This is an operation I need a lot. h is similar, but wraps a different function around each argument. Both of these need better names. and* is and as a function, and hand and hor are h-like versions. while iterates.

f .: g = λ x y ... -> f (g x) (g y) ...
h e f g ... = λ x y ... -> e (f x) (g y) ...
and* a b ... = (and a b ...)
while test step = named-λ loop init ... -> if (test init ...) (loop (step init ...)) init

If the combinators work on arbitrary numbers of arguments, we get n-ary samefringe for free. Not bad for two lines.

No comments:

Post a Comment

It's OK to comment on old posts.