何时使用类型类,何时使用类型

Question

几个月前,我正在重新审视我编写的用于组合搜索的一段代码,并注意到有一种替代的,更简单的方法可以做一些我之前用类型类实现的东西.

具体来说,我之前有一个搜索问题类型的类型类,它具有类型的状态,类型的s动作(状态操作)a,初始状态,获取(动作,状态)对列表的方式和测试状态是否为解决方案的方法:

class Problem p s a where
    initial   :: p s a -> s
    successor :: p s a -> s -> [(a,s)]
    goaltest  :: p s a -> s -> Bool

这有点令人不满意,因为它需要MultiParameterTypeClass扩展,并且当你想要创建这个类的实例时,通常需要FlexibleInstances和可能的TypeSynonymInstances.它还会使您的功能签名变得混乱,例如

pathToSolution :: Problem p => p s a -> [(a,s)]

我今天注意到我可以完全摆脱这个类,并使用类型代替,沿着以下几行

data Problem s a {
    initial   :: s,
    successor :: s -> [(a,s)],
    goaltest  :: s -> Bool
}

这不需要任何扩展,功能签名看起来更好:

pathToSolution :: Problem s a -> [(a,s)]

而且,最重要的是,我发现在重构我的代码以使用这个抽象而不是类型类之后,我留下了比以前少15-20%的行.

最大的胜利是在使用类型类创建抽象的代码中 - 以前我必须创建新的数据结构,以复杂的方式包装旧的数据结构,然后将它们变成Problem类的实例(需要更多的语言扩展) - 很多代码行做一些相对简单的事情.在重构之后,我只有几个功能完全符合我的要求.

我现在正在查看其余的代码,试图找出我可以用类型替换类型类的实例,并获得更多的胜利.

我的问题是:在什么情况下不将这个重构不工作？在什么情况下,实际上只使用类型类而不是数据类型更好,并且如何提前识别这些情况,这样您就不必经历昂贵的重构？

Answer 1

考虑一种情况,即类型和类都存在于同一程序中.类型可以是类的实例,但这相当简单.更有趣的是你可以编写一个函数fromProblemClass :: (CProblem p s a) => p s a -> TProblem s a.

您执行的重构大致相当于fromProblemClass在构建用作CProblem实例的内容的每个地方手动内联,并使接受CProblem实例的每个函数都接受TProblem.

由于这个重构的唯一有趣的部分是定义TProblem和实现fromProblemClass,如果你可以为任何其他类编写类似的类型和函数,你也可以重构它以完全消除类.

这什么时候有效？

想想实施fromProblemClass.您将基本上将类的每个函数部分应用于实例类型的值,并在此过程中消除对p参数的任何引用(类型替换的类型).

重构类型类很简单的任何情况都将遵循类似的模式.

什么时候适得其反？

想象一下Show只有show函数定义的简化版本.这允许相同的重构,应用show和替换每个实例... a String.很明显,我们在这里丢失了一些东西 - 即能够使用原始类型并将它们转换String为各种点.它的价值Show在于它在各种不相关的类型上定义.

根据经验,如果存在许多特定于类的实例的不同函数,并且这些函数通常在与类函数相同的代码中使用,则延迟转换是有用的.如果在单独处理类型的代码和使用该类的代码之间存在明显的分界线,则转换函数可能更适合于类型类,这是一种轻微的语法便利.如果几乎只通过类函数使用类型,则类型类可能完全是多余的.

这什么时候不可能？

顺便提一下,这里的重构类似于OO语言中的类和接口之间的差异; 同样,类型类,其中这个重构是不可能的是那些不能直接表示在所有在许多面向对象的语言.

更重要的是,有些事情你不能轻易地翻译,如果有的话,以这种方式:

• 类的类型参数仅出现在协变位置,例如函数的结果类型或非函数值.这里着名的罪犯是mempty为了Monoid和return为Monad.

• 在函数类型中出现多次的类的类型参数可能不会使这真的不可能,但它会使事情非常严重地复杂化.这里着名的违规者包括Eq,Ord基本上每个数字类.

• 不平凡的使用较高种,具体的哪个我不知道如何牵制,但(>>=)对于Monad这里的显着的罪犯.另一方面,p类中的参数不是问题.

• 非平凡地使用多参数类型,我也不确定如何确定如何在实践中变得非常复杂,与OO语言中的多个调度相当.同样,你的班级在这里没有问题.

