在函数式编程中,什么是函子？

Question

在阅读有关函数式编程的各种文章时,我偶然遇到过"Functor"这个术语,但作者通常认为读者已经理解了这个术语.在网上浏览提供了过多的技术描述(参见维基百科文章)或令人难以置信的模糊描述(请参阅本ocaml教程网站上的Functors部分).

有人可以友好地定义术语,解释它的用法,并提供一个如何创建和使用Functors的例子吗？

编辑:虽然我对这个术语背后的理论感兴趣,但我对这个理论的兴趣不如我在实现和实际使用这个概念.

编辑2:看起来有一些交叉的术语:我特别指的是函数式编程的函数,而不是C++的函数对象.

Answer 1

"仿函数"这个词来自范畴理论,它是一个非常普遍的,非常抽象的数学分支.功能语言的设计者至少以两种不同的方式借用它.

• 在ML系列语言中,仿函数是一个将一个或多个其他模块作为参数的模块.它被认为是一种高级功能,大多数初级程序员都遇到了困难.

  作为实现和实际使用的一个例子,您可以一次性定义您最喜欢的平衡二叉搜索树形式作为仿函数,它将作为参数提供以下模块:

  • 要在二叉树中使用的密钥类型

  • 键上的总排序功能

  完成此操作后,您可以永久使用相同的平衡二叉树实现.(存储在树中的值的类型通常是多态的 - 树不需要查看除了复制它们之外的值,而树肯定需要能够比较键,它从中获取比较函数仿函数的参数.)

  ML仿函数的另一个应用是分层网络协议.这个链接是CMU Fox集团的一篇非常棒的论文; 它展示了如何使用仿函数在更简单的层(如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.

    示例包括列表(零个或多个类型的元素a),Maybe类型(类型的零个或一个元素a),类型的元素集,类型元素的a数组,a包含类型值的所有类型的搜索树a,以及许多其他类型的搜索树可以想到.

  • T必须满足的另一个属性是,如果你有一个类型a -> b的函数(元素上的函数),那么你必须能够在集合上获取该函数和产品相关函数.您可以使用运算符执行此操作fmap,该运算符由类型类中的每个类型共享Functor.操作符实际上是重载的,所以如果你有一个even类型的函数Int -> Bool,那么

    fmap even
    

    是一个重载函数,可以做很多美妙的事情:

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

    • 将整数树转换为布尔树

    • 转换Nothing到Nothing和Just 7到Just False

    在Haskell中,此属性通过给出以下类型来表示fmap:

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

    我们现在有一个小的t,这意味着" Functor班上的任何类型."

  总而言之,在Haskell中,仿函数是一种集合,如果fmap给你一个元素函数,它将为你提供集合函数.正如您可以想象的那样,这是一个可以被广泛重用的想法,这就是为什么它作为Haskell标准库的一部分而受到祝福的原因.

像往常一样,人们继续发明新的,有用的抽象,你可能想要研究应用函子,最好的参考可能是Conor McBride和Ross Paterson 的一篇名为Applicative Programming with Effects的论文.

Answer 2

这里的其他答案是完整的,但我会尝试另外解释FP使用的仿函数.以此类推:

仿函数是类型a的容器,当受到从a → b映射的函数时,产生类型为b的容器.

与C++中使用的抽象函数指针不同,这里的函子不是函数; 相反,它是在受到功能影响时表现一致的东西.

Answer 3

有三种不同的含义,没有多大关系!

• 在Ocaml中,它是一个参数化模块.见手册.我认为解决它们的最好方法是举例:(写得很快,可能是错误的)

  module type Order = sig
      type t
      val compare: t -> t -> bool
  end;;
  
  
  module Integers = struct
      type t = int
      let compare x y = x > y
  end;;
  
  module ReverseOrder = functor (X: Order) -> struct
      type t = X.t
      let compare x y = X.compare y x
  end;;
  
  (* We can order reversely *)
  module K = ReverseOrder (Integers);;
  Integers.compare 3 4;;   (* this is false *)
  K.compare 3 4;;          (* this is true *)
  
  module LexicographicOrder = functor (X: Order) -> 
    functor (Y: Order) -> struct
      type t = X.t * Y.t
      let compare (a,b) (c,d) = if X.compare a c then true
                           else if X.compare c a then false
                           else Y.compare b d
  end;;
  
  (* compare lexicographically *)
  module X = LexicographicOrder (Integers) (Integers);;
  X.compare (2,3) (4,5);;
  
  module LinearSearch = functor (X: Order) -> struct
      type t = X.t array
      let find x k = 0 (* some boring code *)
  end;;
  
  module BinarySearch = functor (X: Order) -> struct
      type t = X.t array
      let find x k = 0 (* some boring code *)
  end;;
  
  (* linear search over arrays of integers *)
  module LS = LinearSearch (Integers);;
  LS.find [|1;2;3] 2;;
  (* binary search over arrays of pairs of integers, 
     sorted lexicographically *)
  module BS = BinarySearch (LexicographicOrder (Integers) (Integers));;
  BS.find [|(2,3);(4,5)|] (2,3);;
  

您现在可以快速添加许多可能的订单,形成新订单的方式,轻松地对它们进行二进制或线性搜索.通用编程FTW.

• 在像Haskell这样的函数式编程语言中,它意味着可以"映射"的一些类型构造函数(像列表,集合这样的参数化类型).确切地说,一个仿函数f配备了(a -> b) -> (f a -> f b).这起源于范畴论.您链接到的维基百科文章就是这种用法.

  class Functor f where
      fmap :: (a -> b) -> (f a -> f b)
  
  instance Functor [] where      -- lists are a functor
      fmap = map
  
  instance Functor Maybe where   -- Maybe is option in Haskell
      fmap f (Just x) = Just (f x)
      fmap f Nothing = Nothing
  
  fmap (+1) [2,3,4]   -- this is [3,4,5]
  fmap (+1) (Just 5)  -- this is Just 6
  fmap (+1) Nothing   -- this is Nothing
  

所以,这是一种特殊的类型构造函数,与Ocaml中的仿函数几乎没有关系!

• 在命令式语言中,它是指向函数的指针.

Answer 4

在OCaml中,它是一个参数化模块.

如果您了解C++,请将OCaml仿函数视为模板.C++只有类模板,而仿函数在模块规模上工作.

仿函数的一个例子是Map.Make; module StringMap = Map.Make (String);;构建一个使用String-keyed贴图的地图模块.

你只能用多态来实现像StringMap这样的东西; 你需要对键做一些假设.String模块包含完全有序的字符串类型的操作(比较等),而functor将链接String模块包含的操作.你可以用面向对象的编程做类似的事情,但是你有方法间接开销.

Answer 5

你有很多好的答案.我会投入:

在数学意义上,算子是代数上的一种特殊函数.它是一个将代数映射到另一个代数的最小函数."极简"由函子定律表达.

有两种方法可以看待这个.例如,列表是某种类型的仿函数.也就是说,给定类型'a'上的代数,您可以生成包含类型'a'的列表的兼容代数.(例如:将元素带到包含它的单例列表的映射:f(a)= [a])同样,兼容性的概念由函子定律表示.

另一方面,给定一个类型为"a"的仿函数(即,fa是将仿函数f应用于类型a的代数的结果),并且从g:a - > b起作用,我们可以计算一个新的函子F =(fmap g),它将fa映射到f b.简而言之,fmap是F的一部分,它将"functor parts"映射到"functor parts",而g是将"代数部分"映射到"代数部分"的函数的一部分.它需要一个函数,一个函子,一旦完成,它也是一个函子.

似乎不同的语言使用不同的仿函数概念,但它们不是.他们只是在不同的代数上使用函子.OCamls有代数模块,而代数上的函子允许你以"兼容"的方式将新的声明附加到模块.

Haskell仿函数不是类型类.它是一个带有自由变量的数据类型,它满足类型类.如果您愿意深入研究数据类型的内容(没有自由变量),您可以将数据类型重新解释为基础代数上的仿函数.例如:

数据F = F Int

与Ints类同构.因此,作为值构造函数,F是一个将Int映射到F Int(一个等效代数)的函数.它是一个算符.另一方面,你没有在这里免费获得fmap.这就是模式匹配的用途.

函数可以以代数兼容的方式将事物"附加"到代数元素中.

Answer 6

There is a pretty good example in the O'Reilly OCaml book that's on Inria's website (which as of writing this is unfortunately down). I found a very similar example in this book used by caltech: Introduction to OCaml (pdf link). The relevant section is the chapter on functors (Page 139 in the book, page 149 in the PDF).

In the book they have a functor called MakeSet which creates a data structure that consists of a list, and functions to add an element, determine if an element is in the list, and to find the element. The comparison function that is used to determine if it's in/not in the set has been parametrized (which is what makes MakeSet a functor instead of a module).

They also have a module that implements the comparison function so that it does a case insensitive string compare.

使用仿函数和实现比较的模块,他们可以在一行中创建一个新模块:

module SSet = MakeSet(StringCaseEqual);;

这为使用不区分大小写的比较的集合数据结构创建了一个模块.如果您想创建一个使用区分大小写比较的集合,那么您只需要实现一个新的比较模块而不是新的数据结构模块.

Tobu将仿函数与C++中的模板进行了比较,我认为这很容易.

Answer 7

这个问题的最佳答案可以在Brent Yorgey的"Typeclassopedia"中找到.

本期Monad Reader包含对仿函数的精确定义以及其他概念的许多定义以及图表.(Monoid,Applicative,Monad和其他概念在仿函数中被解释和看到).

http://haskell.org/sitewiki/images/8/85/TMR-Issue13.pdf

摘自Typeclassopedia for Functor:"一个简单的直觉是Functor代表某种"容器",以及将函数统一应用于容器中每个元素的能力"

但实际上整个类别数据库都是一个非常容易推荐的强烈推荐的阅读材料.在某种程度上,您可以看到在那里呈现的类型类与对象中的设计模式并行,因为它们为您提供了给定行为或功能的词汇表.

干杯

Answer 8

这是一篇关于编程POV的仿函数的文章,接下来是更具体的编程语言.

仿函数的实际用法是monad,如果你想看的话,你可以在monad上找到很多教程.

Answer 9

鉴于其他答案和我现在要发布的内容,我会说这是一个相当沉重的重载词,但无论如何......

有关Haskell中"functor"一词含义的提示,请询问GHCi:

Prelude> :info Functor
class Functor f where
  fmap :: forall a b. (a -> b) -> f a -> f b
  (GHC.Base.<$) :: forall a b. a -> f b -> f a
        -- Defined in GHC.Base
instance Functor Maybe -- Defined in Data.Maybe
instance Functor [] -- Defined in GHC.Base
instance Functor IO -- Defined in GHC.Base

所以,基本上,Haskell中的仿函数是可以映射的东西.另一种说法是,仿函数可以被视为一个容器,可以被要求使用给定的函数来转换它包含的值; 因而,对于列表,fmap重合有map,为Maybe,fmap f (Just x) = Just (f x),fmap f Nothing = Nothing等.

Functor类型类子部分和Functors,Applicative Functors和Monoids of Learn You a Haskell for Great Good这一部分提供了一些关于这个特定概念有用的例子.(总结:很多地方!:-))

