Haskell:处理死锁的自引用列表

Question

GHC是否允许以下内容永久阻止是否有任何有用的理由:

list = 1 : tail list

在列表迭代器/生成器中看起来有点复杂,我们应该能够做一些更有用的事情:

解释2:似乎有可能在进入生成器获取元素时N,我们可以将生成器内的所有自引用限制为列表但结束于N-1(我们注意到read N范围内部generate N并返回列表结尾).这是一种使用范围的简单死锁检测.

显然,这对于上面的玩具示例没有用处,但它可以允许更有用/优雅的有限,自引用列表定义,例如:

primes = filter (\x -> none ((==0).mod x) primes) [2..]

请注意,任何更改都应该只影响当前导致无限块的列表生成器,因此它们似乎是向后兼容的语言更改.

忽略了稍微做出这种改变所需的GHC复杂性,这种行为会破坏我所遗漏的任何现有语言行为吗？关于这种变化的"优雅"的任何其他想法？

另请参阅另一个可以从下面获益的BFS示例.对我来说,这似乎比其他一些解决方案更实用/更优雅,因为我只需要定义bfsList 是什么,而不是如何生成它(即指定终止条件):

bfs :: (a -> Bool) -> (a -> [a]) -> [a] -> Maybe a
bfs predf expandf xs = find predf bfsList
    where bfsList = xs ++ concatMap expandf bfsList

Answer 1

这是一个关于如何的指称观点list = 1 : ?.

首先,一点背景.在Haskell中,值由"定义性"部分排序,其中解决⊥("底部")的值比没有定义的值少.所以

但这是一个偏序,所以

即使第二个列表更长. 1 : ?仅比从1开始的列表更少定义.我强烈建议阅读有关Haskell的指称语义.

现在回答你的问题.看着

list = 1 : tail list

作为要解决的等式而不是"函数声明".我们这样重写:

list = ((1 :) . tail) list

以这种方式查看,我们看到这list是一个固定点

list = f list

哪里f = (1 :) . tail.在Haskell语义中,通过根据上述排序找到最小固定点来解决递归值.

找到这个的方法很简单.如果从⊥开始,然后反复应用该函数,您将发现一个不断增加的值链.链条停止变化的点将是最不固定的点 (从技术上讲,它将是链条的限制,因为它可能永远不会停止变化).

从Starting开始,

f ? = ((1 :) . tail) ? = 1 : tail ?

我们看到⊥不是一个固定点,因为我们没有得到另一端的⊥.那么让我们再试一次我们得到的东西:

f (1 : tail ?) = ((1 :) . tail) (1 : tail ?)
               = 1 : tail (1 : tail ?)
               = 1 : tail ?

哦,看,这是一个固定的点,我们得到了同样的东西,我们投入.

这里重要的一点是,它是至少一个.您的解决方案[1,1] = 1:1:[]也是一个固定点,因此它解决了以下等式:

f (1:1:[]) = ((1 :) . tail) (1:1:[]) 
           = 1 : tail (1:1:[])
           = 1:1:[]

但是,当然,每个以1开头的列表都是一个解决方案,目前还不清楚我们应该如何在它们之间做出选择.但是,我们通过递归找到的那个1:?比它们所有的都定义得少,它提供的信息不是等式所要求的信息,而是由语言指定的信息.