Haskell可以通过类型类的模式匹配实现多重分派？ [英] Can multiple dispatch be achieved in Haskell with pattern matching on type classes?

问题描述

这是一个关于Haskell中多次发送的问题。

下面我使用术语compliant to [type class]来表示具有[type class]的实例的类型，因为类型类通常就像接口一样，所以直观地想到一个具体的东西就像一个实际的Int值，由于它的类型实现了属于那个接口/类型类所需的任何类型，所以它是符合到接口/类型类的。

考虑一个想要创建一个单指数函数的例子，无论它是用浮动参数调用， Num ， Integral 或其他类型，它通过使用由参数类型实现的类型类来工作，以选择预先存在的指数函数来调用。

$ b

函数（^）的类型为（^）::（Integral b，Num a）= > a - > b - >一个和函数（**）的类型为（**）:: Floating a => a - > a - >一个。

假设我想创建一个函数 my_pow ，它接受一个 Num 符合的第一个参数和一个 Num 符合的第二个参数。

如果两个参数都符合 Floating ，那么它会调用（**）;如果第二个参数仅仅是 Integral 兼容，它会调用（^）;并且任何其他的情况都会给出一个模式匹配错误。

我天真的第一次尝试是将类型类视为值构造函数，并尝试在函数定义中模式匹配： / p>

  my_pow ::（数字a，数字b）=> a  - > b  - > a 
 my_pow（Floating x）（Floating y）= x ** y 
 my_pow x（Integral y）= x ^ y 
  