请注意,任何monad都可以被视为仿函数,事实上,正如Craig Stuntz指出的那样,最常用的仿函数往往是monad ... OTOH,有时候将类型作为Functor类型类的实例很方便没有麻烦使它成为Monad.(例如,在的情况下ZipList从Control.Applicative上提及的上述网页中的一个.)

Answer 10

在对最高投票答案的评论中,用户魏虎问道:

我理解ML-functors和Haskell-functors,但缺乏将它们联系在一起的洞察力.在理论意义上,这两者之间的关系是什么？

注意:我不知道ML,所以请原谅并纠正任何相关的错误.

我们最初假设我们都熟悉"类别"和"仿函数"的定义.

一个紧凑的答案是"Haskell-functors"是(endo-)仿函数,F : Hask -> Hask而"ML-functors"是仿函数G : ML -> ML'.

在这里,Hask是通过Haskell的类型以及它们之间的功能,并且类似地形成的类别ML和ML'是由ML结构定义的类别.

注意:制作类别存在一些技术问题Hask,但有一些方法可以解决它们.

从类别理论的角度来看,这意味着Hask-functor是FHaskell类型的映射:

data F a = ...

以及fmapHaskell函数的映射:

instance Functor F where
    fmap f = ...

ML几乎是一样的,虽然没有fmap我所知道的规范抽象,所以让我们定义一个:

