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 as a function, and
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.