thue-morse.lam

/*
In mathematics, the Thue–Morse sequence, or Prouhet–Thue–Morse sequence, is the
binary sequence (an infinite sequence of 0s and 1s) obtained by starting with 0
and successively appending the Boolean complement of the sequence obtained thus
far. The first few steps of this procedure yield the strings 0 then 01, 0110,
01101001, 0110100110010110, and so on, which are prefixes of the Thue–Morse
sequence. 
  -- https://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence

Translated from term found on http://joerg.endrullis.de/lambdaCalculator.html
*/
#define b0 (\x \y x)
#define b1 (\x \y y)
#define Cons (\x \y \c c x y)
#define Y (\f (\x f (x x))(\x f (x x)))
#define Zip Y (\z \l \r Cons (l b0) (Cons (r b0) (z (l b1) (r b1))))
#define Inv Y (\i \s Cons (s b0 b1 b0) (i (s b1)))
#define Tail (\s s b1)

\input Y (\morse Cons b0 (Zip (Inv morse) (Tail morse)))