signature FUNCTOR = sig
  type 'a f
  val fmap: 'a -> 'b -> 'a f -> 'b f
end

这是f地图ML-types和fmap地图ML-functions,所以

functor StructB (StructA : SigA) :> FUNCTOR =
struct
  fmap g = ...
  ...
end

是一个算子F: StructA -> StructB.

Answer 11

粗略概述

在函数式编程中，函子本质上是将普通一元函数（即具有一个参数的函数）提升为新类型变量之间的函数的构造。在普通对象之间编写和维护简单函数并使用函子来提升它们，然后在复杂的容器对象之间手动编写函数要容易得多。另一个优点是只需编写一次普通函数，然后通过不同的函子重复使用它们。

函子的示例包括数组、“也许”和“任一”函子、期货（例如参见https://github.com/Avaq/Fluture）以及许多其他函子。

插图

考虑从名字和姓氏构建完整人名的函数。我们可以将其定义fullName(firstName, lastName)为两个参数的函数，但这不适用于仅处理一个参数的函数的函子。为了补救，我们将所有参数收集在一个对象中name，该对象现在成为函数的单个参数：

// In JavaScript notation
fullName = name => name.firstName + ' ' + name.lastName

现在如果我们有很多人在一个数组中怎么办？fullName我们可以通过为数组提供的方法来简单地使用map简短的单行代码来重用我们的函数，而不是手动检查列表：

