Scala和Haskell中的“组合”代数数据类型

Question

在试图用Scala中的代数数据类型描述Sql的一部分时，我需要创建根trait的子trait来表示数据类型。由于遇到这个要求会产生一些代码，我不确定能否使用Haskell的ADT来表示，并且与Haskell不同，ADT不是Scala的本地构造，所以我现在想知道：

1. 我是否正确认为在Haskell中无法表示模型，例如类型Sql具有“子类型”Statement并具有构造函数Select ? （这似乎可能与这个相关）。
2. 如果如此，术语“ADT”适用于我生成的代码吗？
3. 如果是这样，这是否使Scala在这方面实际上比Haskell更强大？
4. 如果不是这样，为什么Haskell没有实现这个功能？这让我觉得我可能在我的模型中过于复杂了。

这是我谈论的模型：

sealed trait Sql


sealed trait Statement 
  extends Sql

sealed case class Union 
  ( left : Statement, 
    right : Statement ) 
  extends Statement

sealed case class Select
  ( /** other fields don't matter **/
    where : Where )
  extends Statement


sealed trait Where 
  extends Sql

sealed case class And
  ( left : Where,
    right : Where )
  extends Where

sealed case class Or
  ( left : Where,
    right : Where )
  extends Where

sealed case class Equals
  ( /** fields don't matter **/ )
  extends Where

- Nikita Volkov

---

提醒不熟悉术语的读者：本问题中的ADT仅指代数数据类型，而不是抽象数据类型。 - Jörg W Mittag

@JörgWMittag：这在第一句中提到了。 - Niklas B.

是的，我知道。但绝大多数程序员可能从未听说过代数数据类型，因此他们可能不习惯将缩写ADT用于它，而不是用于抽象数据类型。 - Jörg W Mittag

既然案例类无法被扩展，那么将它们标记为“sealed”的价值是什么？ - Erik Kaplun

@ErikAllik 它们可以通过标准类进行扩展。例如，case class A (a: Int); class B (b: Int) extends A(2) - Nikita Volkov

Answer 1

1. 不，因为您的根特质是密封的，所以可以将所呈现的层次结构表示为 ADT：

data Sql = Statement Statement | Where Where
        --           ^ This is the *type* called `Statement`
        -- ^ This is the *constructor* called `Statement`

data Statement = Union Statement Statement | Select Where

data Where = And Where Where | Or Where Where | Equals

在这种情况下是可能的，因为你能够枚举所有你数据类型（在这个案例中是Sql）的“子类”，这使得将它们转换为ADT构造函数成为可能。如果想让用户任意添加“构造函数”/“子类”，那么模拟类型层次结构作为ADT就会变得困难。

2. Scala语言中永远不会用到ADT这个术语，因为Scala缺少语言中的ADTs。然而，你提供的类的行为与ADT类似，所以我认为“差不多够了”。

3 & 4. 这些语言有不同的优势和劣势。

Haskell可以模拟Scala语言的每一个特性，Scala也可以模拟Haskell的每一个特性，因为两种语言都是图灵完备的，并允许不同级别的元编程。当然，Haskell具有Template Haskell，可以用来模拟任何东西--你甚至可以使用TH来能够在Haskell文件中编写Scala代码，并将其编译为Haskell。

在Haskell中不需要对象和继承，而在Scala中大多数情况下也不需要ADT，因此没有比较它们的理由。大多数面向对象的特征也可以通过简单的Haskell类型类和数据类型以及使用模块边界来模拟，而Scala可以使用case类来模拟ADT，并且可以使用隐式参数和隐式对象实例来模拟Haskell类型类。

然而，我认为通常更容易在Haskell中模拟某些Scala的特性，因为Haskell允许比Scala更多的“隐式语言扩展”。我的意思是，如果你想在Scala中模拟Haskell的Monad，你必须在使用Monad的部分写入大量代码，而如果你想在Haskell中模拟Scala的限定续体或隐式参数，你只需编写一个Monad实例（用于续体）或一个多参数类型类（用于隐式参数）一次即可，后来在实际函数中编写的代码看起来非常接近Scala代码，几乎没有重复的代码。Scala的许多高级功能也源自Haskell或OCaml，因此它们已经存在，不需要进行转换。