请注意,鉴于上述情况,对于许多标准类型类,这种重构甚至都不可能,并且对于少数例外会适得其反.这不是巧合.:]

你应用这种重构放弃了什么？

您放弃了区分原始类型的能力.这听起来很明显,但它可能很重要 - 如果在任何情况下您确实需要控制使用哪个原始类实例类型,应用此重构会失去某种程度的类型安全性,您只能通过跳过在其他地方用于确保运行时不变量的同类箍.

相反,如果在某些情况下您确实需要使各种实例类型可以互换 - 您提到的复杂包装是这种情况的经典症状 - 您可以通过丢弃原始类型获得大量收益.通常情况下,您实际上并不关心原始数据本身,而是关于它如何让您对其他数据进行操作; 因此,直接使用函数记录比额外的间接层更自然.

如上所述,这与OOP及其最适合的问题类型密切相关,并且与ML风格语言中的典型代表表达问题的"另一面".

Answer 2

您的重构与Luke Palmer 撰写的博客文章密切相关:"Haskell Antipattern:Existential Typeclass".

我想我们可以证明你的重构将永远有效.为什么？直觉上,因为如果某些类型Foo包含足够的信息以便我们可以将它变成Problem类的实例,我们总是可以编写一个Foo -> Problem函数,将Foo相关信息"投射" 到Problem包含所需信息的函数中.

更正式一点,我们可以草拟一个证明你的重构总是有效的证明.首先,要设置阶段,以下代码将Problem类实例的转换定义为具体CanonicalProblem类型:

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}

class Problem p s a where
    initial   :: p s a -> s
    successor :: p s a -> s -> [(a,s)]
    goaltest  :: p s a -> s -> Bool

data CanonicalProblem s a = CanonicalProblem {
    initial'   :: s,
    successor' :: s -> [(a,s)],
    goaltest'  :: s -> Bool
}

instance Problem CanonicalProblem s a where
    initial = initial'
    successor = successor'
    goaltest = goaltest'

canonicalize :: Problem p s a => p s a -> CanonicalProblem s a
canonicalize p = CanonicalProblem {
    initial' = initial p,
    successor' = successor p,
    goaltest' = goaltest p
}

现在我们要证明以下内容:

1. 对于任何类型Foo,使得instance Problem Foo s a,可以写一个canonicalizeFoo :: Foo s a -> CanonicalProblem s a产生相同的结果的功能canonicalize时适用于任何Foo s a.
2. 可以将使用Problem该类的任何函数重写为使用的等效函数CanonicalProblem.例如,如果你有solve :: Problem p s a => p s a -> r,你可以写一个canonicalSolve :: CanonicalProblem s a -> r相当于的solve . canonicalize

我只是草拟样张.在(1)的情况下,假设您有一个Foo具有此Problem实例的类型:

instance Problem Foo s a where
    initial = initialFoo
    successor = successorFoo
    goaltest = goaltestFoo

然后给x :: Foo s a你通过替换可以简单地证明以下内容:

-- definition of canonicalize
canonicalize :: Problem p s a => p s a -> CanonicalProblem s a
canonicalize x = CanonicalProblem {
                     initial' = initial x,
                     successor' = successor x,
                     goaltest' = goaltest x
                 }

-- specialize to the Problem instance for Foo s a
canonicalize :: Foo s a -> CanonicalProblem s a
canonicalize x = CanonicalProblem {
                     initial' = initialFoo x,
                     successor' = successorFoo x,
                     goaltest' = goaltestFoo x
                 }

后者可以直接用于定义我们所需的canonicalizeFoo功能.

在(2)的情况下,对于任何函数solve :: Problem p s a => p s a -> r(或涉及Problem约束的类似类型),以及任何类型Foo,以便instance Problem Foo s a:

• 定义canonicalSolve :: CanonicalProblem s a -> r'采取的定义solve而代中出现的所有Problem方法与他们的CanonicalProblem实例定义.
• 证明对任何x :: Foo s a,solve x相当于canonicalSolve (canonicalize x).

(2)的具体证据要求具体定义solve或相关功能.一般证明可以采用以下两种方式之一:

• 对具有Problem p s a约束的所有类型的归纳.
• 证明所有Problem函数都可以根据函数的一小部分来编写,证明该子集具有CanonicalProblem等价物,并且将它们一起使用的各种方法保留了等价.