Как создать последовательность Пруе – Туэ – Морса в Хаскеле?

Question

Я новичок в Haskell, но немного опыта с ActionScript 3.0 Object Orientated. Таким образом, работает над основным переходом программирования. Я прочитал базовые знания о Хаскеле, как арифметика. И я могу написать простые функции.

В качестве практического задания мне нужно сгенерировать последовательность Туэ-Морса , называемую tms1, с помощью компьютера в Haskell. Так и должно быть:

>tms1 0
0
>tms1 1
1
>tms1 2
10
>tms1 3
1001
>tms1 4
10010110

и так далее ... Согласно википедии я должен использовать формулу.

t0 = 0
t2n = tn
t2n + 1 = 1 − tn

Я понятия не имею, как я могу реализовать эту формулу в Haskell. Можете ли вы помочь мне создать его? Вот что я получил до сих пор:

module ThueMorse where
tms1 :: Int -> Int
tms1 0 = 0
tms1 1 = 1
tms1 2 = 10
tms1 3 = 1001
tms1 x = tms1 ((x-1)) --if x = 4 the output will be 1001, i don't know how to make this in a recursion function

Я провел небольшое исследование в интернете и нашел этот код.

Источник: http://pastebin.com/Humyf6Kp

Код:

module ThueMorse where
tms1 :: [Int]
tms1 = buildtms1 [0] 1
    where buildtms1 x n 
        |(n `rem` 2 == 0) = buildtms1 (x++[(x !! (n `div` 2))]) (n+1)
        |(n `rem` 2 == 1) = buildtms1 (x++[1- (x !! ((n-1) `div` 2))]) (n+1)

custinv []  = []
custinv x   = (1-head x):(custinv (tail x))

tms3 :: [Int]
tms3 = buildtms3 [0] 1
    where buildtms3 x n = buildtms3 (x++(custinv x)) (n*2)

intToBinary :: Int -> [Bool]
intToBinary n   | (n==0) = []
                | (n `rem` 2 ==0) = intToBinary (n `div` 2) ++ [False]
                | (n `rem` 2 ==1) = intToBinary (n `div` 2) ++ [True]

amountTrue :: [Bool] -> Int
amountTrue [] = 0
amountTrue (x:xs)   | (x==True) = 1+amountTrue(xs)
                    | (x==False) = amountTrue(xs)

tms4 :: [Int]
tms4= buildtms4 0
    where buildtms4 n
        |(amountTrue (intToBinary n) `rem` 2 ==0) = 0:(buildtms4 (n+1))
        |(amountTrue (intToBinary n) `rem` 2 ==1) = 1:(buildtms4 (n+1))

Но этот код не дает желаемого результата. Любая помощь приветствуется.

Answer 1

Я бы предложил использовать список логических значений для вашего кода; тогда вам не нужно явно конвертировать числа. Я использую последовательность, определенную так:

0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
...

Обратите внимание, что ведущие нули очень важны!

Рекурсивное определение теперь легко:

morse = [False] : map step morse where step a = a ++ map not a

Это работает, потому что мы никогда не обращаемся к элементу, который еще не определен. Печать списка оставлена ​​читателю в качестве упражнения.

Вот другое определение, использующее тот факт, что следующий шаг можно получить, заменив 1 на 10 и 0 на 01:

morse = [False] : map (concatMap step) morse where step x = [x,not x]

Редактировать

Вот более простые определения sdcvvc с использованием функции iterate. iterate f x возвращает список повторных приложений от f до x, начиная с отсутствия приложения:

iterate f x = [x,f x,f (f x),f (f (f x)),...]

А вот и определения:

morse = iterate (\a -> a ++ map not a) [False]
morse = iterate (>>= \x -> [x,not x]) [False]

Answer 2

Ваше определение последовательности выглядит как последовательность битовых последовательностей:

0  1  10 1001 10010110 ... etc.
t0 t1 t2 t3   t4

но страница википедии определяет его как единственную битовую последовательность:

0  1  1  0  1  ... etc
t0 t1 t2 t3 t4

Это формулировка, на которую ссылаются определения в Википедии. С этим знанием определение рекуррентного отношения, которое вы упомянули, легче понять:

t0 = 0
t2n = tn
t2n + 1 = 1 − tn

На английском языке это можно указать как:

• Нулевой бит равен нулю.
• Для четного ненулевого индекса этот бит совпадает с битом на половине индекса.
• Для нечетного индекса бит равен 1 минус бит на половине (индекс минус один).

Сложная часть идет от индексов 2n и 2n + 1 к нечетным и четным, и понимая, что означает n в каждом случае. Когда это сделано, написать функцию, которая вычисляет * n * -й бит последовательности:

lookupMorse :: Int -> Int
lookupMorse 0 = 0;
lookupMorse n | even n    =     lookupMorse (div  n    2)
              | otherwise = 1 - lookupMorse (div (n-1) 2)

Если вы хотите, чтобы вся последовательность, map lookupMorse по неотрицательным целым числам:

morse :: [Int]
morse = map lookupMorse [0..]

Это бесконечная последовательность Туэ-Морса. Чтобы показать это, take несколько из них, превратить их в строки и объединить полученную последовательность:

>concatMap show $ take 10 morse
"0110100110"

Наконец, если вы хотите использовать определение «последовательности битовых последовательностей», вам нужно сначала удалить некоторые биты из последовательности, а затем взять некоторые. Число для отбрасывания совпадает с числом для взятия, кроме случая с нулевым индексом:

lookupMorseAlternate :: Int -> [Int]
lookupMorseAlternate 0 = take 1 morse
lookupMorseAlternate n = take len $ drop len morse
    where
        len = 2 ^ (n-1)

Это дает альтернативное определение последовательности:

morseAlternate :: [[Int]]
morseAlternate = map lookupMorseAlternate [0..]

который вы можете использовать следующим образом:

>concatMap show $ lookupMorseAlternate 4
"10010110"
>map (concatMap show) $ take 5 morseAlternate
["0", "1", "10", "1001", "10010110"]

Answer 3

Легко, как это:

invertList :: [Integer] -> [Integer]
invertList [] = []
invertList (h:t) 
    |h == 1 = 0:invertList t
    |h == 0 = 1:invertList t
    |otherwise = error "Wrong Parameters: Should be 0 or 1"

thueMorse :: Integer -> [Integer]
thueMorse 1 = [0]
thueMorse n = thueMorse (n - 1) ++ invertList (thueMorse (n - 1))