use*_*220 49 haskell functional-programming dynamic-dispatch
用例如Java编写的程序很大程度上依赖于动态调度.如何用Haskell等函数式语言表达这些程序？换句话说,Haskell在"动态调度"下表达这个想法的方式是什么？
gla*_*erl 69
答案看似简单:高阶函数.在OO语言中使用虚拟方法的对象只不过是一个美化的功能记录和一些本地状态.在Haskell中,您可以直接使用函数记录,并将本地状态存储在它们的闭包中.
更具体地说,OO对象包括:
在很多时候,整个对象和虚拟功能的大厦感觉就像缺乏对闭包的支持一样精心设计的解决方法.
例如,考虑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));
}
请注意,我们没有定义任何类型.我们使用的只是功能.在这两种情况下,我们传递给sort函数的"payload"是一个函数,它接受两个元素并给出它们的相对排序.在一种情况下,这是通过定义实现接口的类型,以适当的方式实现其虚函数,以及传递该类型的对象来实现的.在另一种情况下,我们直接传递了一个函数.在这两种情况下,我们在传递给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 ...
}
再次注意,在初始之后Widget,我们没有定义任何类型.我们只编写了一个函数来构造函数记录并将事物存储在它们的闭包中.大多数情况下,这也是在OO语言中定义子类的唯一原因.与前一个示例的唯一区别在于,不是一个函数有多个,在Java情况下通过简单地在接口(及其实现)中放置多个函数来编码,而在Haskell中通过传递函数记录而不是单一功能.(我们本可以在前面的例子中传递包含单个函数的记录,但我们不喜欢它.)
(值得注意的是,很多时候你不需要动态调度.如果你只是想根据类型的默认排序对列表进行排序,那么你只需要使用sort :: Ord a => [a] -> [a],它使用Ord为给定定义的实例a类型,静态选择.)
Java方法和上面的Haskell方法之间的一个区别在于,使用Java方法,对象的行为(除了本地状态)由其类型决定(或者更少慈善,每个实现都需要一个新类型).在Haskell中,我们按照自己喜欢的方式制作功能记录.大多数情况下,这是纯粹的胜利(获得灵活性,没有任何损失),但是假设出于某种原因我们希望它是Java方式.在这种情况下,正如其他答案所提到的那样,前进的方式是类型类和存在性.
继续我们的Widget例子,假设我们希望Widget从其类型开始遵循a的实现(为每个实现要求一个新类型).我们定义一个类型类来将类型映射到它的实现:
-- 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语言的一对一映射.但是对于大多数用途来说,它比第一部分中描述的方法更精细,更灵活.原因是如果关于各种Widgets的唯一重要的事情是它们实现窗口小部件函数的方式,那么为这些类型创建类型,接口实例,然后通过将它们放入其中来再次抽象掉底层类型是没有意义的.一个存在的包装器:直接传递函数更简单.
我能想到的一个优点是,虽然Haskell没有子类型,但它确实具有"子类化"(可能更好地称为子接口或子约束).例如,您可以这样做:
class IsWidget a => IsWidgetExtra a where
...additional methods to implement...
然后对于你拥有的任何类型IsWidgetExtra,你也可以使用IsWidget无缝的方法.基于记录的方法的唯一选择是在记录内记录,其中涉及内部记录的一些手动包装和展开.但是,如果你想明确地模仿OO语言的深层次结构,这只会是有利的,反过来你只有在想让自己的生活变得困难时才会这样做.(另请注意,Haskell没有任何内置方式可以动态地向下转换IsWidget为IsWidgetExtra.但是有ifcxt)
(基于记录的方法的优点怎么样？除了每次想要创建新事物时都不必定义新类型,记录是简单的价值级事物,值比类型更容易操作.你可以例如,编写一个函数,它将一个Widget参数作为一个参数并Widget根据它创建一个新函数,其中一些东西不同而其他东西保持不变.这有点像从C++中的模板参数继承子类,只是不那么混乱.)
高阶函数:将其他函数作为参数(或将其作为结果返回)的函数
记录:struct(具有公共数据成员的类,没有别的).也称为字典.
闭包:函数式语言(以及许多其他语言)允许您定义本地函数(函数内的函数,lambdas),这些函数引用定义站点中的作用域(例如,外部函数的参数),这些函数通常不会在函数的"闭包"中被保留,但是.或者,如果你有一个像plus这样的函数需要两个int并返回一个int,你可以将它应用于一个参数,比如说5,结果将是一个带有int的函数并返回一个int,通过向它添加5 -在这种情况下,5它也存储在结果函数的闭包中.(在其他情况下,"闭包"有时也用于表示"具有闭包的函数".)
Type类:不一样的面向对象语言中的类.有点像界面,但也非常不同.看到这里.
编辑29-11-14:虽然我认为这个答案的核心仍然基本上是正确的(Haskell中的HOF对应于OOP中的虚拟方法),但自从我写这篇文章以来,我的价值判断已经变得有些细微差别.特别是,我现在认为Haskell和OOP的方法都不是严格"更基本"的.看到这个reddit评论.
Mat*_*hid 11
令人惊讶的是,您实际上并不需要动态调度,只需多态.
例如,如果您要编写一个对列表中的所有数据进行排序的函数,那么您希望它是多态的.(也就是说,你不希望有重新实现此功能,为每一个类型,由专人这将是糟糕的.),但你实际上并不需要任何动态 ; 你知道在编译时你想要排序的列表中的实际内容.因此,在这种情况下,您根本不需要运行时类型查找.
在Haskell中,如果你只是想移动东西并且你不需要知道或关心它是什么类型,你可以使用所谓的"参数多态",这大致类似于Java泛型或C++模板.如果您需要能够将函数应用于数据(例如,要对数据进行排序,则需要进行顺序比较),您可以将函数作为参数传递.或者,Haskell有一个类似于Java接口的东西,你可以说"这个排序函数接受实现这个接口的任何类型的数据".
到目前为止,根本没有动态调度,只有静态.另请注意,由于您可以将函数作为参数传递,因此您可以手动"手动"调度.
如果你真的需要实际的动态调度,你可以使用"存在类型",或者你可以使用Data.Dynamic库和类似的技巧.
也许你需要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"