，但这会给出错误：

  tmp.hs：25：6：不在范围内：数据构造函数`浮动'
 
 tmp.hs：25：19：不在范围内：数据构造函数`浮动'
 
 tmp.hs：26：8：不在范围内：数据构造函数`Integral'
  

可能意味着我不能将类型类视为值构造函数，这并不令人意外。

但是，如果在函数中与特定类型约束更具体的参数的特定类型类属性进行模式匹配定义没有得到任何明确的答案。

使这种多态的首选方式是什么 - 实际上是一个调度模式，其中函数总体上放宽了类型类的约束，但是之后通过模式匹配来定义a的更具体的类型约束在这种情况下，它会派发给其他函数。

解决方案

你所描述的是类型类实例。使用具体的类型，使用 MultiParamTypeClasses ;这是Haskell如何实现多次调度。

  { - ＃LANGUAGE MultiParamTypeClasses，FlexibleInstances，OverlappingInstances＃ - } 
模块SO26303353其中
 
 class（Num a，Num b）=>给b加电
 my_pow :: a  - > b  - > a 
 
实例Power Double Double其中
 my_pow =（**）
 
实例Num a =>发送一个整数，其中
 my_pow =（^）
  

这很好。除了（**）和（^）是不同的操作并且有些人可能会或多或少地使用Haskell反对模糊的区别。

然而，你要求更精细些的东西。您不仅希望在类型上发布多个分发，而且要在类的类上发布多个分发。这是一个非常不同而且更强大的事情。特别是，它适用于所有 类型，它们可能具有 Floating 或 Intergral ，甚至还没有写入的类型！以下是它的理想写法：

  instance（Floating a）=> Power a a其中
 my_pow =（**）
 
实例（数字a，积分b）=> Power ab其中
 my_pow =（^）
  

这不起作用，因为约束求解器不会回溯，并且在选择实例时不考虑实例约束。因此 my_pow 不起作用，例如，两个 Int s：

  ghci> ：t my_pow :: Int  - > Int  - > Int 
（Floating Int）没有实例
  

发生这种情况是因为更具体 code> Power aa 实例匹配，因为这两个类型是相等的。然后，GHC在 a 和之间施加 Floating 约束，当它不能满足它时。它不会然后回溯并尝试 Power ab 实例。

它可能会也可能不会破解使用高级类型系统功能的限制，但我不认为你可以为（**）和（ ^）在当前Haskell中。

编辑：常规注释

我们有点偏离Q& A格式。）

在重读您的问题和评论时，我注意到您使用的术语dispatch在一种我不熟悉的方式。 Google快速发布了有关双重调度和访客设计模式。那是你从哪里来的？它们看起来有点像你想要做的 - 写一个函数，根据它的参数类型完成不同的事情。我想添加一些东西给这个答案，这可能有助于磨练你的习惯Haskell的感觉。 （或者可能只是不连贯的散乱。）

Haskell通常忽略运行时类型的想法。即使在@Cirdec更详尽的答案中，在编译时，所有类型都是静态的。 （使用REPL， ghci ）不会改变任何事情，只是编译时会变得很模糊。）事实上，关于运行时发生的直觉是通常在Haskell中与其他语言不同，这不仅仅是因为GHC执行激进的优化。

习惯性Haskell建立在参数多态性;像 replicate :: Int - >这样的函数。 a - >对于任何类型 a ，[a] 的作用完全相同。因此，我们知道很多关于 replicate 的内容，而无需查看它的实现。这种态度真的很有用，它深深地感染了Haskell程序员的大脑。你会注意到，我和其他许多Haskell程序员对类型注释疯狂，特别是在像这样的论坛中。静态类型非常有意义。 （关键字：free theorems。）（这与您的问题并不直接相关）。
$ b Haskell使用类型类来允许 ad hoc多态性。在我看来，'ad hoc'是指一个函数的实现可能因不同类型而不同。这对数字类型来说当然是至关重要的，并且多年来以无数方式应用。但重要的是要明白，即使使用类型类，所有内容仍然是静态类型的。要真正评估任何类型函数 - 从中​​获取一个值 - 最终需要选择一个特定的类型。 （对于数字类型，默认规则会经常为您选择它。）当然，您可以组合事物来生成另一个多态函数（或值）。

从历史上看，类型类被认为是严格地作为函数重载的一种机制，在几个不同的函数具有相同的名称的意义上。换句话说，而不是 addInt :: Int - > Int - > Int ， addFloat :: Float - >浮动 - > Float ，我们有一个名字：（+）:: Num a => a - > a - >一个。但它仍然有一个基本相同的概念：有一堆完全不同的函数，称为（+）。 （现在我们倾向于按照法则来谈论类型类，但这是一个不同的主题。）有时，像（+），甚至是非原始函数。

是的，类型类有点像界面，但不允许OOP思维模式陷入太远。如果您正在编写一个类型为 Num a =>的函数， a - >一个，期望的是你知道 a 的 only 是它是<$ c的一个实例$ C>货号。你不能像幕布一样往后看。 （没有作弊，这很难）。处理 a 类型值的唯一方法是使用完全多态函数，并使用其他 Num 函数。尤其是，您不能确定 a 是否也是其他类的实例。

各种编译器我们一直在使用的扩展模糊了这个模型，因为我们现在可以编写类型的级别函数。但不要将它与动态分派混淆。

哦，顺便说一下，Haskell支持动态类型。请参阅 Data.Dymamic 。说实话，除了与其他语言交互之外，我从来没有真正看到过它的用处。 （我愿意做错）。典型的访问者模式问题可以通过其他方式实现。

This is a question about multiple dispatch in Haskell.

Below I use the term "compliant to [type class]" to mean "has type which is instance of [type class]", because type classes are often like interfaces, so it's intuitive to think of a concrete thing like an actual Int value as being "compliant" to an interface/type class by virtue of its type implementing whatever is needed to belong to that interface/type class.

Consider the example of wanting to make a single exponentiation function that will work whether it is called with Floating arguments, Num, Integral or whatever, and it works by using the type classes that are implemented by the types of the arguments to select a pre-existing exponentiation function to call.

The function (^) has type (^) :: (Integral b, Num a) => a -> b -> a and the function (**) has type (**) :: Floating a => a -> a -> a.

Suppose I want to create a function my_pow that accepts a Num compliant first argument and a Num compliant second argument.

If both arguments are Floating compliant, then it will call (**); if the second argument is merely Integral compliant, it will call (^); and any other case will give a pattern matching error.

My naive first try was to treat the type classes like value constructors and try to pattern match within the function definition:

my_pow :: (Num a, Num b) => a -> b -> a
my_pow (Floating x) (Floating y) = x ** y
my_pow x (Integral y) = x ^ y 

but this gives the errors:

tmp.hs:25:6: Not in scope: data constructor `Floating'

tmp.hs:25:19: Not in scope: data constructor `Floating'

tmp.hs:26:8: Not in scope: data constructor `Integral'

probably meaning that I cannot treat type classes as value constructors, which is not surprising.

But then Googling around for how to pattern-match against particular type class properties of the arguments that are more specific than the type class constraints in the function definition did not yield any clear answers.

What is the preferred way to make this sort of polymorphism -- effectively a dispatch pattern where the function has relaxed type class constraints overall, but then is defined by pattern matching on more specific type class constraints for any of the cases it will dispatch to other other functions.

解决方案

