frederick99

Thue-Morse sequence

Jul 25th, 2021
921
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. {-  Print the first n elements of the Thue-Morse sequence. The Thue-Morse sequence
  2.     is a binary sequence (it comprises of only 1's and 0's) beginning with 0, which
  3.     is derived by repeatedly appending an inverted version of the sequence to the
  4.     sequence itself. The first few iterations look like this:
  5.         0
  6.         01
  7.         0110
  8.         01101001
  9.         0110100110010110
  10.     etc. -}
  11.  
  12. main = interact $ concatMap show . flip take tmSequence . read
  13. tmSequence = concat helper where
  14.     helper = [0] : map (concatMap invert . flip take helper) [1..]
  15.     invert = map (1 -)
  16.  
  17. -- Golfed (86 bytes)
  18. main=interact$c.map show.(`take`c t).read
  19. t=[0]:map(map(1-).c.(`take`t))[1..]
  20. c=concat
  21.  
  22. -- Fibonacci
  23. fib = 0 : 1 : zipWith (+) fib (tail fib)
  24.  
RAW Paste Data