haskell - 无限自引用列表

Question

问题

我正在尝试实现修改后的 Dragon Curve来自 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

我在解决 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 - 但与其他解决方案不同，它只在输入大小的数据 block 上调用一次，而不是在同样大的数据 block 上重复调用作为您消费的 list 的一部分。)一些时间来证明我的主张是合理的；所有版本用于生成 2^25 个元素，种子为空，使用 ghc -O2 编译，并使用 /usr/bin/time 计时。

freestyle 的解决方案耗时 11.64 秒，最大驻留时间约为 1.8Gb
David Fletcher 的解决方案耗时 10.71 秒，最大驻留时间约为 2Gb
luqui 的解决方案需要 9.93 秒，~1GB max resident
我的解决方案需要 8.87 秒，最大驻留时间约为 760MB

完整的测试程序是

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

用 dragon 依次替换为每个实现。精心设计的消费者可以进一步降低内存使用量:到目前为止，我对第二星问题的最佳解决方案在 5Mb 实际驻留中运行(即包括从操作系统为其多代分配的所有 GHC 空间、松弛空间和其他 RTS 开销)，60Kb GHC 报告的驻留(即，仅由尚未 GC 处理的对象使用的空间，无论 GHC 从操作系统分配了多少空间)。

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