54

Programs written in, for example, Java rely a lot on dynamic dispatch.

How are such programs expressed in functional languages such as Haskell?

In other words, what is the Haskell way of expressing the idea underneath "dynamic dispatch"?

4

4 回答 4

78

答案看似简单：高阶函数。在 OO 语言中具有虚方法的对象只不过是功能与一些本地状态的美化记录。在 Haskell 中，您可以直接使用函数记录，并将本地状态存储在它们的闭包中。

更具体地说，一个 OO 对象包括：

  • 指向 vtable（虚拟方法表）的指针 (vptr)，其中包含对象类的虚拟方法的实现。换句话说，一堆函数指针；功能记录。值得注意的是，每个函数都有一个隐藏参数，即对象本身，它是隐式传递的。
  • 对象的数据成员（本地状态）

很多时候，对象和虚函数的整个大厦感觉就像是一个精心设计的解决方法，因为它缺乏对闭包的支持。

例如考虑 Java 的Comparator接口：

public interface Comparator<T> {
    int compare(T o1, T o2); // virtual (per default)
}

并假设您想使用它根据字符串的第 N 个字符对字符串列表进行排序（假设它们足够长）。您将定义一个类：

public class MyComparator implements Comparator<String> {
    private final int _n;

    MyComparator(int n) {
        _n = n;
    }

    int compare(String s1, String s2) {
        return s1.charAt(_n) - s2.charAt(_n);
    }
}

然后你使用它：

Collections.sort(myList, new MyComparator(5));

在 Haskell 中，你会这样做：

sortBy :: (a -> a -> Ordering) -> [a] -> [a]

myComparator :: Int -> (String -> String -> Ordering)
myComparator n = \s1 s2 -> (s1 !! n) `compare` (s2 !! n)
-- n is implicitly stored in the closure of the function we return

foo = sortBy (myComparator 5) myList

如果你不熟悉 Haskell，下面是它在一种伪 Java 中的大致样子：（我只打算这样做一次）

public void <T> sortBy(List<T> list, Ordering FUNCTION(T, T) comparator) { ... }

public (Ordering FUNCTION(String, String)) myComparator(int n) {
    return FUNCTION(String s1, String s2) {
        return s1[n].compare(s2[n]);
    }
}

public void foo() {
    sortBy(myList, myComparator(5));
}

请注意，我们没有定义任何类型。我们使用的只是函数。在这两种情况下，我们传递给排序函数的“有效负载”都是一个接受两个元素并给出它们相对顺序的函数。在一种情况下，这是通过定义实现接口的类型、以适当的方式实现其虚函数并传递该类型的对象来实现的；在另一种情况下，我们只是直接传递了一个函数。在这两种情况下，我们都在传递给排序函数的事物中存储了一个内部整数。在一种情况下，这是通过向我们的类型添加一个私有数据成员来完成的，在另一种情况下，通过在我们的函数中简单地引用它，使其保留在函数的闭包中。

考虑更详细的带有事件处理程序的小部件示例：

public class Widget {
    public void onMouseClick(int x, int y) { }
    public void onKeyPress(Key key) { }
    public void paint() { }
    ...
}

public class MyWidget extends Widget {
    private Foo _foo;
    private Bar _bar;
    MyWidget(...) {
        _foo = something;
        _bar = something; 
    }
    public void onMouseClick(int x, int y) {
        ...do stuff with _foo and _bar...
    }
}

在 Haskell 中，你可以这样做：

data Widget = Widget {
    onMouseClick :: Int -> Int -> IO (),
    onKeyPress   :: Key -> IO (),
    paint        :: IO (),
    ...
}

constructMyWidget :: ... -> IO Widget
constructMyWidget = do
    foo <- newIORef someFoo
    bar <- newIORef someBar
    return $ Widget {
        onMouseClick = \x y -> do
            ... do stuff with foo and bar ...,
        onKeyPress = \key -> do ...,
        paint = do ...
    }