fullNameList = nameList => nameList.map(fullName)

并像这样使用它

nameList = [
    {firstName: 'Steve', lastName: 'Jobs'},
    {firstName: 'Bill', lastName: 'Gates'}
]

fullNames = fullNameList(nameList) 
// => ['Steve Jobs', 'Bill Gates']

只要我们中的每个条目都是提供和属性nameList的对象，这就会起作用。但如果某些对象不存在（甚至根本不是对象）怎么办？为了避免错误并使代码更安全，我们可以将对象包装到类型中（例如https://sanctuary.js.org/#maybe-type）：firstNamelastNameMaybe

// function to test name for validity
isValidName = name => 
    (typeof name === 'object') 
    && (typeof name.firstName === 'string')
    && (typeof name.lastName === 'string')

// wrap into the Maybe type
maybeName = name => 
    isValidName(name) ? Just(name) : Nothing()

其中Just(name)是仅包含有效名称的容器，Nothing()是用于其他所有内容的特殊值。现在，我们不必中断（或忘记）检查参数的有效性，而是可以简单地使用fullName另一行代码重用（提升）原始函数，再次基于该map方法，这次是为 Maybe 类型提供的：

// Maybe Object -> Maybe String
maybeFullName = maybeName => maybeName.map(fullName)

并像这样使用它

justSteve = maybeName(
    {firstName: 'Steve', lastName: 'Jobs'}
) // => Just({firstName: 'Steve', lastName: 'Jobs'})

notSteve = maybeName(
    {lastName: 'SomeJobs'}
) // => Nothing()

steveFN = maybeFullName(justSteve)
// => Just('Steve Jobs')

notSteveFN = maybeFullName(notSteve)
// => Nothing()

范畴论

范畴论中的函子是两个范畴之间关于态射组成的映射。在计算机语言中，主要感兴趣的类别是其对象是类型（某些值集）并且其态射是从一种类型到另一种类型的函数的类别。f:a->bab

