### 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.

#### Post a Comment

It's OK to comment on old posts.