再次注意，在初始 之后Widget，我们没有定义任何类型。我们只写了一个函数来构造函数的记录并将事物存储在它们的闭包中。在大多数情况下，这也是在 OO 语言中定义子类的唯一原因。与我们之前示例的唯一区别是，不是一个函数，而是多个函数，在 Java 案例中，通过简单地将多个函数放入接口（及其实现）中进行编码，而在 Haskell 中，通过传递函数记录而不是单一功能。（在前面的示例中，我们可以传递包含单个函数的记录，但我们不喜欢这样。）

（值得注意的是，很多时候您不需要动态调度。如果您只想根据类型的默认排序对列表进行排序，那么您只需使用sort :: Ord a => [a] -> [a]，它使用Ord为给定定义的实例a类型，静态选择。）

基于类型的动态调度

Java 方法和上面的 Haskell 方法之间的一个区别是，在 Java 方法中，对象的行为（除了它的本地状态）是由它的类型决定的（或者更不仁慈的是，每个实现都需要一个新类型）。在 Haskell 中，我们以我们喜欢的方式记录函数。大多数情况下，这是一个纯粹的胜利（获得了灵活性，没有损失任何东西），但假设出于某种原因我们希望它采用 Java 方式。在这种情况下，正如其他答案所提到的那样，要走的路是类型类和存在主义。

继续我们的Widget示例，假设我们希望 a 的实现Widget遵循其类型（每个实现都需要一个新类型）。我们定义一个类型类来将类型映射到它的实现：

-- the same record as before, we just gave it a different name
data WidgetImpl = WidgetImpl {
    onMouseClick :: Int -> Int -> IO (),
    onKeyPress   :: Key -> IO (),
    paint        :: IO (),
    ...
}

class IsWidget a where
    widgetImpl :: a -> WidgetImpl

data Widget = forall a. IsWidget a => Widget a

sendClick :: Int -> Int -> Widget -> IO ()
sendClick x y (Widget a) = onMouseClick (widgetImpl a) x y

data MyWidget = MyWidget {
    foo :: IORef Foo,
    bar :: IORef Bar
}

constructMyWidget :: ... -> IO MyWidget
constructMyWidget = do
    foo_ <- newIORef someFoo
    bar_ <- newIORef someBar
    return $ MyWidget {
        foo = foo_,
        bar = bar_
    }

instance IsWidget MyWidget where
    widgetImpl myWidget = WidgetImpl {
            onMouseClick = \x y -> do
                ... do stuff with (foo myWidget) and (bar myWidget) ...,
            onKeyPress = \key -> do ...,
            paint = do ...
        }

有点尴尬的是，我们有一个类只是为了获取函数的记录，然后我们必须将函数分别取出。我这样做只是为了说明类型类的不同方面：它们也只是函数的美化记录（我们在下面使用）以及一些魔法，编译器根据推断的类型插入适当的记录（我们在上面使用，并在下面继续使用）。让我们简化一下：

class IsWidget a where
    onMouseClick :: Int -> Int -> a -> IO ()
    onKeyPress   :: Key -> a -> IO ()
    paint        :: a -> IO ()
    ...

instance IsWidget MyWidget where
    onMouseClick x y myWidget = ... do stuff with (foo myWidget) and (bar myWidget) ...
    onKeyPress key myWidget = ...
    paint myWidget = ...

sendClick :: Int -> Int -> Widget -> IO ()
sendClick x y (Widget a) = onMouseClick x y a

-- the rest is unchanged from above

这种风格经常被来自 OO 语言的人采用，因为它更熟悉，更接近于 OO 语言的一对一映射。但对于大多数目的来说，它只是比第一节中描述的方法更复杂，更不灵活。原因是，如果关于各种 Widget 的唯一重要的事情是它们实现小部件功能的方式，那么为这些类型创建类型、接口实例，然后通过将它们放入一个存在的包装器：直接传递函数更简单。

我能想到的一个优点是，虽然 Haskell 没有子类型，但它确实有“子类化”（可能更好地称为子接口或子约束）。例如你可以这样做：

