haskell - Haskell 中的动态调度

Question

例如，用 Java 编写的程序在很大程度上依赖于动态调度。

这些程序如何用 Haskell 等函数式语言表达？

换句话说，Haskell 表达“动态调度”思想的方式是什么？

Answer 1

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

更具体地说，一个面向对象的对象包括:

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

对象的数据成员(本地状态)

很多时候，由于缺乏对闭包的支持，整个对象和虚拟函数的架构感觉像是一个精心设计的解决方法。

例如考虑 Java 的 Comparator 接口(interface):

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));
}

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

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

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 情况下，通过简单地将多个函数放入接口(interface)(及其实现)中来编码，而在 Haskell 中则通过传递函数记录而不是单一功能。 (我们本可以在前面的例子中传递一个包含单个函数的记录，但我们并不喜欢它。)

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

基于类型的动态调度

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

继续我们的 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 唯一重要的事情是它们实现小部件功能的方式，那么创建类型、这些类型的接口(interface)实例，然后通过将它们放入其中来再次抽象出底层类型就没有什么意义了。存在性包装器:直接传递函数更简单。

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

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

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

(基于记录的方法的优点是什么？除了不需要每次做新事物时都定义一个新类型，记录是简单的值级事物，值比类型更容易操作。你可以例如，编写一个函数，它以 IsWidgetExtra 作为参数，并基于它生成一个新的 Widget，其中有些不同，有些保持不变。这有点像从 C++ 中的模板参数进行子类化，只是不那么令人困惑。 )

词汇表

高阶函数:将其他函数作为参数(或作为结果返回)的函数

记录:struct(具有公共(public)数据成员的类，没有别的)。也称为字典。

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

类型类:与面向对象语言中的类不同。有点像一个界面，但也非常不同。 See here。

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