Бесконечный список ссылок на самих себя

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

merge (x:xs) ys = x:merge ys xs
dragon = merge (cycle [False, True]) dragon

Его можно расширить, чтобы использовать «начальное число», как того требует проблема AoC, просто чередуя начальное число и биты истинной кривой дракона:

infinite bs = go bs (map not (reverse bs)) dragon where
    go bs bs' (d:ds) = bs ++ [d] ++ go bs' bs ds

(Это вызывает reverse один раз, но, в отличие от других решений, он вызывается только один раз для фрагмента данных о размере входных данных, а не повторно для фрагментов данных размером с часть потребляемого вами списка.) Некоторые тайминги, чтобы оправдать мои претензии; все версии, используемые для создания 2 ^ 25 элементов с пустым начальным числом, скомпилированы с ghc -O2 и синхронизированы с /usr/bin/time.

решение от freestyle занимает 11,64 с, макс. ~1,8 Гб резидентного режима
Решение Дэвида Флетчера занимает 10,71 с, макс. ~2 Гб резидентного режима
решение luqui занимает 9,93 с, макс. житель

Полная программа испытаний была

main = mapM_ print . take (2^25) . dragon $ []

с заменой dragon каждой реализацией по очереди. Тщательно продуманный потребитель может еще больше снизить использование памяти: мое лучшее решение проблемы второй звезды на данный момент работает в реальном местоположении 5 МБ (т. ), 60 КБ, о котором сообщает GHC (т. е. только пространство, используемое объектами, еще не подвергнутыми сборке мусора, независимо от того, сколько места GHC выделил из ОС).

Однако по чистой скорости вы не можете превзойти неупакованный изменяемый вектор Bool: коллега сообщает, что его программа, использующая такой, работала за 0,2 с, используя около 35 МБ памяти для хранения полного расширенного (но не бесконечного!) вектора.

Вот один из способов. Мы составляем список не из s0, s1 и т. д., а только из новой части на каждом шаге, тогда мы можем просто объединить их вместе.

dragonCurve :: [Bool]
dragonCurve = concatMap f [0..]
  where
    f n = False : (map not . reverse) (take (2^n-1) dragonCurve)

(Это предполагает, что s0 = []. Если это может быть что-то другое, вам придется изменить вычисление длины.)

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

dragonCurve' :: [Bool]
dragonCurve' = concat (unfoldr f [])
  where
    f soFar = Just (part, soFar ++ part)
      where
        part = False : (map not . reverse) soFar

Ты полный ботаник, подстреливший меня этим. Это не самоссылающийся список, но мне удалось найти «безотходное» решение — такое, при котором мы не отбрасываем и не забываем ничего, что вычислили.

dragon :: [Bool] -> [Bool]
dragon = \s -> s ++ gen [] s
    where
    inv = map not . reverse
    gen a b =
        let b' = inv b
            r = b' ++ a
        in False:r ++ gen r (False:r)

gen a b принимает в качестве входных данных все данные текущей последовательности, так что текущая последовательность равна inv a ++ b. Затем мы генерируем остаток в r, выводим его и рекурсивно продолжаем генерировать остаток. Я принимаю инвертированное a, потому что тогда все, что мне нужно сделать, это добавить b' на каждом этапе (что даже не проверяет a), и нам не нужно инвертировать больше, чем нужно.

Будучи ботаником, я исследовал довольно много других структур данных, полагая, что связанный список, вероятно, не лучший вариант для этой проблемы, включая DList, Data.Sequence (деревья пальцев), свободный моноид (который должен быть хорошо обращен) и пользовательское дерево, которое отменяет реверсы. К моему удивлению, список по-прежнему показал лучшие результаты, и я до сих пор сбит с толку этим. Если вам интересно, вот мой код.

Например:

dragon s0 = s0 ++ concatMap ((False :) . inv) seq
  where
    inv = map not . reverse
    seq = iterate (\s -> s ++ False : inv s) s0