2012-10-02 49 views
51

Haskell具有一个名为seq的神奇函数,该函数接受任意类型的参数并将其减小为弱磁头标准形式(WHNF)。为什么seq不好?

我读过几个消息来源[不是我能记得他们是谁现在 ...],它声称“polymorphic seq是坏的”。他们以什么方式“不好”?

类似地,存在rnf函数,该函数将参数减少为正常形式(NF)。但是这个是一个类的方法;它不适用于任意类型。对我来说,似乎“显而易见”的是,可以改变语言规范以将其作为内置原语提供,类似于seq。据推测,这可能比仅有seq“更糟糕”。这是怎样的?

最后,有人建议给seqrnfpar和同类者相同类型的id功能,而不是const功能,因为它是现在,会是一个进步。怎么会这样?

+22

的'seq'函数不是拉姆达可定义(I.R.,不能在λ-演算来定义),这意味着所有的从演算结果可以当我们有'seq'不再值得信任。 – augustss

回答

49

据我知道的多态seq功能是不好的,因为它削弱了免费的定理或者,换句话说,一些等式是有效的,而不seq没有与seq不再有效。例如,平等

map g (f xs) = f (map g xs) 

适用于所有功能g :: tau -> tau',所有列表xs :: [tau]和所有的多态函数f :: [a] -> [a]。基本上,这种平等说明f只能对其参数列表的元素重新排序,或者放弃或重复元素,但不能创造新的元素。

说实话,它可以发明元素,因为它可以将非终止计算/运行时错误“插入”到列表中,因为错误类型是多态的。也就是说,在没有seq的Haskell这种编程语言中,这种平等已经被打破了。下面的函数定义为这个方程提供了一个反例。基本上,在左侧g“隐藏”错误。

g _ = True 
f _ = [undefined] 

为了固定该方程中,g必须是严格的,也就是,它有一个错误映射到一个错误。在这种情况下,平等再次成立。

如果添加多态性seq运算符,则等式再次中断,例如,以下实例化就是一个反例。

g True = True 
f (x:y:_) = [seq x y] 

如果我们考虑的名单xs = [False, True],我们有

map g (f [False, True]) = map g [True] = [True] 

,但是,从另一方面

f (map g [False, True]) = f [undefined, True] = [undefined] 

也就是说,你可以使用seq做出了一定的元素列表的位置取决于列表中另一个元素的定义。如果g是总数,则等式再次成立。如果您在免费定理intereseted检查了free theorem generator,它允许你指定你是否考虑与错误,甚至有seq语言的语言。虽然,这似乎是不太实际意义,seq打破了用于提高的功能程序性能自动,例如,foldr/build融合的seq存在失败一些转换。如果在seq的存在范围内对有关自由定理的更多细节进行了细分,请查看Free Theorems in the Presence of seq

据我知道它已经知道,一个多态seq休息一定的转换,当它被添加到语言。但是,别名也有缺点。如果您添加基于seq一个类型的类,你可能需要很多类型的类约束添加到您的程序,如果你添加一个seq某处深跌。此外,它没有被省略seq因为它已经知道有内存泄露,可以使用seq固定选择。

最后,我可能会错过某些东西,但我看不到类型的seq运算符是如何工作的。 seq的线索是,如果另一个表达式评估为标准形式,则它将评估表达式以标准形式。如果seq的类型为a -> a,则无法使一个表达式的评估取决于另一个表达式的评估。

+0

'图g(F XS)= F(图g XS)'呃...即使在没有'undefined'或'seq'共语言不成立。 'f = map(1:)''g =(2:)''xs = [[3],[4]]'根本不涉及任何幻想,但它确实打破了这种平等。我是否错过了一些非常明显的东西,或者基本上这个答案有很大的缺陷? – semicolon

+0

@semicolon该定理采用了关于多态的'f',它不能发明新的元素,因为它不知道它在操作什么类型。你的'f'至少需要一个'Num'约束,它不能是'[a] - > [a]'。 – Ben

+0

@Ben啊好吧,我的坏,这是有道理的。 – semicolon

8

另一个反例在this answer中给出 - 单子不能满足单子法则与sequndefined。而且由于undefined在图灵完备语言中是不可避免的,所以责怪的是seq