在函数式编程中,什么是函子? [英] In Functional Programming, what is a functor?
问题描述
在阅读关于函数式编程的各种文章时,我碰到过几次'函子',但作者通常假设读者已经理解了这个术语。环顾网络提供了过多的技术性描述(请参阅维基百科文章)或难以置信的模糊描述(请参阅 ocaml-tutorial网站上有关Functors的部分)。
有人可以好好定义这个术语,解释它的用法,或者提供一个关于如何创建和使用Functors的例子?
编辑:虽然我对这个术语背后的理论很感兴趣,但我对这个理论的兴趣并不比我在这个概念的实现和实际应用中。
编辑2 :看起来好像有一些跨界问题正在发生:我特指函数式编程的函子,而不是C ++的函数对象。 p>
函子一词来自类别理论,是一个非常普遍,非常抽象的数学分支。它至少以两种不同的方式被功能语言的设计者借用。
-
在ML语言系列中,函子是一个将一个或多个其他模块作为参数的模块。它被认为是一个高级功能,大多数初学程序员都遇到了困难。
作为实现和实际应用的例子,您可以定义您最喜欢的平衡二叉搜索树形式一劳永逸地作为一个仿函数,它将作为参数提供一个模块:在二叉树中使用
-
关键字上的总排序函数
完成此操作后,您可以永远使用相同的平衡二叉树实现。 (存储在树中的值的类型通常是多态的 - 树不需要查看除复制它们之外的值,而树肯定需要能够比较键,并且它从)
ML函数的另一个应用是分层网络协议。链接是由CMU福克斯集团撰写的一篇非常了不起的论文;它展示了如何使用仿函数在更简单的图层类型(如IP或甚至直接通过以太网)上构建更复杂的协议层(如TCP)。每个图层都是作为一个函子实现的,它将下面的图层作为参数。软件的结构实际上反映了人们思考问题的方式,而不是程序员头脑中存在的层。在1994年这项工作发布时,这是一件大事。
对于ML函子的一个实例,你可以看到 ML Module Mania ,其中包含一个可发布的函数例子(即可怕的例子) 。为了对ML模块系统(与其他类型的模块进行比较)做出明确,清晰,明确的解释,请阅读Xavier Leroy的辉煌的1994年POPL论文的前几页清单类型,模块和独立编译。 >在Haskell和一些相关的纯函数语言中, Functor
是一个类型的类。一个类型属于一个类型类(或者更技术上讲,类型是类型类的一个实例),当类型提供某些预期行为的某些操作时。 T
类型可以属于类 Functor
,如果它具有某种类似集合的行为:
-
类型
T
是通过另一种类型参数化的,您应该将其视为元素类型集合。完整集合的类型则类似于T Int
,T String ,
$ bT Bool
,如果分别包含整数,字符串或布尔值。如果元素类型是未知的,它将被写为类型参数a
,如T a 示例包括列表(零个或多个类型为
a
的元素),可能
类型(零或一个元素类型a
),类型a
,a
类型的元素数组,包含类型a
的值的各种搜索树,以及很多其他人可以想到的。 有一个类型为 -
将整数列表转换为布尔值列表
-
将整数树转换为布尔值树
-
将
Nothing
转换为Nothing
和Just 7
$ b $ p $在Haskell中,this属性通过给定类型fmap
来表示:
fmap :: (Functor t)=> (a - > b) - > t a - > tb
我们现在有一个
t
,这意味着任何类型的Functor
类。
a - >的函数。 b
(元素上的一个函数),那么你必须能够使用该函数并在集合上产生相关的函数。您可以使用 Functor
类型类中的每个类型共享的运算符 fmap
执行此操作。运算符实际上已经被重载,所以如果你有一个函数甚至
并且类型为 Int - > Bool
,然后 fmap甚至
是一个重载函数,可以执行许多美妙的事情:
<长话短说,在Haskell 中,一个函子是一种集合,如果你给它一个函数元素, fmap
会让你回来集合函数。正如你可以想象的那样,这是一个可以被广泛重用的想法,这就是为什么它作为Haskell标准库的一部分而受到祝福。
像往常一样,人们不断发明新的有用的抽象概念,并且您可能希望查看应用函子,其最佳参考可能是名为 Contribute McBride和Ross Paterson的Applicative Programming with Effects。
I've come across the term 'Functor' a few times while reading various articles on functional programming, but the authors typically assume the reader already understands the term. Looking around on the web has provided either excessively technical descriptions (see the Wikipedia article) or incredibly vague descriptions (see the section on Functors at this ocaml-tutorial website).
Can someone kindly define the term, explain its use, and perhaps provide an example of how Functors are created and used?
Edit: While I am interested in the theory behind the term, I am less interested in the theory than I am in the implementation and practical use of the concept.
Edit 2: Looks like there is some cross-terminoligy going on: I'm specifically referring to the Functors of functional programming, not the function objects of C++.
The word "functor" comes from category theory, which is a very general, very abstract branch of mathematics. It has been borrowed by designers of functional languages in at least two different ways.
In the ML family of languages, a functor is a module that takes one or more other modules as a parameter. It's considered an advanced feature, and most beginning programmers have difficulty with it.
As an example of implementation and practical use, you could define your favorite form of balanced binary search tree once and for all as a functor, and it would take as a parameter a module that provides:
The type of key to be used in the binary tree
A total-ordering function on keys
Once you've done this, you can use the same balanced binary tree implementation forever. (The type of value stored in the tree is usually left polymorphic—the tree doesn't need to look at values other than to copy them around, whereas the tree definitely needs to be able to compare keys, and it gets the comparison function from the functor's parameter.)
Another application of ML functors is layered network protocols. The link is to a really terrific paper by the CMU Fox group; it shows how to use functors to build more complex protocol layers (like TCP) on type of simpler layers (like IP or even directly over Ethernet). Each layer is implemented as a functor that takes as a parameter the layer below it. The structure of the software actually reflects the way people think about the problem, as opposed to the layers existing only in the mind of the programmer. In 1994 when this work was published, it was a big deal.
For a wild example of ML functors in action, you could see the paper ML Module Mania, which contains a publishable (i.e., scary) example of functors at work. For a brilliant, clear, pellucid explanation of the ML modules system (with comparisons to other kinds of modules), read the first few pages of Xavier Leroy's brilliant 1994 POPL paper Manifest Types, Modules, and Separate Compilation.
In Haskell, and in some related pure functional language,
Functor
is a type class. A type belongs to a type class (or more technically, the type "is an instance of" the type class) when the type provides certain operations with certain expected behavior. A typeT
can belong to classFunctor
if it has certain collection-like behavior:The type
T
is parameterized over another type, which you should think of as the element type of the collection. The type of the full collection is then something likeT Int
,T String
,T Bool
, if you are containing integers, strings, or Booleans respectively. If the element type is unknown, it is written as a type parametera
, as inT a
.Examples include lists (zero or more elements of type
a
), theMaybe
type (zero or one elements of typea
), sets of elements of typea
, arrays of elements of typea
, all kinds of search trees containing values of typea
, and lots of others you can think of.The other property that
T
has to satisfy is that if you have a function of typea -> b
(a function on elements), then you have to be able to take that function and product a related function on collections. You do this with the operatorfmap
, which is shared by every type in theFunctor
type class. The operator is actually overloaded, so if you have a functioneven
with typeInt -> Bool
, thenfmap even
is an overloaded function that can do many wonderful things:
Convert a list of integers to a list of Booleans
Convert a tree of integers to a tree of Booleans
Convert
Nothing
toNothing
andJust 7
toJust False
In Haskell, this property is expressed by giving the type of
fmap
:fmap :: (Functor t) => (a -> b) -> t a -> t b
where we now have a small
t
, which means "any type in theFunctor
class."
To make a long story short, in Haskell a functor is a kind of collection for which if you are given a function on elements,
fmap
will give you back a function on collections. As you can imagine, this is an idea that can be widely reused, which is why it is blessed as part of Haskell's standard library.
As usual, people continue to invent new, useful abstractions, and you may want to look into applicative functors, for which the best reference may be a paper called Applicative Programming with Effects by Conor McBride and Ross Paterson.
这篇关于在函数式编程中,什么是函子?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!