This is a follow-up question to my Puzzling.SE question: I asked if there’s a function f mapping Boolean strings to Boolean strings, so that f(f(b)) = reverse(b) for all input strings b. (By reverse, I mean the function that reverses the order of bits.)
The above link contains a positive answer, with proof, by the great f'', but you might want to ponder the question for yourself before looking.
Implement such a function f in as few bytes as possible.
You may either read input from STDIN, or take a function argument; and either write the result string to STDOUT, or return it.
Either way, you may work with actual strings of two distinct bytes or characters of your choice (say
0and1, or\x00and\x01), or with arrays/lists of truthy and falsy values. Pick two values and stick with those, though.The result of a single application of f must be a binary string itself: no silly answers like
b -> if b starts with 'x' then reverse(b[1:]) else 'x' + b...Your function should be total; in particular, the input may be the empty string, or one bit long, etc. There’s no upper bound for the string’s length.
It should also be pure: don’t keep any global state between function calls; the input string must completely determine the output string.