无限的自引用列表 [英] Infinite self-referencing list

问题描述

问题

我正在尝试执行修改后的 AoC Day 16 的noreferrer> Dragon Curve 。

该列表由 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] ++（fs0）））++ ... 
  其中f =（地图不是反向）
    

  
  
  

  试图执行

  
  
  

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

    modifiedDragonCurve :: [Bool ]  - > Int  - > [bool] 
   modifiedDragonCurve sn =（iterate fs）!! n 
  其中fs = 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 ）。

  
  
  

  任何建议将不胜感激。

  解决方案

  在解决AoC问题的同时，我自己也玩过这个游戏。我发现了一个不需要反转的显着解决方案，因此比此处列出的其他解决方案更具有内存友好和更快的速度。它也很漂亮！龙的曲线本身是一个很好的短双线：
  
  

    merge（x：xs）ys = x：merge ys xs 
   dragon = merge（cycle [False，True]）龙
    

  可以扩展使用作为AoC问题的种子只是通过种子和真龙曲线之间的交替来实现：
  
  

    infinite bs = go bs（map not（reverse bs））dragon where 
   go bs bs'（d：ds）= bs ++ [d] ++ go bs'bs ds 
    

  （这确实会调用反向一次 - 但与其他解决方案不同，它仅被称为一次关于输入大小的大量数据，而不是重复关于大小与您所使用的列表部分一样大的数据。）有些时间来证明我的观点;用 ghc -O2 编译并用 / usr / bin / time 编译的空种子生成2 ^ 25元素的所有版本。 code $。

freestyle的解决方案需要11.64s，最大〜1.8Gb居民

David Fletcher的解决方案需要10.71s，最大约2Gb

luqui的解决方案需要9.93秒，最大〜1GB居民

我的解决方案需要8.87秒，最高驻留时间为〜760MB



  完整的测试程序是


    main = mapM_ print。采取（2 ^ 25）。龙$ [
    

  加上龙取代每个实施依次进行。精心设计的消费者可以进一步降低内存使用量：迄今为止，我对第二颗星问题的最佳解决方案是5Mb真实驻留（即，包括从OS为其多代分配的所有空间GHC，松弛空间和其他RTS开销），60Kb GHC报告的驻留（即，只有尚未GC对象使用的空间，无论GHC从操作系统分配多少空间）。



  然而，对于原始速度，你无法击败一个无盒的可变向量 Bool ：一位同事报告说他的程序使用这种运行在0.2s，使用大约35Mb的内存存储完整的扩展（但不是无限！）向量。

  
  

  Problem

  I'm trying to implement the modified Dragon Curve from AoC Day 16 as an infinite list in Haskell.

  The list is composed of True and False. We start with some list s0:

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

  Generally

  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)
  

  Attempted Implementation

  I can get sn quite easily using the iterate function.

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

  This gives me a list [s0, s1, s2, ...]. However, since s(n-1) is a prefix of sn this could be built as an infinite list, but i cannot figure out how to approach it. I think I need something along the lines of

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

  But cannot figure out how to refer to the already generated list (listSoFar).

  Any suggestions would be greatly appreciated.

  解决方案

  I played with this myself while solving the AoC problem, too. I found a remarkable solution that does not require reverse, hence is more memory-friendly and speedy than the other solutions listed here. It's also beautiful! The dragon curve itself is a nice short two-liner:

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

  It can be extended to use a "seed" as the AoC problem demands just by alternating between the seed and the bits of the true dragon curve:

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

  (This does call reverse once -- but unlike other solutions, it is called just once on a chunk of data about the size of the input, and not repeatedly on chunks of data about as large as the part of the list you consume.) Some timings to justify my claims; all versions used to produce 2^25 elements with an empty seed, compiled with ghc -O2, and timed with /usr/bin/time.

  freestyle's solution takes 11.64s, ~1.8Gb max resident
  David Fletcher's solution takes 10.71s, ~2Gb max resident
  luqui's solution takes 9.93s, ~1GB max resident
  my solution takes 8.87s, ~760MB max resident

  The full test program was

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

  with dragon replaced by each implementation in turn. A carefully crafted consumer can lower memory usage even further: my best solution to the second-star problem so far runs in 5Mb real residency (i.e. including all the space GHC allocated from the OS for its multiple generations, slack space, and other RTS overhead), 60Kb GHC-reported residency (i.e. just the space used by not-yet-GC'd objects, regardless of how much space GHC has allocated from the OS).

  For raw speed, though, you can't beat an unboxed mutable vector of Bool: a coworker reports that his program using such ran in 0.2s, using about 35Mb memory to store the complete expanded (but not infinite!) vector.

  这篇关于无限的自引用列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！