在Haskell中检测循环列表的能力是否会破坏该语言的任何属性？ [英] Would the ability to detect cyclic lists in Haskell break any properties of the language?

问题描述

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

  ones = 1：ones 
  
 
 
其他不是： 
 
 
  nums = [ 1 ..] 
  
然后有这样的事情：
  more_ones = f 1其中fx = x：fx 
  
这表示与 ones 相同的值，并且肯定该值是重复序列。但是否将它作为循环数据结构在内存中表现出来是值得怀疑的。 （一个实现可以这样做，但这个答案解释说这不太可能在实际中发生） p> 
 
 
假设我们接受一个Haskell实现，并将其嵌入到一个内置函数 isCycle :: [a]  - > Bool ，它检查参数的内存中表示的结构。如果列表是物理循环的，它返回 True ，如果参数是有限长度的，则返回 False 。否则，它将无法终止。 （我猜想黑客入侵是因为在Haskell中编写该函数是不可能的。）
 
 
 该函数的存在是否会打破语言的任何有趣属性？
 
解决方案
 
 
 
这个函数的存在是否会打破语言的任何有趣属性？ 
 
 是的。它会破坏参照透明度（另请参阅维基百科文章）。 Haskell表达式总是可以用它的值来代替。换句话说，它仅取决于传递的参数，而不取决于其他。如果我们有
 
 
  isCycle :: [a]  - > Bool 
  
正如你所建议的那样，使用它的表达式不会再满足这个属性。他们可能依赖于内部存储器对值的表示。其结果是，其他法律将受到侵犯。例如，身份法   Functor    
 
 
  fmap id === id 
  
不会再存在：你可以区分 ones 和 fmap id ones ，因为后者是非循环的。编译器优化，比如应用上面的法则不会再保留程序的属性。
 
 
 
然而，另一个问题是有功能
  isCycleIO :: [a]  - > IO Bool 
  
作为 IO 动作允许检查和改变任何东西。
 
 
 
纯粹的解决方案可能是让数据类型在内部区分这两种： 
 
 
 将限定的Data.Foldable导入为F 
 
 data SmartList a =循环[a] | acyclic [a] 
 
实例Functor SmartList其中
 fmap f（循环xs）=循环（映射f xs）
 fmap f（非循环xs）=非循环（映射f xs） 
 
实例F.Foldable SmartList其中
 foldr fz（Acyclic xs）= F.foldr fz xs 
 foldr f _（Cyclic xs）= let r = F.foldr fr xs在r 
  
当然，它不能识别泛型列表是否循环，但是对于许多操作，可以保留 Cyclic 值的知识。
 
In Haskell, some lists are cyclic:
ones = 1 : ones
Others are not:
nums = [1..]
And then there are things like this:
more_ones = f 1 where f x = x : f x
This denotes the same value as ones, and certainly that value is a repeating sequence. But whether it's represented in memory as a cyclic data structure is doubtful. (An implementation could do so, but this answer explains that "it's unlikely that this will happen in practice".)

Suppose we take a Haskell implementation and hack into it a built-in function isCycle :: [a] -> Bool that examines the structure of the in-memory representation of the argument. It returns True if the list is physically cyclic and False if the argument is of finite length. Otherwise, it will fail to terminate. (I imagine "hacking it in" because it's impossible to write that function in Haskell.)

Would the existence of this function break any interesting properties of the language?
解决方案

  
Would the existence of this function break any interesting properties of the language?
Yes it would. It would break referential transparency (see also the Wikipedia article). A Haskell expression can be always replaced by its value. In other words, it depends only on the passed arguments and nothing else. If we had
isCycle :: [a] -> Bool
as you propose, expressions using it would not satisfy this property any more. They could depend on the internal memory representation of values. In consequence, other laws would be violated. For example the identity law for Functor
fmap id === id
would not hold any more: You'd be able to distinguish between ones and fmap id ones, as the latter would be acyclic. And compiler optimizations such as applying the above law would not longer preserve program properties.

However another question would be having function
isCycleIO :: [a] -> IO Bool
as IO actions are allowed to examine and change anything.

A pure solution could be to have a data type that internally distinguishes the two:
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
Of course it wouldn't be able to recognize if a generic list is cyclic or not, but for many operations it'd be possible to preserve the knowledge of having Cyclic values.

                        
这篇关于在Haskell中检测循环列表的能力是否会破坏该语言的任何属性？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！