Haskell中的动态调度

Question

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

Answer 1

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

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

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

很多时候，对象和虚函数的整个结构感觉就像是对闭包缺乏支持的精心设计的变通方法。

例如，考虑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));      

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

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

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

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 ...
    }

-- 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语言的一对一映射。但是对于大多数目的来说，它只是比第一节中描述的方法更复杂，更不灵活。原因是，如果关于各种小部件的唯一重要的事情是它们实现小部件功能的方式，那么创建类型、这些类型的接口实例，然后通过将它们放在存在包装器中来再次抽象底层类型就没有什么意义了：直接传递函数更简单。

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

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

然后，对于具有iswidgetExtra的任何类型，还可以无缝地使用iswidget的方法。基于记录的方法的唯一替代方法是在记录中设置记录，这涉及到内部记录的一些手动包装和展开。但是，只有当您想显式地模拟一个OO语言的深层类层次结构时，这才是有利的，反过来，只有当您想让自己的生活变得困难时，才会这样做。（还要注意，Haskell没有任何内置的方式可以动态地从iswidget向下转换到iswidgetextrate。但是有ifcxt）

（基于记录的方法的优点是什么？除了每次要做新的事情时不必定义新的类型之外，记录是简单的值级别的事情，值比类型更容易操作。例如，您可以编写一个函数，将小部件作为参数，并在此基础上创建一个新的小部件，有些事情不同，有些事情保持不变。这有点像C++中模板参数的子类，只是不那么容易混淆。）

>

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

Record：struct（使用公共数据成员而不使用其他内容的类）。也被称为字典。

闭包：函数语言（和许多其他语言）允许您定义局部函数（函数中的函数，lambda)，这些函数引用定义站点范围内的东西（例如，外部函数的参数），您通常不希望保留这些东西，而是在函数的“闭包”中。或者，如果您有一个像加上这样的函数，它接受两个int，返回一个int，您可以将它应用于一个参数，例如5，结果将是一个接受int，返回int，方法是将其加上5-在这种情况下，5也存储在结果函数的闭包中。（在其他上下文中，“闭包”有时也用来表示“带有闭包的函数”。）

类型类：与OO语言中的类不同。有点像接口，但也很不同。看这里。

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