换句话说：为了添加新功能所需的复杂代码只需在Haskell中的一个位置进行添加，之后它可以在多个地方非常容易地使用，而如果要模仿Haskell功能，则通常需要在Scala代码的各个地方添加许多“噪音”。

- dflemstr

---

哦！所以，使用“选择等于”可以得到一个Sql类型的“等于”值，对吧？我的思维太过于专注于继承，没想到这点。谢谢！非常好的回答！ - Nikita Volkov

@Nikita，只需要“等于”。 - Heatsink

看起来你的模型并不完全匹配，因为它翻译回Scala将会有所不同。以下是你的模型中Statement类型与Sql类型之间关系在Scala中的翻译：sealed trait Sql; case class StatementSql(s: Statement); sealed trait Statement。我倾向于得出这样的结论：我在问题中提出的模型在Haskell中确实没有直接对应物，因此并不完全符合Scala的ADT模式。 - Nikita Volkov

不，它与Scala版本匹配，因为它们具有相同的语义。这就像说“1 + 2”和“3”之间有区别一样。是的，你可以看到有区别，但它们在语义上是相同和同构的。即使你所说的是正确的，它也意味着Scala版本没有“在Haskell中实现ADT模式”，因为Scala中没有ADT的概念 :) - dflemstr

在Scala中没有ADT构造，但有一种模式。我的意思是，尽管我的模型可以被视为ADT，正如我们已经确定的那样，但它可能并不完全遵循这种模式。如果您回答，请在前面加上我的名字，否则我将不会收到通知。 - Nikita Volkov

@NikitaVolkov，是的，您当然是正确的，但是“该模型...不完全符合Scala的ADT模式”这个说法对我来说仍然没有意义。即使它本身不是ADT，它也以100％的方式表示有效的ADT仿真，并具有与Haskell版本的1：1映射。 - dflemstr

Answer 2

您可以在Haskell中模仿Scala的设计，尽管Haskell鼓励使用限定类型和和并类型来替代Scala的继承和子类型。 以下是我根据有限的Scala知识在Haskell中编写的相同内容。

• Traits是类
• Case classes是代数数据类型
• Trait继承是类成员
• Trait类型的成员是有界存在类型
• Class Typeable 用于向下转型

-- Define traits
class Typeable a => Sql a
class (Typeable a, Sql a) => Statement a
class (Typeable a, Sql a) => Where a

-- Define case classes
data Union  where Union     :: (Statement a, Statement b) => a -> b -> Union deriving (Typeable)
data Select where Select    :: Where a => a -> Select                        deriving (Typeable)          

data And    where And       :: (Where a, Where b) => a -> b -> And           deriving (Typeable)
data Or     where Or        :: (Where a, Where b) => a -> b -> Or            deriving (Typeable)
data Equals where Equals    :: Equals                                        deriving (Typeable)

-- Define subtyping
instance Sql Union
instance Statement Union
instance Sql Select
instance Statement Select
instance Sql And
instance Where And
instance Sql Or
instance Where Or
instance Sql Equals
instance Where Equals

在Haskell中，您可能会使用和Statement和Where类不同的和类型。

class Sql a
instance Sql Statement
instance Sql Where

data Statement = Union Statement Statement | Select Where
data Where = And Where Where | Or Where Where | Equals

- Heatsink

---

澄清一下：这是将Haskell ADT翻译为Scala，再将Scala表示法翻译回Haskell。这可能会让任何人的大脑感到疼痛，但它当然能够工作！ - dflemstr

请注意，此版本允许在类定义后向类添加其他特征。我不是指“new And(...) with Statement”这种情况，而是您可以添加一个特征，以便每个 And 实例之后都具有该特征。据我所知，Scala 特征无法实现这一点。 - dflemstr

Answer 3

可能的第四个问题答案：

Haskell的类型推断（Hindley-Milner）在存在继承时会出现问题，因此Scala具有继承但类型推断能力较弱。

- jhegedus