Haskell正则数序列代码的性能与内存行为技术问询

以下是一段基于维基百科算法实现的Haskell正则数（仅以2、3、5为质因数的正整数）生成代码，以及对应的运行示例：

regularSeq :: [Integer]
regularSeq = 1 : union timesTwo (union timesThree timesFive)
  where
    timesTwo   = map (* 2) regularSeq
    timesThree = map (* 3) regularSeq
    timesFive  = map (* 5) regularSeq

union :: (Ord a) => [a] -> [a] -> [a]
union [] ys = ys
union xs [] = xs
union (x : xs) (y : ys)
  | x < y     = x : union      xs (y : ys)
  | x > y     = y : union (x : xs)     ys
  | otherwise = x : union      xs      ys

示例运行结果：

ghci> takeWhile (<= 60) regularSeq 
[1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40,45,48,50,54,60]

问题1：regularSeq的旧值是否会被缓存复用？ #

会被缓存复用，不会生成低效的3叉计算树。Haskell中顶级定义（如regularSeq）默认是记忆化的，一旦某个元素被求值，结果就会被存储起来。timesTwo、timesThree、timesFive都是基于regularSeq的映射，当它们需要访问regularSeq的某个元素时，直接读取已缓存的值即可，无需重新计算。这和naive Fibonacci实现完全不同——后者每次递归都会重复计算子问题，而这里的regularSeq是共享的惰性列表，所有依赖它的映射都会复用已求值的元素。

问题2：内存中是否仅存在一个整数列表？ #

内存中存在一个核心的regularSeq列表，timesTwo、timesThree、timesFive是这个列表的惰性视图，并非独立列表。map函数在Haskell中是惰性的，timesTwo不会提前生成所有元素，而是在需要的时候才从regularSeq取出元素乘以2。本质上这三个序列只是指向regularSeq不同位置的指针，加上延迟执行的乘法逻辑，它们共享regularSeq的底层存储，不会重复存储相同的整数。

问题3：Haskell的GC能否释放旧的不可达元素？ #

Haskell的GC可以识别并释放不可达的旧元素。如果代码中只保留了timesFive头部到当前值的引用（比如遍历序列时仅持有当前位置的指针，没有保留对更早元素的引用），那些不再被任何引用指向的旧元素会被GC标记为垃圾并回收。但如果有其他地方（如GHCi历史记录、调试工具或代码中的其他引用）保留了对regularSeq早期元素的引用，这些元素就不会被释放。在纯粹的流式处理场景下，GC会自动回收不再需要的旧元素。

问题4：推理Haskell内存行为的通用原则与框架 #

可以遵循以下核心原则：

• 惰性求值与记忆化：模块级的顶级绑定默认记忆化，一旦求值就缓存结果；let/where绑定同样具备记忆化特性，而case或lambda中的临时变量通常不记忆化。
• 数据共享：Haskell天然鼓励数据共享，相同的表达式只会被求值一次，所有引用都会指向同一个结果。比如map f xs不会复制xs，而是生成依赖xs的惰性结构。
• 可达性决定存活：GC仅回收无任何可达引用的数据。如果数据结构的部分元素不再被变量、闭包或活跃计算引用，这部分元素就会被回收。
• 惰性结构本质：列表、Map等惰性结构是由延迟计算的thunk和已求值节点组成的链。遍历惰性列表时，若前面的节点不再被引用，就会被GC回收。

推理时可从这几点切入：先确定哪些绑定是记忆化的，再分析数据的引用关系，最后判断哪些部分是可达的，以此推断内存使用情况。

内容的提问来源于stack exchange，提问作者Federico