首页 文章

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

提问于
浏览
209

我在阅读各种关于函数式编程的文章时,曾几次尝试Functor,但作者通常认为读者已经理解了这个术语 . 在网上浏览提供了过多的技术说明(请参阅Wikipedia article)或令人难以置信的模糊描述(请参阅此处ocaml-tutorial website上的Functors部分) .

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

Edit :虽然我对这个术语背后的理论很感兴趣,但我对这个理论的兴趣不如我对该概念的实施和实际应用 .

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

17 回答

  • 5

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

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

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

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

    • 键上的总排序功能

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

    ML仿函数的另一个应用是layered network protocols . 这个链接是CMU Fox集团的一篇非常棒的论文;它展示了如何使用仿函数在更简单的层(如IP或甚至直接在以太网上)上构建更复杂的协议层(如TCP) . 每个图层都实现为一个仿函数,它将下面的图层作为参数 . 软件的结构实际上反映了人们对问题的思考方式,而不是仅存在于程序员心中的层 . 1994年这项工作发表时,这是一个大问题 .

    对于一个疯狂的ML仿函数实例,你可以看到论文ML Module Mania,其中包含一个可发布的(即可怕的)仿函数的例子 . 有关ML模块系统的精彩,清晰,透明的解释(与其他类型的模块进行比较),请阅读Xavier Leroy辉煌的1994年POPL论文的前几页Manifest Types, Modules, and Separate Compilation .

    • 在Haskell中,以及在一些相关的纯函数式语言中, Functor 是一个类型类 . 当类型提供具有某些预期行为的某些操作时,类型属于类型类(或者更具技术性,类型为"is an instance of"类型类) . 类型 T 如果具有某些类似集合的行为,则属于类 Functor

    • 类型 T 参数化为另一种类型,您应该将其视为集合的元素类型 . 如果您分别包含整数,字符串或布尔值,那么完整集合的类型就像 T IntT StringT Bool . 如果元素类型未知,则将其写为类型参数 a ,如 T a .

    示例包括列表(类型为 a 的零个或多个元素), Maybe 类型(类型为 a 的零个或一个元素),类型为 a 的元素集,类型为 a 的元素数组,包含类型 a 的值的所有类型的搜索树,还有很多你能想到的 .

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

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

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

    • 转换a整数树到布尔树

    • Nothing 转换为 Nothing 并将 Just 7 转换为 Just False

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

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

    我们现在有一个小 t ,这意味着“ Functor 类中的任何类型” .

    长话短说,在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 . 正如您可以想象的那样,这是一个可以被广泛重用的想法,这就是为什么它作为Haskell标准库的一部分而受到祝福的原因 .

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

  • 35

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

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

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

  • -4

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

    • 在Ocaml中,它是一个参数化模块 . 见manual . 我认为解决它们的最好方法是举例:(写得很快,可能是错误的)
    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这样的函数式编程语言中,它意味着某些类型构造函数(参数化类型,如列表,集合)可以是"mapped" . 确切地说,一个仿函数 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中的仿函数几乎没有关系!

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

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

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

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

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

  • 2

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

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

    有两种方法可以看待这个 . 例如,列表是某种类型的仿函数 . 也就是说,给定类型'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 . 那是什么样的模式匹配 .

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

  • 15

    在Inria的网站上有一个非常好的例子(不幸的是,写这篇文章的时候很少) . 我在caltech使用的这本书中找到了一个非常相似的例子:Introduction to OCaml (pdf link) . 相关部分是关于仿函数的章节(本书的第139页,PDF中的第149页) .

    在本书中,他们有一个名为MakeSet的仿函数,它创建一个由列表组成的数据结构,以及添加元素,确定元素是否在列表中以及查找元素的函数 . 用于确定它是否在集合中的比较函数已被参数化(这使得MakeSet成为仿函数而不是模块) .

    它们还有一个实现比较功能的模块,以便它进行不区分大小写的字符串比较 .

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

    module SSet = MakeSet(StringCaseEqual);;
    

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

    Tobu将仿函数与C中的模板进行了比较,我觉得这很简单 .

  • -10

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

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

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

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

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

    干杯

  • 5

    这是一个article on functors from a programming POV,后面是更具体的how they surface in programming languages .

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

  • 7

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

    有关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中的仿函数是可以映射的东西 . 另一种说法是,仿函数可以被视为一个容器,可以被要求使用给定的函数来转换它包含的值;因此,对于列表, fmapmapMaybefmap f (Just x) = Just (f x)fmap f Nothing = Nothing 等重合 .

    The Functor typeclass分节和Functors, Applicative Functors and MonoidsLearn You a Haskell for Great Good部分给出了一些这个特定概念有用的例子 . (总结:很多地方!:-))

    请注意,任何monad都可以被视为仿函数,事实上,正如Craig Stuntz指出的那样,最常用的仿函数往往是monad ... OTOH,有时候将类型作为Functor类型类的实例很方便没有麻烦使它成为Monad . (例如, ZipList 来自 Control.Applicative ,在one of the aforementioned pages上提及 . )

  • 13

    在对最高投票的answer的评论中,用户Wei Hu询问:

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

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

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

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

    这里, Hask 是由Haskell类型和它们之间的函数形成的类别,类似地 MLML' 是由ML结构定义的类别 .

    Note :有一些technical issues使 Hask 成为一个类别,但有很多方法可以解决它们 .

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

    data F a = ...
    

    以及Haskell函数的 Map fmap

    instance Functor F where
        fmap f = ...
    

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

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

    那是 f maps ML -types和 fmap maps ML -functions,所以

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

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

  • 0

    “Functor是对象和态射的映射,它保留了一个类别的构成和身份 . ”

    让我们定义什么是类别?

    这是一堆物品!在圆圈内画一些圆点(现在是2个点,一个是'a',另一个是'b'),现在命名为A(类别) .

    该类别包含什么?

    每个对象的对象和Identity函数之间的组合 .

    因此,我们必须在应用我们的Functor后映射对象并保留合成 .

    让我们想象'A'是我们的类别,它有对象['a','b']并且存在一个态射a - > b

    现在,我们必须定义一个函子,它可以将这些对象和态射映射到另一个类别'B' .

    让我们说仿函数叫'可能'

    data Maybe a = Nothing | Just a
    

    所以,类别'B'看起来像这样 .

    请绘制另一个圆圈,但这次使用'Maybe a'和'Maybe b'而不是'a'和'b' .

    一切似乎都很好,所有的对象都被映射出来

    'a'成为'也许','b'成为'也许b' .

    但问题是我们必须将态射从'a'映射到'b' .

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

    来自a - > b的态射被称为f,然后来自'Maybe a'的态射 - >'也许b'被称为'fmap f'

    现在让我们看看'f'中的'f'函数是什么,看看我们是否可以在'B'中复制它

    'A'中'f'的函数定义:

    f :: a -> b
    

    f取a并返回b

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

    f :: Maybe a -> Maybe b
    

    f需要一个并返回Maybe 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'应用于'x' 11871846 . 'Nothing'的特殊模式匹配来自 Functor Maybe 的定义 .

    因此,我们将对象[a,b]和态射[f]从类别'A'映射到类别'B' .

    那是Functor!

    enter image description here

  • 58

    不要与之前的理论或数学答案相矛盾,但Functor也是一个Object(面向对象的编程语言),它只有一个方法,并且有效地用作函数 .

    一个例子是Java中的Runnable接口,它只有一个方法:run .

    考虑这个例子,首先在Javascript中,它具有一流的功能:

    [1, 2, 5, 10].map(function(x) { return x*x; });
    

    输出:[1,4,25,100]

    map方法接受一个函数并返回一个新数组,每个元素都是该函数应用于原始数组中相同位置的值的结果 .

    要做同样的事情是Java,使用Functor,你首先需要定义一个接口,比如说:

    public interface IntMapFunction {
      public int f(int x);
    }
    

    然后,如果添加具有 Map 功能的集合类,则可以执行以下操作:

    myCollection.map(new IntMapFunction() { public int f(int x) { return x * x; } });
    

    这使用IntMapFunction的内联子类来创建一个Functor,它是早期JavaScript示例中函数的OO等价物 .

    使用Functors,您可以使用OO语言应用功能技术 . 当然,一些OO语言也直接支持函数,因此不需要这样做 .

    参考:http://en.wikipedia.org/wiki/Function_object

  • 260

    粗略概述

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

    仿函数的例子包括数组,"maybe"和"either"仿函数,期货(参见例如https://github.com/Avaq/Fluture)等等 .

    插图

    考虑从名字和姓氏构造完整人名的功能 . 我们可以将它定义为 fullName(firstName, lastName) 作为两个参数的函数,但是它不适用于仅处理一个参数的函数的函子 . 为了补救,我们收集单个对象 name 中的所有参数,现在它们成为函数的单个参数:

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

    如果我们阵列中有很多人呢?我们可以通过 map 方法重新使用我们的函数 fullName ,而不是手动遍历列表 . 具有短单行代码的数组:

    fullNameList = nameList => nameList.map(fullName)
    

    并使用它

    nameList = [
        {firstName: 'Steve', lastName: 'Jobs'},
        {firstName: 'Bill', lastName: 'Gates'}
    ]
    
    fullNames = fullNameList(nameList) 
    // => ['Steve Jobs', 'Bill Gates']
    

    只要我们的 nameList 中的每个条目都是提供 firstNamelastName 属性的对象,这将有效 . 但是如果有些物体完全没有对象呢?为了避免错误并使代码更安全,我们可以将对象包装到 Maybe 类型中(例如https://sanctuary.js.org/#maybe-type):

    // 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()
    

    类别理论

    类别理论中的 Functor 是关于其态射的组成的两个类别之间的映射 . 在计算机语言中,感兴趣的主要类别是 objects 是类型(某些值集合)的类别,其 morphisms 是从一种类型 a 到另一种类型 b 的函数 f:a->b .

    例如,将 a 设为 String 类型, b 为数字类型, f 是将字符串映射到其长度的函数:

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

    这里 a = String 表示所有字符串的集合, b = Number 表示所有数字的集合 . 从这个意义上说, ab 都代表集合类别中的对象(与类型的类别密切相关,差别在这里是不必要的) . 在Set Category中,两组之间的 morphisms 恰好是从第一组到第二组的所有功能 . 所以我们的长度函数 f 这里是从一组字符串到一组数字的态射 .

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

    示例:数组

    Array 可能意味着许多事情,但只有一件事是Functor - 类型构造,将类型 a 映射到 a 类型的所有数组的类型 [a] . 例如, Array 仿函数将类型 String 映射到类型 [String] (任意长度的所有字符串数组的集合),并将类型 Number 设置为相应的类型 [Number] (所有数字数组的集合) .

    重要的是不要混淆Functor Map

    Array :: a => [a]
    

    与态射 a -> [a] . 仿函数只是将类型 a 映射(关联)到 [a] 类型中,作为另一个东西 . 每种类型实际上是一组元素,与此无关 . 相反,态射是这些集合之间的实际函数 . 例如,有一个自然的态射(函数)

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

    它将值作为单个条目发送到1元素数组中 . 该功能是 not Array Functor的一部分!从这个仿函数的角度来看, pure 只是一个像其他任何函数一样的函数,没什么特别的 .

    另一方面, Array Functor有它的第二部分 - 态射部分 . 将态射 f :: a -> b 映射为态射 [f] :: [a] -> [b]

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

    这里 arr 是任意长度的任何数组,其值为 aarr.map(f) 是具有类型 b 的值的相同长度的数组,其条目是将 f 应用于 arr 的条目的结果 . 为了使它成为一个仿函数,必须保持将身份与身份和成分映射到成分的数学定律,这很容易在这个例子中检查 .

  • 2

    KISS:仿函数是一个具有map方法的对象 .

    JavaScript中的数组实现了map,因此是functor . Promises,Streams和Trees经常用函数式语言实现map,当它们这样做时,它们被认为是functor . 仿函数的map方法使用它自己的内容并使用传递给map的转换回调转换它们中的每一个,并返回一个新的仿函数,它包含作为第一个仿函数的结构,但具有转换后的值 .

    src:https://www.youtube.com/watch?v=DisD9ftUyCk&feature=youtu.be&t=76

  • -6

    实际上,functor是指在C中实现调用操作符的对象 . 在ocaml中,我认为仿函数指的是将模块作为输入并输出另一个模块的东西 .

  • 4

    简而言之,仿函数或函数对象是一个类对象,可以像a一样调用功能 .

    在C:

    这是你编写函数的方法

    void foo()
    {
        cout << "Hello, world! I'm a function!";
    }
    

    这就是你编写仿函数的方法

    class FunctorClass
    {
        public:
        void operator ()
        {
            cout << "Hello, world! I'm a functor!";
        }
    };
    

    现在你可以这样做:

    foo(); //result: Hello, World! I'm a function!
    
    FunctorClass bar;
    bar(); //result: Hello, World! I'm a functor!
    

    使这些如此伟大的原因是你可以在课堂上保持状态 - 想象一下你是否想要问一个函数被调用了多少次 . 有's no way to do this in a neat, encapsulated way. With a function object, it'就像任何其他类一样:你有一些实例变量,你在 operator () 中增加了一些方法来检查那个变量,一切都很整齐你随意 .

  • 5

    Functor与函数式编程没有特别的关系 . 它只是一个函数或某种对象的“指针”,可以被称为函数 .

相关问题