在Haskell中检测循环列表的能力会破坏语言的任何属性吗?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (47)

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

ones = 1 : ones

另一些则不是:

nums = [1..]

还有这样的事情:

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

假设我们使用一个haskell实现,并对其进行内建函数的黑客攻击。isCycle :: [a] -> Bool的结构。内存表示争论的焦点。它返回True如果列表是物理循环的,并且False如果这个论点是有限长度的。否则,它将无法终止。

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

提问于
用户回答回答于

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

。Haskell表达式总是可以被其值替换。换句话说,它只取决于传递的参数,而不是其他任何东西。如果我们有

isCycle :: [a] -> Bool

正如所建议的,使用它的表达式将不再满足此属性。它们可以依赖于值的内部内存表示。因此,将违反其他法律。例如,Functor同一性法

fmap id === id

你可以区分onesfmap 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值。

用户回答回答于

Data.List

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

扫码关注云+社区

领取腾讯云代金券