class IsWidget a => IsWidgetExtra a where
    ...additional methods to implement...

然后对于您拥有的任何类型，您也可以无缝地IsWidgetExtra使用 的方法。IsWidget基于记录的方法的唯一替代方案是记录内记录，这涉及到内部记录的一些手动包装和展开。但这只有在您想显式地模拟 OO 语言的深层类层次结构时才有优势，而这反过来又只有在您想让自己的生活变得困难时才会这样做。（另请注意，Haskell 没有任何内置方法可以从 to 动态向下IsWidget转换IsWidgetExtra。但是有ifcxt）

（基于记录的方法的优点是什么？除了不必每次你想做新事物时都定义一个新类型，记录是简单的值级别的东西，值比类型更容易操作。你可以，例如，编写一个以 aWidget作为参数并Widget基于它创建一个新函数的函数，其中一些不同而另一些保持相同。这有点像 C++ 中模板参数的子类化，只是不那么令人困惑。）

词汇表

  • 高阶函数：将其他函数作为参数（或将它们作为结果返回）的函数

  • 记录：结构（具有公共数据成员的类，仅此而已）。也称为字典。

  • 闭包：函数式语言（和许多其他语言）允许您定义本地函数（函数内的函数，lambdas），这些函数引用定义站点范围内的事物（例如，外部函数的参数），您通常不希望这样做被保留，但在函数的“闭包”中。或者，如果你有一个这样的函数plus，它接受两个 int 并返回一个 int，你可以将它应用到一个参数上，比如5，结果将是一个接受一个 int 并返回一个 int 的函数，方法是向它添加 5 -在这种情况下，5也存储在结果函数的闭包中。（在其他情况下，“闭包”有时也用于表示“带有闭包的函数”。）

  • 类型类：与OO 语言中的类不同。有点像一个界面，但也非常不同。见这里。

编辑 29-11-14：虽然我认为这个答案的核心仍然是基本正确的（Haskell 中的 HOF 对应于 OOP 中的虚拟方法），但自从我编写它以来，我的价值判断已经变得有些细微差别。特别是，我现在认为 Haskell 和 OOP 的方法都不是严格意义上的“更基础”。请参阅此 reddit 评论。

于 2012-10-28T16:14:27.213 回答
13

令人惊讶的是，您实际上并不需要动态调度，只需要多态性。

例如，如果您要编写一个对列表中的所有数据进行排序的函数，您希望它是多态的。（也就是说，你不想手动为每一种类型重新实现这个函数。那样会很糟糕。）但你实际上并不需要任何动态的东西；您在编译时就知道要排序的列表或列表中的实际内容。因此，在这种情况下，您实际上根本不需要运行时类型查找。

在 Haskell 中，如果你只是想移动东西而不需要知道或关心它是什么类型，你可以使用所谓的“参数多态”，它大致类似于 Java 泛型或 C++ 模板。如果您需要能够将函数应用于数据（例如，对需要比较顺序的数据进行排序），您可以将函数作为参数传递给它。或者，Haskell 有一个有点像 Java 接口的东西，你可以说“这个排序函数接受实现这个接口的任何类型的数据”。

到目前为止，根本没有动态调度，只有静态调度。另请注意，由于您可以将函数作为参数传递，因此您可以手动手动执行“调度”。

如果你真的需要实际的动态调度，你可以使用“存在类型”，或者你可以使用Data.Dynamic库和类似的技巧。

于 2012-10-28T09:22:20.037 回答
7

临时多态性是通过typeclasses完成的。更多类似 OOP 的 DD 是用存在类型来模拟的。

于 2012-10-28T07:57:21.953 回答
5

也许您需要 ADT 和模式匹配？

data Animal = Dog {dogName :: String}
            | Cat {catName :: String}
            | Unicorn

say :: Animal -> String
say (Dog {dogName = name}) = "Woof Woof, my name is " ++ name
say (Cat {catName = name}) = "Meow meow, my name is " ++ name
say Unicorn = "Unicorns do not talk"
于 2012-10-28T07:22:41.827 回答