无限的自引用列表

Question

问题

我试图执行修改后的龙形曲线从业务计费16日在哈斯克尔无限名单.

该列表由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)

尝试实施

我可以sn很容易地使用该iterate功能.

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一次 - 但与其他解决方案不同的是,它只在一大块关于输入大小的数据上调用一次,而不是在与您使用的列表部分一样大的数据块上重复调用.)时间来证明我的主张; 所有版本用于生成带有空种子的2 ^ 25个元素,用,编译ghc -O2和定时/usr/bin/time.

freestyle的解决方案需要11.64s,最大1.8Gb驻留
David Fletcher的解决方案需要10.71s,~2Gb最大驻留
luqui的解决方案需要9.93s,最大~1GB,
我的解决方案需要8.87s,最大~760MB

完整的测试程序是

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

与dragon通过依次每个实现替换.精心设计的消费者可以进一步降低内存使用率:到目前为止,我对第二个星问题的最佳解决方案是以5Mb实际驻留时间运行(即包括从OS分配的多代GHC空间和其他RTS开销的所有空间GHC) ),60Kb GHC报告的驻留时间(即只有尚未GC的对象使用的空间,无论GHC从OS分配了多少空间).

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