参数多态是否与arity上的调度相同？

Question

如果参数多态在不依赖于参数类型的情况下进行调度,那么除了arity之外还有什么可以调度？如果不一样,有人可以提供反例吗？

Answer 1

参数多态性

参数多态性背后的想法是你不调度 - 参数化多态函数是一种对所有输入类型都以相同方式运行的函数.让我们考虑一个非常简单的例子(我将使用Haskell ¹):

id x = x

这定义了一个名为的函数id,它接受一个参数x,然后返回它.这是id实体函数; 它没有做任何事情.现在,应该id有什么类型？它绝对是一个函数,因此它将具有某些类型和.我们可以说有类型; 然后会评估,但不会进行类型检查,这似乎很愚蠢.说不是更好; 问题是逆转的.我们知道,对,它并不重要的输入是什么类型; 忽略那个结构,只是传递价值.所以对于任何类型,都有类型,我们可以明确地写出来:input -> outputinputoutputidInt -> Intid 33id Trueid :: Bool -> Boolididaida -> a

id :: a -> a
id x = x

在Haskell中,类型中的小写标识符是普遍量化的变量 - 上面的签名与我编写的一样id :: forall a. a -> a,除了forall明确写入只对某些语言扩展有效.

标识函数是参数化多态函数的最简单示例,它强调了参数函数只是传递数据的想法.他们无法检查数据以对其执行任何操作.

让我们考虑一个稍微有趣的功能:列表反转.在Haskell中,a编写了某些类型的列表[a],因此reverse函数是

reverse :: [a] -> [a]
reverse []     = []
reverse (x:xs) = reverse xs ++ [x]
  -- `x:xs` is the list whose first element is `x` and whose second element is
  -- `xs`; `++` is the list-append operator.

该reverse函数将列表中的元素混洗,但它从不操纵它们(因此永远不会"调度"它们).因此,reverse知道它必须采取并返回某些东西的列表 - 但它并不关心那是什么东西.

参数多态的最后一个例子是map函数.此函数接受函数f和列表,并将该函数应用于列表中的每个元素.这个描述告诉我们,我们不关心函数的输入或输出类型,也不关心输入列表的类型 - 但它们必须适当匹配.因此,我们有

map :: (a -> b) -> [a] -> [b]
map f []     = []
map f (x:xs) = f x : map f xs
  -- In Haskell, function application is whitespace, so `map f xs` is like
  -- `map(f,xs)` in a C-like language.

注意,传入函数的输入(分别输出)类型和输入(分别为输出)列表的元素类型必须匹配; 但是,输入和输出类型可以彼此不同,我们不在乎.

参数多态与子类型

您在评论中询问参数函数是否只接受顶部类型的值.答案是否定的:子类型完全独立于参数多态.Haskell没有子类型的任何概念都:一个Int是Int,和Bool是Bool,两者永远不相遇.在Java中,你有泛型和子类型,但这两个特性在语义上是无关的(除非你使用形式的有界多态<T extends Super>,但这更像是一种ad-hoc多态,我将在下面讨论).参数多态实际上就是它所说的:接受任何类型的函数.这与接受顶级类型并依赖包含/隐式向上转换的函数不同.考虑它的一种方法是参数函数采用另一个参数:参数的类型.所以不是id 3,你会有id Int 3; 而不是id True,你会id Bool True.在Haskell中,您永远不需要明确地执行此操作,因此没有语法.另一方面,在Java中,您有时需要,因此有反映这一点的语法,如Collections.<String>emptyList().

Ad-hoc多态性

参数多态通常与各种形式的ad-hoc多态性形成对比:多态性允许一个函数在不同类型中以不同方式运行.这是"派遣"出现的地方; 参数多态性是关于均匀性的,ad-hoc多态性是关于差异的.有时您不希望函数在每种类型中以相同的方式运行!

标准的类Java面向对象的子类型多态性,正式称为名义子类型,就是这样的一个例子; 例如,在Java中,该boolean Object.equals(Object)方法使用子类型多态来分派其第一个参数并返回适当的结果.很明显,你不希望平等是参数化的; 你不能写一个函数来准确地比较字符串和整数是否相等!但是,请注意,.equals它还用于instanceof对参数的运行时类型执行"typecase"检查; 该int Object.hashCode()方法是纯子类型多态方法的一个例子.

Haskell使用一种称为类型多态的不同方法来处理这个问题.这是一个如何运作的旋风之旅.首先,我们说出相等的等式意味着什么(请注意,Haskell允许您定义作为任意运算符的函数名,然后使用它们作为中缀):

class Eq a where -- To say that a type `a` is comparable for equality, implement
                 -- these functions:
  (==) :: a -> a -> Bool -- Equality
  (/=) :: a -> a -> Bool -- Inequality

  -- We can also define default implementations for those functions:
  x == y = not (x /= y)
  x /= y = not (x == y)

然后,我们实例化类型类; 例如,在这里我们说如何比较布尔值的平等.

instance Eq Bool where
  True  == True  = True
  False == False = True
  _     == _     = False
    -- `_` means "don't care".

当我们想要比较元素的相等性时,我们指定必须有一个满足适当约束的类型.例如,elem检查元素是否出现在列表中的函数具有类型Eq a => a -> [a] -> Bool; 我们可以把它读作"对于任何a 一个实例Eq,elem期望一个a和一个as 的列表,并返回一个布尔值":

elem :: Eq a => a -> [a] -> Bool
elem _ []     = False
elem y (x:xs) = x == y || elem y xs
  -- Haskell supports an infix syntax that would have allowed us to write
  -- `y `elem` xs`, with the backticks around `elem`.

这里,elem函数不是参数多态的,因为我们有一些关于类型的信息 - a我们知道我们可以比较它的元素是否相等.因此,对于每种输入类型elem都不会以相同的方式运行(并且有些类型我们甚至无法比较相等性,例如函数),因此这里也有一种基于类型的调度.

¹如果您更熟悉Java等语言,Java中的相同功能(忽略包含类)

public static <T> T id(T t) { return t; }

请注意,与Haskell不同,Java允许您通过使用instanceof运算符或类似于.toString()始终可用的调用方法来违反参数,但我们的id函数不会这样做.