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

Question

在Haskell中，一些列表是循环的：

ones = 1 : ones

其他不是：

nums = [1..]

然后是这样的：

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

这表示与ones相同的值，并且该值当然是一个重复序列。但它是否在内存中表示为循环数据结构值得怀疑。（实现可以这样做，但是 this answer explains that "it's unlikely that this will happen in practice"。）

假设我们采用 Haskell 实现，并在其中侵入一个内置函数 isCycle :: [a] -> Bool，该函数检查 内存表示 的结构论据。它 returns True 如果列表是物理循环的并且 False 如果参数是有限长度的。否则，它将无法终止。（我想象 "hacking it in" 因为不可能在 Haskell 中编写该函数。）

这个函数的存在会破坏语言的任何有趣的特性吗？

Answer 1

在一般情况下，不，您无法识别循环列表。但是，如果列表是由展开操作生成的，则可以。 Data.List 包含这个：

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

第一个参数是一个函数，它接受类型为 "b" 的 "state" 参数，并且可以 return 列表的一个元素和一个新状态。第二个参数是初始状态。 "Nothing"表示列表结束。

如果状态再次出现，则列表将从最后一个状态的点开始重复。因此，如果我们改为使用不同的展开函数，即 return 是 (a, b) 对的列表，我们可以检查与每个元素对应的状态。如果相同的状态出现两次，则该列表是循环的。当然，这假设状态是 Eq 或其他东西的实例。

Answer 2

Would the existence of this function break any interesting properties of the language?

是的会的。它会破坏 referential transparency (see also the Wikipedia article)。 Haskell 表达式总是可以被它的值替换。换句话说，它仅取决于传递的参数，而不依赖于其他任何东西。如果我们有

isCycle :: [a] -> Bool

如您所建议，使用它的表达式将不再满足此属性。它们可能依赖于值的内部存储器表示。结果，将违反其他法律。例如 identity law for 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 个值的知识。

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

Would the ability to detect cyclic lists in Haskell break any properties of the language?

haskell

cycle

infinite