什么是多态 lambda？

Question

什么是多态 lambda？

functionhaskelllambdafunctional-programmingpolymorphism

5

对于我来说，Lambda函数（匿名函数）的概念非常清晰。我也知道在类方面的多态性，使用运行时/动态调度根据实例的最终派生类型调用适当的方法。但是Lambda如何实现多态呢？我是另一个试图学习更多关于函数式编程的Java程序员。

- sdanzig

我猜这是为了可以“通用地”处理lambda，其中你有一个接受函数的东西，并且可以像处理其他函数类型一样处理它。但是这个功能的实际实现方式对我来说还有点模糊。 - sdanzig

3个回答

1

在C++中，从C++14开始，多态（或通用）lambda是一种可以接受任何类型作为参数的lambda表达式。基本上它是一个具有auto参数类型的lambda表达式： auto lambda = [](auto){};

- dividedbyzero

0

你听说过“多态 lambda”这个术语吗？如果有上下文，我们也许可以更具体地解释。

lambda 函数最简单的多态形式是接受类型与最终结果部分无关的参数。

例如，lambda 函数：

\(head:tail) -> tail

具有类型[a] -> [a]，例如它在列表的内部类型中是完全多态的。

其他简单的例子包括

\_ -> 5      :: Num n => a -> n
\x f -> f x  :: a -> (a -> b) -> b
\n -> n + 1  :: Num n => n -> n

等等。

（请注意涉及类型类分派的 Num n 示例）

- amindfv

在谷歌上搜索“多态lambda”会导致关于C++11 lambda及其不支持模板化的讨论（例如，这个问题）。这表明这个答案将与OP相关。 - duplode

实际上，这个上下文是关于 Rust 编程语言对多态 lambda 的支持是其适合函数式编程的原因之一的讨论。 - sdanzig

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- leftaroundabout · Accepted Answer

你会注意到，在下面的答案中，我并没有过多地谈论lambda。请记住，在函数式语言中，任何函数都只是绑定到名称的lambda，因此我所说的关于函数的内容也适用于lambda。

多态

请注意，多态并不真正需要OO语言通过派生类覆盖虚拟方法实现的"分发"。那只是一种特定类型的多态，即子类型化。

多态本身只是表示一个函数不仅允许一种特定类型的参数，而且能够相应地处理任何允许的类型。最简单的例子：你根本不关心类型，只需传递任何被传入的值。或者，为了使它不那么琐碎，可以将其包装在单个元素容器中。你可以在C++中实现这样一个函数：

template<typename T> std::vector<T> wrap1elem( T val ) {
  return std::vector(val);
}

但你不能将其实现为lambda，因为C++（编写时：C++11）不支持多态lambda。

未分类值

...至少不是以这种方式。C++模板以相当不寻常的方式实现多态：编译器实际上为每个类型生成单态函数，并在遇到的所有代码中生成。这是由于C++的“值语义”：当传入一个值时，编译器需要知道确切的类型（它在内存中的大小、可能的子节点等），以便复制它。

在大多数较新的语言中，几乎所有东西都只是对某个值的引用，当您调用函数时，它不会得到参数对象的副本，而只是对已经存在的对象的引用。较早的语言要求您明确标记参数为引用/指针类型。

引用语义的一个很大优点是多态性变得更加容易：指针始终具有相同的大小，因此相同的机器代码可以处理对任何类型的引用。这使得即使在C中也可以非常丑陋地创建多态容器包装器：

typedef struct{
  void** contents;
  int size;
} vector;

vector wrap1elem_by_voidptr(void* ptr) {
  vector v;
  v.contents = malloc(sizeof(&ptr));
  v.contents[0] = ptr;
  v.size = 1;
  return v;
}
#define wrap1elem(val) wrap1elem_by_voidptr(&(val))

在这里，void*只是指向任何未知类型的指针。因此产生了一个明显的问题：vector不知道它“包含”的元素类型！所以你不能真正地对那些对象做任何有用的事情。除非你知道它是什么类型！

int sum_contents_int(vector v) {
  int acc = 0, i;
  for(i=0; i<v.size; ++i) {
    acc += * (int*) (v.contents[i]);
  }
  return acc;
}

显然，这非常费力。如果类型是double呢？如果我们想要的是“product”而不是“sum”呢？当然，我们可以手动编写每种情况。这不是一个好的解决方案。更好的方法是有一个通用函数，它将“要执行什么指令”作为额外参数！C语言有函数指针：

int accum_contents_int(vector v, void* (*combine)(int*, int)) {
  int acc = 0, i;
  for(i=0; i<v.size; ++i) {
    combine(&acc, * (int*) (v.contents[i]));
  }
  return acc;
}

那可以像这样使用

void multon(int* acc, int x) {
  acc *= x;
}
int main() {
  int a = 3, b = 5;
  vector v = wrap2elems(a, b);
  printf("%i\n", accum_contents_int(v, multon));
}

除了仍然笨重，以上所有C代码都有一个巨大的问题：如果容器元素实际上具有正确的类型，则完全未经检查！来自* void 的强制转换将在任何类型上轻松触发，但是如果存在疑问，则结果将是完全的垃圾²。

类和继承