The normal way to "pattern match" on types in the way you're describing is with type class instances. With concrete types, this is easy using MultiParamTypeClasses; this is how Haskell implements multiple dispatch.

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, OverlappingInstances #-}
module SO26303353 where

class (Num a, Num b) => Power a b where
  my_pow :: a -> b -> a

instance Power Double Double where
  my_pow = (**)

instance Num a => Power a Integer where
  my_pow = (^)

This works just fine. It's more or less idiomatic Haskell, except that (**) and (^) are different operations and some people might object to blurring the distinction.

You're asking for something a bit more elaborate, however. You want multiple dispatch not only on types but on classes of types. This is a significantly different and more powerful thing. In particular, it would work for all types that could have instances of Floating or Intergral, even types that haven't been written yet! Here's how it would be written ideally:

instance (Floating a) => Power a a where
  my_pow = (**)

instance (Num a, Integral b) => Power a b where
  my_pow = (^)

This doesn't work, though, because the constraint solver does not backtrack, and does not consider instance constraints when choosing an instance. So my_pow doesn't work, for instance, with two Ints:

ghci> :t my_pow :: Int -> Int -> Int
No instance for (Floating Int)

This happens because the "more specific" Power a a instance matches, because the two types are equal. GHC then imposes the Floating constraint on a, and barfs when it can't satisfy it. It does not then backtrack and try the Power a b instance.

It may or may not be possible to hack around the limitation using advanced type system features, but I don't think you could ever make a drop-in replacement for both (**) and (^) in current Haskell.

Edit: general comments

(Note that we're kind of straying away from a Q&A format here.)

In rereading your question and comment, I notice you're using the term "dispatch" in a way I'm not familiar with. A quick Google turns up articles on double dispatch and the visitor design pattern. Is that where you're coming from? They look a bit like what you're trying to do--write a function that does totally different things based on the types of its arguments. I want to add a few things to this answer that may help hone your sense of idiomatic Haskell. (Or may just be disjointed rambling.)

Haskell normally disregards the idea of a "runtime type". Even in @Cirdec's more elaborate answer, all the types are statically known, "at compile time." (Using the REPL, ghci, doesn't change things, except that "compile time" gets kind of hazy.) In fact, intuitions about what happen "at runtime" are often different in Haskell than other languages, not least because GHC performs aggressive optimizations.

Idiomatic Haskell is built on a foundation of parametric polymorphism; a function like replicate :: Int -> a -> [a] works absolutely the same for any type a. As a result, we know a lot about what replicate does without having to look at its implementation. This attitude is really helpful, and it deeply infects the brains of Haskell programmers. You'll notice that me and many other Haskell programmers go crazy with type annotations, especially in a forum like this one. The static types are very meaningful. (Keyword: free theorems.) (This isn't immediately relevant to your question.)

Haskell uses type classes to permit ad hoc polymorphism. In my mind, 'ad hoc' refers to the fact that the implementation of a function may be different for different types. This is of course critical for numerical types, and has been applied over the years in countless ways. But it's important to understand that everything is still statically typed, even with type classes. To actually evaluate any type-class function--to get a value out of it--you need to in the end choose a specific type. (With numeric types, the defaulting rules frequently choose it for you.) You can of course combine things to produce another polymorphic function (or value).

Historically, type classes were thought of strictly as a mechanism for function overloading, in the sense of having the same name for several distinct functions. In other words, rather than addInt :: Int -> Int -> Int, addFloat :: Float -> Float -> Float, we have one name: (+) :: Num a => a -> a -> a. But it's still fundamentally the same idea: there are a bunch of completely different functions called (+). (Now we tend to talk about type classes in terms of "laws," but that's a different topic.) There's oftentimes no literal dispatch occurring with a function like (+), or even non-primitive functions.

Yes, type classes are a bit like interfaces, but don't allow an OOP mindset to creep in too far. If you are writing a function with a type like Num a => a -> a, the expectation is that the only thing you know about a is that it is an instance of Num. You can't look behind the curtain, as it were. (Without cheating. Which is hard.) The only way to manipulate values of type a is with fully polymorphic functions and with other Num functions. In particular, you can't determine whether a is also an instance of some other class.

The various compiler extensions we've been playing with blur this model a bit, because we now can write, essentially, type level functions. But don't confuse that with dynamic dispatch.

Oh, by the way, Haskell does support dynamic types. See Data.Dymamic. To be honest, I've never really seen much use for it outside of interop with other languages. (I'm willing to be wrong.) The typical "visitor pattern" problems can be implemented in other ways.

这篇关于Haskell可以通过类型类的模式匹配实现多重分派？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！