Определение списка путем повторной записи/итерации

Question

Я хочу определить Thue-Morse Sequence (или fair-sharing sequence) в терминах начального элемента 0 и правила, определяющие следующий раздел списка в терминах всего списка до этой точки , т.е.

fair 0 = [0] 
--fair 1 = [0,1] 
--fair 2 = [0,1,1,0] 
--fair 3 = [0,1,1,0,1,0,0,1] 
fair n = fair (n - 1) ++ map (1-) (fair (n - 1)) 

Это прекрасно работает для создания списка до любой заранее определенной длины, но это, кажется неэффективным, не просто определить весь список сразу, и использовать take если мне нужно заранее определенную сумму.

Моя первая попытка определить весь список: fair = 0 : map (1-) fair, но, разумеется, это заполняет список, как он есть, поэтому он никогда не должен (нужно) повторно вводить список (и возвращает [0,1,0,1,0,1...]). То, что я хочу, - это способ определить список, так что, когда он достигнет еще не определенного элемента в списке, он определяет следующий «кусок», повторно введя список только до этой точки (а не вычисления ' чеканка»новых значения, как они производятся), так что шаги в вычислении списка будут сродни эта процедура:

• начинается с первоначальным списком, [0]
• карту (1-) поверх существующего список, производя [1]
• добавить в существующий список, производящий [0,1]
• карта (1-) поверх существующего списка, производя [1,0]
• Append это к существующему списку, производя [0,1,1,0]
• карту (1-) поверх существующего списка, производя [1,0,0,1]
• Append это к существующему списку, производя [0,1,1,0,1,0,0,1]

Wikipedia article У меня есть ссылка helpful gif, чтобы проиллюстрировать этот процесс.

Как я полагаю, вы можете видеть, это будет продолжаться бесконечно, так как нужны новые элементы. Тем не менее, я не могу для жизни меня найти способ успешно кодировать это в рекурсивной функции.

Я попытался

reenter f xs = reenter f (xs ++ map f xs) 
fair = reenter (1-) [0] 

Но в то время как логика кажется правильной, она висит, не производя ничего, вероятно, из-за непосредственный рекурсивный вызов (хотя я думал, что ленива оценка Хаскеля может позаботиться о том, что, несмотря на это время довольно сложный случай).

Answer 1

Как вы отметили, вы не можете сделать рекурсивный вызов немедленно - сначала нужно вернуть следующий результат, а затем рекурсивный вызов, как и в последней попытке:

Prelude> reenter prev_list = inverted_prev_list ++ reenter (prev_list ++ inverted_prev_list) where inverted_prev_list = map (1-) prev_list 
Prelude> f = [0] ++ reenter [0] 
Prelude> take 20 f 
[0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1] 

Answer 2

Ниже приведен код в Racket, еще один функциональный язык программирования, используя шаги, перечисленные в вопросе.

(define (f n) 

    (define (invert s)   ; sub-function to invert the numbers 
    (list->string 
    (for/list ((i (string->list s))) 
     (if (equal? i #\0) #\1 #\0)))) 

    (let loop ((c 1) 
      (s "0"))   ; starting string is "0" 
    (if (> c n) 
     s 
     (loop (add1 c) 
       (string-append s (invert s)))))) 

Тестирование:

(f 1) 
(f 2) 
(f 3) 
(f 4) 
(f 5) 

Выход:

"01" 
"0110" 
"01101001" 
"0110100110010110" 
"01101001100101101001011001101001" 

Для бесконечной серии:

(define (f) 
    (define (invert s) 
    (list->string 
    (for/list ((i (string->list s))) 
     (if (equal? i #\0) #\1 #\0)))) 

    (let loop ((s "0")) 
    (define ss (string-append s (invert s))) 
    (println ss) 
    (loop ss))) 

Для запуска:

(f) 

Это может дать некоторые идеи относительно решения Haskell для решения этой проблемы.