在Haskell中检测循环列表的能力会破坏该语言的任何属性吗？
在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来检查参数在内存中表示的结构。如果列表是物理循环的，则返回True；如果参数的长度有限，则返回False。否则，它将无法终止。(我想象“that in”，因为不可能用Haskell编写该函数。)
此函数的存在会破坏语言的任何有趣属性吗？
回答 2
Stack Overflow用户
发布于 2015-05-17 00:46:04
这个函数的存在会破坏语言的任何有趣的属性吗？
是的，会的。它会破坏referential transparency (另请参阅the Wikipedia article)。Haskell表达式总是可以用它的值替换。换句话说，它只依赖于传递的参数，而不依赖于其他参数。如果我们有
isCycle :: [a] -> Bool正如您所建议的，使用它的表达式将不再满足此属性。它们可以依赖于值的内部存储器表示。因此，其他法律将被违反。例如，Functor的identity law
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值的知识。
Stack Overflow用户
发布于 2015-05-16 23:30:44
在一般情况下，不能识别循环列表。但是，如果列表是由展开操作生成的，那么您可以。Data.List包含以下内容：
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]第一个参数是一个函数，它接受类型为"b“的" state”参数，并且可以返回列表中的一个元素和一个新状态。第二个参数是初始状态。"Nothing“表示列表结束。
如果该状态再次出现，则该列表将从上一个状态的点开始重复。因此，如果我们使用返回(a，b)对列表的不同展开函数，我们可以检查对应于每个元素的状态。如果相同的状态出现两次，则该列表是循环的。当然，这假设状态是Eq的实例或其他东西。
https://stackoverflow.com/questions/30272662
复制相似问题