在函数式编程中,什么是函子? [英] In Functional Programming, what is a functor?

查看:300
本文介绍了在函数式编程中,什么是函子?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

在阅读关于函数式编程的各种文章时,我碰到过几次'函子',但作者通常假设读者已经理解了这个术语。环顾网络提供了过多的技术性描述(请参阅维基百科文章)或难以置信的模糊描述(请参阅 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 , T Bool ,如果分别包含整数,字符串或布尔值。如果元素类型是未知的,它将被写为类型参数 a ,如 T a $ b

    示例包括列表(零个或多个类型为 a 的元素),可能类型(零或一个元素类型 a ),类型 a a 类型的元素数组,包含类型 a 的值的各种搜索树,以及很多其他人可以想到的。

  • 有一个类型为 a - >的函数。 b (元素上的一个函数),那么你必须能够使用该函数并在集合上产生相关的函数。您可以使用 Functor 类型类中的每个类型共享的运算符 fmap 执行此操作。运算符实际上已经被重载,所以如果你有一个函数甚至并且类型为 Int - > Bool ,然后

      fmap甚至

    是一个重载函数,可以执行许多美妙的事情:


    • 将整数列表转换为布尔值列表


    • 将整数树转换为布尔值树


    • Nothing 转换为 Nothing Just 7 $ b $ p $在Haskell中,this属性通过给定类型 fmap 来表示:

        fmap :: (Functor t)=> (a  - > b) - > t a  - > tb 

      我们现在有一个 t ,这意味着任何类型的 Functor 类。




    <长话短说,在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 type T can belong to class Functor 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 like T 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 parameter a, as in T a.

      Examples include lists (zero or more elements of type a), the Maybe type (zero or one elements of type a), sets of elements of type a, arrays of elements of type a, all kinds of search trees containing values of type a, and lots of others you can think of.

    • The other property that T has to satisfy is that if you have a function of type a -> 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 operator fmap, which is shared by every type in the Functor type class. The operator is actually overloaded, so if you have a function even with type Int -> Bool, then

      fmap 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 to Nothing and Just 7 to Just 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 the Functor 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屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