例如，将a视为String类型，即bNumber 类型，并将f字符串映射为其长度的函数：

// f :: String -> Number
f = str => str.length

这里a = String表示所有字符串的集合和b = Number所有数字的集合。从这个意义上说， 和a都b代表集合类别中的对象（它与类型类别密切相关，这里的区别并不重要）。在集合范畴中，态射恰好是从第一个集合到第二个集合的所有函数。所以我们这里的长度函数f是从字符串集合到数字集合的态射。

由于我们只考虑集合类别，因此相关函子是将对象发送到对象以及将态射发送到态射的映射，满足某些代数定律。

例子：Array

Array可以意味着很多东西，但只有一件事是函子——类型构造，将类型映射到所有类型数组的a类型。例如，函子将类型映射 到类型（任意长度的字符串数组的集合），并设置类型[a]aArrayString[String]Number到相应的类型[Number]（所有数字数组的集合）。

重要的是不要混淆 Functor 映射

Array :: a => [a]

具有态射a -> [a]. 函子只是将类型映射（关联）a到类型中[a]，就像一件事与另一件事一样。每种类型实际上是一组元素，在这里无关紧要。相反，态射是这些集合之间的实际函数。例如，有一个自然态射（函数）

pure :: a -> [a]
pure = x => [x]

它将一个值发送到 1 元素数组中，并将该值作为单个条目。该功能不是Array！从这个函子的角度来看，pure它只是一个像其他函数一样的函数，没有什么特别的。

另一方面，Array函子有它的第二部分——态射部分。将态射映射f :: a -> b为态射[f] :: [a] -> [b]：

// a -> [a]
Array.map(f) = arr => arr.map(f)

这arr是具有类型 值的任意长度的数组a，并且arr.map(f)是具有类型 值的相同长度的数组b，其条目是应用于f的条目的结果arr。为了使其成为函子，必须满足将恒等映射到恒等以及将组合映射到组合的数学定律，这在本Array例中很容易检查。

Answer 12

“ Functor是对象和形态射影的映射，可以保留类别的组成和标识。”

让我们定义什么是类别？

一堆东​​西！

在一个圆圈内画一些点（目前为2个点，一个为'a'，另一个为'b'），并暂时命名为A（类别）。

类别包含什么？

对象之间的组成以及每个对象的身份功能。

因此，在应用Functor之后，我们必须映射对象并保留构图。

假设'A'是我们的类别，其中包含对象['a'，'b']，并且存在一个态射a-> b

现在，我们必须定义一个函子，该函子可以将这些对象和态射映射到另一个类别“ B”。

假设函子被称为“也许”

data Maybe a = Nothing | Just a

因此，类别“ B”看起来像这样。

请再画一个圆圈，但这次用“也许是a”和“也许是b”代替“ a”和“ b”。

一切似乎都很好，所有对象都已映射

“ a”变成“也许是a”，“ b”变成“也许是b”。

但是问题是我们还必须将态射从“ a”映射到“ b”。

这意味着'A'中的态射a-> b应该映射到射态'Maybe a'->'Maybe b'

a-> b的态射称为f，然后'Maybe a'->'也许b'的射态称为'fmap f'

现在，让我们看看“ f”在“ A”中正在执行的功能，以及是否可以在“ B”中复制它

“ A”中“ f”的功能定义：

f :: a -> b

f取a并返回b

'B'中'f'的函数定义：

f :: Maybe a -> Maybe b

f可能是a，然后可能是b

让我们看看如何使用fmap将函数“ f”从“ A”映射到“ B”中的函数“ fmap f”

fmap的定义

fmap :: (a -> b) -> (Maybe a -> Maybe b)
fmap f Nothing = Nothing
fmap f (Just x) = Just(f x)

那么，我们在这里做什么？

我们正在将函数“ f”应用于类型为“ a”的“ x”。'Nothing'的特殊模式匹配来自的定义Functor Maybe。

因此，我们将对象[a，b]和态射[f]从类别“ A”映射到类别“ B”。

多数民众赞成在Functor！