无限自引用列表

Question

问题

我正在尝试将修改后的 Dragon Curve from AoC Day 16 实现为 Haskell 中的无限列表。

列表由True和False组成。我们从一些列表 s0:

开始

s1 = s0 ++ [False] ++ (map not . reverse) s0
s2 = s1 ++ [False] ++ (map not . reverse) s1
s3 = s2 ++ [False] ++ (map not . reverse) s2

一般

sn = s(n-1) ++ [0] ++ (map not . reverse) s(n-1) 
   = s0 ++ [0] ++ (f s0) ++ [0] ++ (f (s0 ++ [0] ++ (f s0))) ++ ...
      where f = (map not . reverse)

尝试实施

我可以使用 iterate 函数很容易地得到 sn。

modifiedDragonCurve :: [Bool] -> Int -> [Bool]
modifiedDragonCurve s n = (iterate f s)!!n
    where f s     = s ++ [False] ++ (map not . reverse) s

这给了我一个列表 [s0, s1, s2, ...]。但是，由于 s(n-1) 是 sn 的前缀，因此可以将其构建为无限列表，但我不知道如何处理它。我想我需要一些类似

的东西

modifiedDragonCurve :: [Bool] -> [Bool]
modifiedDragonCurve s = s ++ [False] ++ (map not . reverse) listSoFar

但无法弄清楚如何引用已生成的列表 (listSoFar)。

如有任何建议，我们将不胜感激。

Answer 1

这是一种方法。我们列出的不是 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

Answer 2

例如：

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

Answer 3

你这个书呆子用这个来狙击我。这不是一个自引用列表，但我确实想出了一个 "wasteless" 解决方案——一个我们不会丢失或忘记我们计算过的任何东西的解决方案。

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 inverted 因为那时我需要做的就是在每个步骤前添加 b' （甚至不检查 a），我们不需要比我们更多的反转到.

作为书呆子，我研究了很多其他数据结构，认为链表可能不是解决这个问题的最佳选择，包括 DList、Data.Sequence（手指树），免费幺半群（它应该善于被逆转），以及一个取消逆转的自定义树。令我惊讶的是，list 仍然是所有这些中最好的，我仍然对此感到困惑。如果你好奇，here is my code.

Answer 4

我自己也在解决AoC问题的时候玩过这个。我找到了一个不需要逆向的出色解决方案，因此比此处列出的其他解决方案更加内存友好和快速。也很美！龙曲线本身就是一个不错的短双线：

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

它可以扩展为使用 "seed" 作为 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.8Gb 最大驻留
David Fletcher 的解决方案需要 10.71 秒，~2Gb max resident
luqui 的解决方案需要 9.93 秒，~1GB max resident
我的解决方案需要 8.87 秒，最大驻留 ~760MB

完整的测试程序是

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

和dragon依次被每个实现替换。精心设计的消费者可以进一步降低内存使用率：到目前为止，我对二星级问题的最佳解决方案运行在 5Mb 实际驻留（即包括从 OS 为其多代分配的所有 space GHC ，slack space，和其他 RTS 开销），60Kb GHC 报告的驻留（即只是 space 被尚未 GC 的对象使用，不管 space GHC 有多少从OS).

分配

但是，对于原始速度，您无法击败 Bool 的未装箱可变向量：一位同事报告说他的程序在 0.2 秒内使用了这样的运行，使用了大约 35Mb 的内存来存储完整的扩展（但不是无限！）向量。

无限自引用列表

Infinite self-referencing list

haskell

sequence

infinite

recursive-datastructures

self-reference

问题

尝试实施