在Haskell中检测循环列表的能力是否会破坏该语言的任何属性？

Question

在Haskell中,一些列表是循环的:

ones = 1 : ones

其他人则不是:

nums = [1..]

然后有这样的事情:

more_ones = f 1 where f x = x : f x

这表示与该值相同的值ones,当然该值是重复序列.但它是否在内存中表示为循环数据结构是值得怀疑的.(一个实现可以这样做,但这个答案解释说"这不太可能在实践中发生".)

假设我们采用Haskell实现并在其中入侵一个内置函数isCycle :: [a] -> Bool,该函数检查参数的内存中表示的结构.True如果列表是物理循环的并且False参数的长度是有限的,则返回.否则,它将无法终止.(我想"在黑客入侵"因为在Haskell中编写该函数是不可能的.)

这个函数的存在是否会打破语言的任何有趣属性？

Answer 1

这个函数的存在是否会打破语言的任何有趣属性？

是的,它会的.它会破坏引用透明度(另见维基百科文章).Haskell表达式总是可以用其值替换.换句话说,它只取决于传递的参数而不是其他任何东西.如果我们有

isCycle :: [a] -> Bool

正如你所建议的那样,使用它的表达式将不再满足这个属性.它们可能依赖于值的内部存储器表示.因此,其他法律将受到侵犯.例如,身份法的Functor

fmap id === id

不会再这样了:你能够区分ones和fmap id ones,因为后者是非循环的.并且诸如应用上述定律的编译器优化将不再保留程序属性.

然而另一个问题是具有功能

isCycleIO :: [a] -> IO Bool

因为IO行动可以检查和改变任何事情.

一个纯粹的解决方案可能是拥有一个内部区分这两者的数据类型:

import qualified Data.Foldable as F

data SmartList a = Cyclic [a] | Acyclic [a]

instance Functor SmartList where
    fmap f (Cyclic xs) = Cyclic (map f xs)
    fmap f (Acyclic xs) = Acyclic (map f xs)

instance F.Foldable SmartList where
    foldr f z (Acyclic xs) = F.foldr f z xs
    foldr f _ (Cyclic xs) = let r = F.foldr f r xs in r

当然,它无法识别通用列表是否是循环的,但对于许多操作,可以保留具有Cyclic值的知识.