Реализация необычной последовательности в виде бесконечного списка в Haskell - PullRequest
Новая
       51

Реализация необычной последовательности в виде бесконечного списка в Haskell

4 голосов
/ 09 октября 2019

У меня есть два элемента в начале списка [1, 2]

Эта необычная последовательность состоит в том, что она копирует цифры в количестве цифр определенного типа, который следует за этими тремя элементами. Например, после 1 и 2 у нас будет еще 2, а затем два 1. Первые несколько элементов желаемого списка приведут к

[1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2] потому что 

1  2   2  1 1   2  1  2   2  1   2   2

, где предыдущие цифры представляют длину мини-последовательностей одной и той же цифры.

До сих пор я пытался использовать функцию replicateдля повторения той же цифры на основе элемента, ранее в списке. 

selfrle :: [Int]
selfrle = 1 : 2 : [x | a <- [0..], let x = replicate (selfrle !! a) (selfrle !! (a + 1))) ]

Проблема в том, что я не могу понять, почему он не работает.

Ответы [ 4 ]

5 голосов
/ 09 октября 2019

Не так уж и необычно, как в OEIS в https://oeis.org/A000002 и названо там как последовательность Колакоски. Там они даже дают программу на Haskell Джона Тромпа от 2011 года: 

a = 1:2: drop 2 (concat . zipWith replicate a . cycle $ [1, 2])
2 голосов
/ 09 октября 2019

Первое, что вы можете сделать, это правильно настроить ваши типы. replicate создает список, поэтому x в вашем понимании списка имеет тип [Int], а полное понимание списка представляет собой список всех значений x, а его тип - [[Int]]. Вы не можете использовать список списков из Int в качестве хвоста списка, когда первые два элемента - 1 и 2. Типы просто не совпадают: вам нужно решить, будет ли это список Int или список списков из Int.

Основываясь на вашем описании, яПодозреваю, что вы хотите исправить это, сгладив понимание списка, используя concat, например так: 

selfrie = 1 : 2 : concat [x | a <- [0..],
                              let x = replicate (selfrie !! a) (selfrie !! (a + 1))]

Если вы попробуете это, вы не получите описанный вами список. Я не знаю, как помочь со следующей частью, и это потому, что я не понимаю вашего описания желаемого списка. Это не вопрос программирования, а скорее вопрос спецификации, так что, возможно, вы могли бы вернуться к исходному источнику и посмотреть, как он там объясняется?

0 голосов
/ 12 ноября 2019

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

Мы можем перефразировать его как 

a = 1:2:2: (concat . zipWith replicate (drop 2 a) . cycle) [1, 2]

Мы должны помнитьa - это просто полуструктурированный список, подобный 1:2:2:?: ... ?:[], и мы начинаем использовать его, просто отбрасывая первые два элемента (drop 2 a), что оставляет нам 2:?: ... ?:[] для применения к zipWith replicate, и этого достаточно для запусканаша логика неопределенна. Имейте в виду, 2:?: ... ?:[] - это список, который должен быть рассчитан так же, как cycle [1,2]. Наличие исходного элемента 2 позволяет рассчитать следующий элемент, а затем следующий элемент, а затем следующий и т. Д.

Это прекрасный шаблон в Haskell для генерации бесконечных списков, если вы знаетеначальные предметы. Возьмем, к примеру, серию Фибоначчи 

fib = 1:1: (zipWith (+) fib (tail fib))

Все, что вам нужно сделать, это настроить ваше мышление, чтобы думать, что fib уже существует, но еще не рассчитано.

Другой подходс Государственной Монадой:

Тем не менее, я считаю, что данная серия Колакоски также может быть хорошим примером для изучения Государственной монады. Давайте посмотрим, сможем ли мы получить такую ​​же производительность ..? 

import Control.Monad.Trans.State

invert :: Int -> Int
invert = (+1) . (`mod` 2)

rle :: Int -> State Int [Int]
rle n = state $ \s -> (replicate n s, invert s)

kolakoski :: [Int] -> Int -> [Int]
kolakoski ps s = ps ++ kolakoski xs i
                 where (xs,i) = runState (mapM rle ps >>= pure . concat) s
  • У нас есть функция invert, когда с 1 дает 2, а с 2 с 1.
  • rle принимает тип Int и возвращает тип State, функцию, которая принимает состояние и реплицирует его на n и возвращает реплицированный список вместе с новым состоянием,invert s. Таким образом, наше состояние чередуется, например, 1,2,1,2....

Однако при тестировании с ghci (:set +s), хотя оба демонстрируют линейную сложность по времени, для финализации требуется в 10 раз больше времени. Кто-нибудь хочет прокомментировать ..?

0 голосов
/ 09 октября 2019

Мы можем написать это немного более элегантно, чем @ ответ DanD , используя дополнительную переменную b, с которой мы "связываем узел": 

a :: [Int]
a = 1 : 2 : b
    where b = 2 : concat (zipWith replicate b (cycle [1, 2]))

Мы здесь таким образомсначала выведите 1 : 2 : b, с b, который начинается с 2, а затем конкатенацию повторов b с бесконечным списком с [1, 2, 1, 2, &hellip;].

...