这个问题是OO语言试图通过尝试将您可能执行的所有操作与数据一起捆绑在对象中作为方法来解决的主要问题之一。编译您的类时，类型是单态的，因此编译器可以检查操作是否有意义。当您尝试使用值时，如果编译器知道如何找到方法，则就足够了。特别是，如果您创建了派生类，则编译器知道“啊哈，在派生对象上调用基类的方法是可以的”。

很不幸，这意味着通过多态实现的所有内容都等同于组合数据并仅在单个字段上调用（单态）方法。要实际获得不同类型的（但可控的！）不同行为，面向对象语言需要虚拟方法。这基本上意味着类具有额外的字段，其中包含指向方法实现的指针，就像我在 C 示例中使用的指向 combine 函数的指针一样——唯一的区别是您只能通过添加派生类来实现重写方法，对于这些类，编译器再次知道所有数据字段的类型等，因此您是安全的。

复杂的类型系统，检查过的参数化多态性

尽管基于继承的多态显然有效，但我不得不说它有点限制性，也许有点疯狂愚蠢。如果您想要使用仅作为类方法未实现的特定操作，您需要创建一个完整的派生类。即使您只想以某种方式改变操作，您也需要派生并覆盖方法的稍微不同版本。

让我们重新审视一下我们的C代码。乍一看，我们注意到应该完全可以使其具有类型安全性，而不需要任何方法捆绑的废话。我们只需要确保在编译时没有丢失任何类型信息。想象一下_{(将∀T读作“对于所有类型T”)}

∀T: {
  typedef struct{
    T* contents;
    int size;
  } vector<T>;
}

∀T: {
  vector<T> wrap1elem(T* elem) {
    vector v;
    v.contents = malloc(sizeof(T*));
    v.contents[0] = &elem;
    v.size = 1;
    return v;
  }
}

∀T: {
  void accum_contents(vector<T> v, void* (*combine)(T*, const T*), T* acc) {
    int i;
    for(i=0; i<v.size; ++i) {
      combine(&acc, (*T) (v[i]));
    }
  }
}

请看一下，即使签名看起来很像这篇文章顶部的 C++ 模板（实际上只是自动生成的单态代码），实现实际上几乎就是普通的 C 语言。其中没有 T 值，只有指向它们的指针。不需要编译多个版本的代码：在 运行时，不需要类型信息，我们只需要处理通用指针。在编译时，我们知道类型并可以使用函数头来确保它们匹配。例如，如果你写了

void evil_sumon (int* acc, double* x) { acc += *x; }

并尝试去做

vector<float> v; char acc;
accum_contents(v, evil_sumon, acc);

编译器会抱怨类型不匹配：在accum_contents的声明中，它说类型可能会有所变化，但是所有出现的T都需要解析为相同的类型。这正是ML系列语言和Haskell中参数多态性的工作原理：函数确实不知道它们正在处理的多态数据的任何信息。但是它们被赋予了具有此知识的专用运算符，作为参数。

在像Java（Lambda之前）这样的语言中，参数多态性并没有带来太多好处：由于编译器故意使“只定义一个简单的辅助函数”变得困难，而更喜欢仅有类方法，因此您可以直接采用从类派生的方式。但在函数式语言中，定义小型辅助函数是最容易想象的事情：lambda！

因此，您可以在Haskell中编写令人难以置信的简洁代码。 foldr (+) 0 [1,4,6]
11
Prelude> foldr (\x y -> x+y+1) 0 [1,4,6]
14
Prelude> let f start = foldr (\_ (xl,xr) -> (xr, xl)) start
Prelude> :t f
f :: (t, t) -> [a] -> (t, t)
Prelude> f ("left", "right") [1]
("right","left")
Prelude> f ("left", "right") [1, 2]
("left","right")

注意，在 f 的帮助程序中，我并不知道 xl 和 xr 的类型，我只想交换这些元素的元组，这需要这些类型相同。因此，这将是一个多态 lambda，其类型为

\_ (xl, xr) -> (xr, xl)   ::  ∀ a t.  a -> (t,t) -> (t,t)

Apart from the weird explicit malloc stuff, type safety etc.: code like that is extremely hard to work with in languages without garbage collector, because somebody always needs to clean up memory once it's not needed anymore, but if you didn't watch out properly whether somebody still holds a reference to the data and might in fact need it still. That's nothing you have to worry about in Java, Lisp, Haskell...

There is a completely different approach to this: the one dynamic languages choose. In those languages, every operation needs to make sure it works with any type (or, if that's not possible, raise a well-defined error). Then you can arbitrarily compose polymorphic operations, which is on one hand "nicely trouble-free" (not as trouble-free as with a really clever type system like Haskell's, though) but OTOH incurs quite a heavy overhead, since even primitive operations need type-decisions and safeguards around them.

³当然，我在这里有些不公平。面向对象的范式不仅仅是类型安全的多态性，它还可以实现许多其他的功能，例如旧版 ML 使用的 Hindler-Milner 类型系统无法实现的（特殊多态性：Haskell 有类型类，SML 有模块），甚至一些 Haskell 中比较困难的东西（主要是将不同类型的值存储在可变大小的容器中）。但是，当您习惯函数式编程时，您对这种东西的需求就会越来越少。