Na Programação Funcional, o que é um functor?

224

Encontrei o termo 'Functor' algumas vezes enquanto lia vários artigos sobre programação funcional, mas os autores normalmente assumem que o leitor já entende o termo. A pesquisa na web forneceu descrições excessivamente técnicas (consulte o artigo da Wikipedia ) ou descrições incrivelmente vagas (consulte a seção sobre Functors neste site do ocaml-tutorial ).

Alguém pode definir gentilmente o termo, explicar seu uso e talvez fornecer um exemplo de como os Functors são criados e usados?

Edit : Enquanto estou interessado na teoria por trás do termo, estou menos interessado na teoria do que na implementação e uso prático do conceito.

Edit 2 : Parece que existe alguma terminologia cruzada: estou me referindo especificamente aos Functors da programação funcional, não aos objetos de função do C ++.

Erik Forbes
fonte
4
Veja também: adit.io/posts/…
Vlad, o Impala
Boa resposta bonita também: stackoverflow.com/a/45149475/1498178
toraritte
Se você está mais interessado na implementação e no uso prático do que na terminologia e teoria estratosférica por trás do conceito, você só precisa de um argumento: um functor expõe uma função "map".
Richard Gomes
@RichardGomes IMHO Acho que reduz o papel de um functor a uma interface simples semelhante a Java, o que não é. Um functor transforma coisas, cria novos tipos a partir dos existentes (em Haskell), o que significa que os tipos também são mapeados. fmapmapeia as funções. Existem dois tipos de mapeamento envolvidos. Essa maneira de ver as coisas ajudará a entender a teoria das categorias (que é mais geral). Quero dizer, é interessante entender a teoria básica das categorias para nos ajudar com todo o material da teoria das categorias em Haskell (functor, mônadas, ...).
Ludovic Kuty
@VladtheImpala O post do blog é fantástico, mas, mesmo que ajude bastante, gosto de lembrar que um functor cria (mapeia para) outro tipo. Eu particularmente gosto da frase "Um functor F pega cada tipo T e mapeia para um novo tipo FT" nas mônadas são como burritos . IMHO não é apenas um contexto (a caixa) em torno de um valor, mesmo se isso for prático para ver coisas como esta (Haskell PoV vs teoria da categoria PoV?)
Ludovic Kuty

Respostas:

273

A palavra "functor" vem da teoria das categorias, que é um ramo muito geral e muito abstrato da matemática. Foi emprestado por designers de linguagens funcionais de pelo menos duas maneiras diferentes.

  • Na família de idiomas ML, um functor é um módulo que usa um ou mais outros módulos como parâmetro. É considerado um recurso avançado e a maioria dos programadores iniciantes tem dificuldade com isso.

    Como um exemplo de implementação e uso prático, você pode definir sua forma favorita de árvore de pesquisa binária balanceada de uma vez por todas como um functor e tomaria como parâmetro um módulo que fornece:

    • O tipo de chave a ser usada na árvore binária

    • Uma função de pedido total nas teclas

    Depois de fazer isso, você pode usar a mesma implementação de árvore binária equilibrada para sempre. (O tipo de valor armazenado na árvore geralmente é deixado polimórfico - a árvore não precisa olhar outros valores além de copiá-los, enquanto a árvore definitivamente precisa ser capaz de comparar chaves e obtém a função de comparação de o parâmetro do functor.)

    Outra aplicação dos functores de ML é protocolo de rede em camadas . O link é para um artigo realmente fantástico do grupo CMU Fox; mostra como usar functors para criar camadas de protocolo mais complexas (como TCP) em tipos de camadas mais simples (como IP ou mesmo diretamente via Ethernet). Cada camada é implementada como um functor que assume como parâmetro a camada abaixo dela. A estrutura do software realmente reflete a maneira como as pessoas pensam sobre o problema, em oposição às camadas existentes apenas na mente do programador. Em 1994, quando este trabalho foi publicado, foi um grande negócio.

    Para um exemplo selvagem de functores de ML em ação, você pode ver o artigo ML Module Mania , que contém um exemplo publicável (isto é, assustador) de functores em ação. Para obter uma explicação brilhante, clara e plúcida do sistema de módulos ML (com comparações com outros tipos de módulos), leia as primeiras páginas do brilhante artigo POPL de 1994 de Xavier Leroy, Manifest Types, Modules e Compilation Separated .

  • Em Haskell, e em alguma linguagem funcional pura relacionada, Functorhá uma classe de tipo . Um tipo pertence a uma classe de tipo (ou mais tecnicamente, o tipo "é uma instância" da classe de tipo) quando o tipo fornece determinadas operações com determinado comportamento esperado. Um tipo Tpode pertencer à classe Functorse tiver determinado comportamento de coleção:

    • O tipo Té parametrizado em relação a outro tipo, que você deve considerar como o tipo de elemento da coleção. O tipo de coleção completa é, então, algo como T Int, T String, T Bool, se você estiver contendo inteiros, strings, ou Booleans respectivamente. Se o tipo de elemento for desconhecido, ele será gravado como um parâmetro de tipo a , como em T a.

      Os exemplos incluem listas (zero ou mais elementos do tipo a), o Maybetipo (zero ou um elemento do tipo a), conjuntos de elementos do tipo a, matrizes de elementos do tipo a, todos os tipos de árvores de pesquisa que contêm valores do tipo ae muitas outras que você pode pensar.

    • A outra propriedade que Tdeve ser satisfeita é que, se você tem uma função do tipo a -> b(uma função nos elementos), deve poder assumir essa função e produzir uma função relacionada nas coleções. Você faz isso com o operador fmap, que é compartilhado por todos os tipos na Functorclasse type. O operador está realmente sobrecarregado; portanto, se você tiver uma função evencom o tipo Int -> Bool,

      fmap even

      é uma função sobrecarregada que pode fazer muitas coisas maravilhosas:

      • Converter uma lista de números inteiros em uma lista de booleanos

      • Converter uma árvore de números inteiros em uma árvore de booleanos

      • Converter Nothingem Nothinge Just 7paraJust False

      Em Haskell, essa propriedade é expressa fornecendo o tipo de fmap:

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

      onde agora temos um pequeno t, o que significa "qualquer tipo na Functorclasse".

    Para resumir uma longa história, em Haskell, um functor é um tipo de coleção para a qual, se você receber uma função em elementos, fmapretornará uma função em coleções . Como você pode imaginar, essa é uma ideia que pode ser amplamente reutilizada, e é por isso que é abençoada como parte da biblioteca padrão de Haskell.

Como sempre, as pessoas continuam a inventar abstrações úteis e úteis, e talvez você queira investigar functores aplicativos , para os quais a melhor referência pode ser um artigo chamado Programação Aplicativa com Efeitos de Conor McBride e Ross Paterson.

Norman Ramsey
fonte
7
Eu entendo tanto os functores de ML quanto os de Haskell, mas não tenho a percepção necessária para relacioná-los. Qual é a relação entre esses dois, no sentido teórico da categoria?
Wei Hu
6
@ Wei Hu: a teoria das categorias nunca fez nenhum sentido para mim. O melhor que posso dizer é que todas as três noções envolvem mapeamento.
Norman Ramsey
16
De acordo com este wiki da Haskell: en.wikibooks.org/wiki/Haskell/Category_theory , é assim: Uma categoria é uma coleção de objetos e morfismos (funções), onde os morfismos são de objetos em uma categoria para outros objetos nessa categoria . Um functor é uma função que mapeia objetos e morfismos de uma categoria para objetos e morfismos em outra. Pelo menos é assim que eu entendo. O que isso significa exatamente para a programação que ainda tenho que entender.
paul
5
@ norman-ramsey, você já viu a Matemática Conceitual de Lawvere e Schanuel? Sou um novato na área, mas o livro é eminentemente legível e - ouso dizer - agradável. (Amei a sua explicação.)
Ram Rajamony
2
then you have to be able to take that function and product a related function on collectionsVocê quis dizer em producevez de product?
problemaofficer
64

Outras respostas aqui estão completas, mas tentarei outra explicação sobre o uso do functor por FP . Tome isso como analogia:

Um functor é um contêiner do tipo a que, quando sujeito a uma função que mapeia de ab , gera um contêiner do tipo b .

Diferente do uso do ponteiro de função abstraída em C ++, aqui o functor não é a função; pelo contrário, é algo que se comporta consistentemente quando sujeito a uma função .

seh
fonte
3
Um contêiner do tipo b significa "o mesmo tipo de contêiner que o contêiner de entrada, mas agora preenchido com b's". Portanto, se tivermos uma lista de bananas e mapearmos uma função que pega uma banana e produz uma salada de frutas, agora temos uma lista de saladas de frutas. Da mesma forma, se tivéssemos uma árvore de bananas e mapeamos a mesma função, agora teríamos uma árvore de maçãs. Etc. árvore e lista são dois Functors aqui.
Qqwy
3
"Um functor é um contêiner do tipo a que, quando submetido a uma função" - na verdade é o contrário - a função (morfismo) está sujeita a um functor, para ser mapeada para outro morfismo
Dmitri Zaitsev
38

Existem três significados diferentes, não muito relacionados!

  • No Ocaml, é um módulo parametrizado. Veja o manual . Eu acho que a melhor maneira de grok-los é pelo exemplo: (escrito rapidamente, pode ser buggy)

    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);;

Agora você pode adicionar rapidamente muitos pedidos possíveis, formas de formar novos pedidos, fazer uma pesquisa binária ou linear facilmente sobre eles. Programação genérica FTW.

  • Em linguagens de programação funcional como Haskell, significa alguns construtores de tipos (tipos parametrizados como listas, conjuntos) que podem ser "mapeados". Para ser mais preciso, um functor festá equipado com (a -> b) -> (f a -> f b). Isso tem origens na teoria das categorias. O artigo da Wikipedia ao qual você vinculou é esse uso.

    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

Portanto, esse é um tipo especial de construtor de tipos e tem pouco a ver com functors no Ocaml!

  • Em linguagens imperativas, é um ponteiro para funcionar.
sdcvvc
fonte
O <q> mapa </q> nas últimas 3 linhas deste comentário não deveria ser de fato <q> fmap </q>?
imz - Ivan Zakharyaschev
1
Eu sempre li que functores são contêineres - mas isso é apenas uma pobre simplificação. Sua resposta finalmente forneceu o link ausente: Functors são uma classe de tipo (restrição de tipo) para tipos parametrizados (construtores de tipo). É simples assim!
16

No OCaml, é um módulo parametrizado.

Se você conhece C ++, pense em um functor OCaml como um modelo. O C ++ possui apenas modelos de classe e os functores funcionam na escala do módulo.

Um exemplo de functor é Map.Make; module StringMap = Map.Make (String);;cria um módulo de mapa que funciona com mapas com chave de seqüência de caracteres.

Você não poderia conseguir algo como o StringMap apenas com polimorfismo; você precisa fazer algumas suposições sobre as chaves. O módulo String contém as operações (comparação, etc) em um tipo de string totalmente ordenado, e o functor será vinculado às operações que o módulo String contém. Você poderia fazer algo semelhante com a programação orientada a objetos, mas teria uma sobrecarga indireta de método.

Tobu
fonte
Eu peguei isso no site da ocaml - mas não entendo qual seria o uso de um módulo parametrizado.
Erik Forbes
4
@ Kornel Sim, o que eu descrevi é um conceito OCaml. O outro conceito é apenas "valor funcional", o que não é nada particular no FP. @ Erik eu expandi um pouco, mas os documentos de referência são lentos para carregar.
Tobu
13

Você obteve algumas boas respostas. Vou abordar:

Um functor, no sentido matemático, é um tipo especial de função em uma álgebra. É uma função mínima que mapeia uma álgebra para outra álgebra. "Minimalidade" é expressa pelas leis do functor.

Existem duas maneiras de ver isso. Por exemplo, listas são functors sobre algum tipo. Ou seja, dada uma álgebra sobre um tipo 'a', você pode gerar uma álgebra compatível de listas contendo itens do tipo 'a'. (Por exemplo: o mapa que leva um elemento a uma lista de singleton que o contém: f (a) = [a]) Novamente, a noção de compatibilidade é expressa pelas leis do functor.

Por outro lado, dado um functor f "sobre" um tipo a, (isto é, fa é o resultado da aplicação do functor f à álgebra do tipo a), e função de g: a -> b, podemos calcular um novo functor F = (fmap g) que mapeia fa a f b. Em resumo, fmap é a parte de F que mapeia "partes de functor" para "partes de functor", eg é a parte da função que mapeia "partes de álgebra" para "partes de álgebra". É preciso uma função, um functor e, uma vez concluído, também é um functor.

Pode parecer que idiomas diferentes estão usando noções diferentes de functores, mas não estão. Eles estão apenas usando functores em diferentes álgebras. O OCamls possui uma álgebra de módulos, e os functores dessa álgebra permitem anexar novas declarações a um módulo de maneira "compatível".

Um functor Haskell NÃO é uma classe de tipo. É um tipo de dados com uma variável livre que satisfaz a classe de tipo. Se você estiver disposto a se aprofundar em um tipo de dados (sem variáveis ​​livres), poderá reinterpretar um tipo de dados como um functor em uma álgebra subjacente. Por exemplo:

dados F = F Int

é isomórfico para a classe de Ints. Portanto, F, como construtor de valor, é uma função que mapeia Int para F Int, uma álgebra equivalente. É um functor. Por outro lado, você não recebe o fmap gratuitamente aqui. É para isso que serve a correspondência de padrões.

Functors são bons para "anexar" coisas a elementos de álgebras, de maneira algebricamente compatível.

user276631
fonte
8

A melhor resposta para essa pergunta é encontrada em "Typeclassopedia", de Brent Yorgey.

Esta edição do Monad Reader contém uma definição precisa do que é um functor, além de muitas definições de outros conceitos e um diagrama. (Monóide, Aplicativo, Mônada e outros conceitos são explicados e vistos em relação a um functor).

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

trecho da Typeclassopedia for Functor: "Uma intuição simples é que um Functor representa um" contêiner "de algum tipo, juntamente com a capacidade de aplicar uma função de maneira uniforme a todos os elementos do contêiner"

Mas, na verdade, toda a tipografia é uma leitura altamente recomendada e surpreendentemente fácil. De certa forma, você pode ver a classe de tipo apresentada lá como um paralelo ao padrão de design no objeto, no sentido em que fornece um vocabulário para determinado comportamento ou capacidade.

Felicidades

JFT
fonte
7

Há um bom exemplo no livro O'Reilly OCaml, que está no site da Inria (que, infelizmente, está escrito abaixo). Encontrei um exemplo muito semelhante neste livro usado pela caltech: Introdução ao OCaml (link em pdf) . A seção relevante é o capítulo sobre functores (página 139 no livro, página 149 no PDF).

No livro, eles têm um functor chamado MakeSet, que cria uma estrutura de dados que consiste em uma lista e funções para adicionar um elemento, determinar se um elemento está na lista e encontrar o elemento. A função de comparação usada para determinar se está no / não no conjunto foi parametrizada (que é o que torna o MakeSet um functor em vez de um módulo).

Eles também têm um módulo que implementa a função de comparação para fazer uma comparação de cadeias sem distinção entre maiúsculas e minúsculas.

Usando o functor e o módulo que implementa a comparação, eles podem criar um novo módulo em uma linha:

module SSet = MakeSet(StringCaseEqual);;

que cria um módulo para uma estrutura de dados definida que usa comparações sem distinção entre maiúsculas e minúsculas. Se você quisesse criar um conjunto que usasse comparações com distinção entre maiúsculas e minúsculas, seria necessário implementar um novo módulo de comparação em vez de um novo módulo de estrutura de dados.

Tobu comparou os functores aos modelos em C ++, o que eu acho bastante adequado.

Niki Yoshiuchi
fonte
6

Dadas as outras respostas e o que vou postar agora, eu diria que é uma palavra bastante sobrecarregada, mas de qualquer maneira ...

Para uma dica sobre o significado da palavra 'functor' em Haskell, pergunte ao 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

Então, basicamente, um functor em Haskell é algo que pode ser mapeado. Outra maneira de dizer isso é que um functor é algo que pode ser considerado como um contêiner que pode ser solicitado a usar uma determinada função para transformar o valor que ele contém; Assim, para as listas, fmapcoincide com map, para Maybe, fmap f (Just x) = Just (f x), fmap f Nothing = Nothingetc.

A subseção de classe de tipo Functor e a seção Functors, Functors Aplicable e Monoids of Learn You a Haskell for Great Good fornecem alguns exemplos de onde esse conceito específico é útil. (Um resumo: muitos lugares! :-))

Observe que qualquer mônada pode ser tratada como um functor e, de fato, como Craig Stuntz salienta, os functores mais usados ​​tendem a ser mônadas ... OTOH, às vezes é conveniente fazer de um tipo uma instância da classe de tipo Functor sem se dar ao trabalho de torná-la uma mônada. (Por exemplo, no caso de ZipListfrom Control.Applicative, mencionado em uma das páginas mencionadas acima .)

Michał Marczyk
fonte
5

Aqui está um artigo sobre functores de um POV de programação , seguido mais especificamente de como eles aparecem em linguagens de programação .

O uso prático de um functor está em uma mônada, e você pode encontrar muitos tutoriais sobre mônadas, se procurar por isso.

Craig Stuntz
fonte
1
"O uso prático de um functor está em uma mônada" - não apenas. Todas as mônadas são functores, mas há muitos usos para functores não-mônad.
Amndfv 06/04
1
Eu diria que estudar mônadas para usar functores é como economizar para um Rolls comprar mantimentos.
Marco Faustinelli
5

Em um comentário à resposta mais votada , o usuário Wei Hu pergunta:

Entendo tanto os functores ML como os Haskell-functors, mas não tenho o discernimento para relacioná-los. Qual é a relação entre esses dois, no sentido teórico da categoria?

Nota : Como não conheço o ML, perdoe e corrija os erros relacionados.

Vamos inicialmente assumir que todos estamos familiarizados com as definições de 'categoria' e 'functor'.

Uma resposta compacta seria que "Haskell-functors" são (endo-) functores F : Hask -> Haskenquanto "ML-functors" são functores G : ML -> ML'.

Aqui, Haské a categoria formada pelos tipos e funções de Haskell entre eles, e da mesma forma MLe ML'são categorias definidas pelas estruturas de ML.

Nota : Existem alguns problemas técnicos na criação de Haskuma categoria, mas existem maneiras de contorná-los.

De uma perspectiva teórica da categoria, isso significa que um Hask-functor é um mapa Fdos tipos Haskell:

data F a = ...

junto com um mapa fmapdas funções Haskell:

instance Functor F where
    fmap f = ...

O ML é praticamente o mesmo, embora não exista fmapabstração canônica , então vamos definir um:

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

São fmapas ML-types e fmapmaps ML-functions, então

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

é um functor F: StructA -> StructB.

Ncat
fonte
5

"Functor é o mapeamento de objetos e morfismos que preserva a composição e a identidade de uma categoria".

Vamos definir o que é uma categoria?

É um monte de objetos!

Desenhe alguns pontos (por enquanto 2 pontos, um é 'a' outro é 'b') dentro de um círculo e nomeie esse círculo A (Categoria) por enquanto.

O que a categoria contém?

Composição entre objetos e função Identidade para cada objeto.

Portanto, temos que mapear os objetos e preservar a composição após aplicar nosso Functor.

Vamos imaginar que 'A' é a nossa categoria que possui objetos ['a', 'b'] e existe um morfismo a -> b

Agora, temos que definir um functor que possa mapear esses objetos e morfismos em outra categoria 'B'.

Vamos dizer que o functor é chamado de 'Talvez'

data Maybe a = Nothing | Just a

Portanto, a categoria 'B' se parece com isso.

Desenhe outro círculo, mas desta vez com 'Talvez a' e 'Talvez b' em vez de 'a' e 'b'.

Tudo parece bom e todos os objetos são mapeados

'a' se tornou 'Talvez a' e 'b' se tornou 'Talvez b'.

Mas o problema é que temos que mapear o morfismo de 'a' para 'b' também.

Isso significa que o morfismo a -> b em 'A' deve ser mapeado para o morfismo 'Talvez a' -> 'Talvez b'

o morfismo de a -> b é chamado f, então o morfismo de 'Talvez a' -> 'Talvez b' é chamado de 'fmap f'

Agora vamos ver qual função 'f' estava executando em 'A' e ver se podemos replicá-la em 'B'

definição de função de 'f' em 'A':

f :: a -> b

f pega ae retorna b

definição de função de 'f' em 'B':

f :: Maybe a -> Maybe b

f pega Talvez ae retorna Talvez b

vamos ver como usar o fmap para mapear a função 'f' de 'A' para a função 'fmap f' em 'B'

definição de fmap

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

Então o que estamos fazendo aqui ?

Estamos aplicando a função 'f' a 'x', que é do tipo 'a'. A correspondência de padrão especial de 'Nothing' vem da definição de Functor Maybe.

Assim, mapeamos nossos objetos [a, b] e morfismos [f] da categoria 'A' para a categoria 'B'.

Isso é Functor!

insira a descrição da imagem aqui

Sumanth Kumar Mora
fonte
Resposta interessante. Desejo complementá-lo com mônadas. São como burritos (resposta engraçada para abstração, intuição e a “falácia tutorial da mônada” ) e sua frase "Um functor F pega cada tipo T e mapeia-o para um novo tipo FT", também conhecido como construtor de tipos . Programação Funcional e Teoria das Categorias - Categorias e Functors também foram úteis.
Ludovic Kuty
3

Visão geral aproximada

Na programação funcional, um functor é essencialmente uma construção de elevação de funções unárias comuns (isto é, aquelas com um argumento) para funções entre variáveis ​​de novos tipos. É muito mais fácil escrever e manter funções simples entre objetos simples e usar functors para levantá-los e depois escrever funções manualmente entre objetos contêineres complicados. Outra vantagem é escrever funções simples apenas uma vez e depois reutilizá-las através de diferentes functores.

Exemplos de functores incluem matrizes, "talvez" e "qualquer" functores, futuros (consulte, por exemplo, https://github.com/Avaq/Fluture ) e muitos outros.

Ilustração

Considere a função que constrói o nome completo da pessoa a partir do nome e sobrenome. Poderíamos defini-lo como fullName(firstName, lastName)função de dois argumentos, que, no entanto, não seriam adequados para functores que lidam apenas com funções de um argumento. Para remediar, coletamos todos os argumentos em um único objeto name, que agora se torna o único argumento da função:

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

Agora, e se tivermos muitas pessoas em uma matriz? Em vez de revisar manualmente a lista, podemos simplesmente reutilizar nossa função fullNameatravés do mapmétodo fornecido para matrizes com uma única linha de código curta:

fullNameList = nameList => nameList.map(fullName)

e use-o como

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

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

Isso funcionará, sempre que cada entrada no nosso nameListfor um objeto que fornece propriedades firstNamee tanto lastName. Mas e se alguns objetos não o fizerem (ou nem sequer são objetos)? Para evitar os erros e tornar o código mais seguro, podemos agrupar nossos objetos no Maybetipo (por exemplo, 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()

onde Just(name)é um contêiner que contém apenas nomes válidos e Nothing()é o valor especial usado para todo o resto. Agora, em vez de interromper (ou esquecer) para verificar a validade de nossos argumentos, podemos simplesmente reutilizar (elevar) nossa fullNamefunção original com outra linha de código única, baseada novamente no mapmétodo, desta vez fornecido para o tipo Maybe:

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

e use-o como

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

Teoria da categoria

Um Functor na Teoria da Categoria é um mapa entre duas categorias, respeitando a composição de seus morfismos. Em uma linguagem de computador , a principal categoria de interesse é aquela cujos objetos são tipos (determinados conjuntos de valores) e cujos morfismos são funções f:a->bde um tipo apara outro tipo b.

Por exemplo, considere aser o Stringtipo, bo tipo Number e fé a função que mapeia uma sequência em seu comprimento:

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

Aqui a = Stringrepresenta o conjunto de todas as strings e b = Numbero conjunto de todos os números. Nesse sentido, ambos ae brepresentam objetos na Categoria de conjunto (que está intimamente relacionada à categoria de tipos, com a diferença aqui não essencial). Na categoria de conjuntos, os morfismos entre dois conjuntos são precisamente todas as funções do primeiro conjunto ao segundo. Portanto, nossa função de comprimento faqui é um morfismo do conjunto de cordas para o conjunto de números.

Como consideramos apenas a categoria definida, os Functors relevantes a partir dela são mapas que enviam objetos a objetos e morfismos a morfismos, que satisfazem certas leis algébricas.

Exemplo: Array

Arraypode significar muitas coisas, mas apenas uma coisa é um Functor - a construção de tipo, mapeando um tipo ano tipo [a]de todas as matrizes do tipo a. Por exemplo, o Arrayfunctor mapeia o tipo String para o tipo [String](o conjunto de todas as matrizes de cadeias de comprimento arbitrário) e define o tipo Numberpara o tipo correspondente [Number](o conjunto de todas as matrizes de números).

É importante não confundir o mapa do Functor

Array :: a => [a]

com um morfismo a -> [a]. O functor simplesmente mapeia (associa) o tipo ano tipo [a]como uma coisa para outra. Que cada tipo é realmente um conjunto de elementos, não tem relevância aqui. Por outro lado, um morfismo é uma função real entre esses conjuntos. Por exemplo, existe um morfismo natural (função)

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

que envia um valor para a matriz de 1 elemento com esse valor como entrada única. Essa função não faz parte do ArrayFunctor! Do ponto de vista desse functor, pureé apenas uma função como outra qualquer, nada de especial.

Por outro lado, o ArrayFunctor tem sua segunda parte - a parte do morfismo. Que mapeia um morfismo f :: a -> bem um morfismo [f] :: [a] -> [b]:

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

Aqui arrestá qualquer matriz de comprimento arbitrário com valores do tipo ae arr.map(f)é a matriz do mesmo comprimento com valores do tipo b, cujas entradas são resultados da aplicação fàs entradas de arr. Para torná-lo um functor, as leis matemáticas do mapeamento de identidade para identidade e de composições para composições devem ser válidas, que são fáceis de verificar neste Arrayexemplo.

Dmitri Zaitsev
fonte
2

Não para contradizer as respostas teóricas ou matemáticas anteriores, mas um Functor também é um Objeto (em uma linguagem de programação Orientada a Objetos) que possui apenas um método e é efetivamente usado como uma função.

Um exemplo é a interface Runnable em Java, que possui apenas um método: run.

Considere este exemplo, primeiro em Javascript, que possui funções de primeira classe:

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

Saída: [1, 4, 25, 100]

O método map pega uma função e retorna uma nova matriz, com cada elemento sendo o resultado da aplicação dessa função ao valor na mesma posição na matriz original.

Para fazer a mesma coisa que o Java, usando um Functor, você primeiro precisa definir uma interface, digamos:

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

Em seguida, se você adicionar uma classe de coleção que possui uma função de mapa, poderá:

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

Isso usa uma subclasse in-line de IntMapFunction para criar um Functor, que é o equivalente de OO da função do exemplo anterior de JavaScript.

O uso de Functors permite aplicar técnicas funcionais em uma linguagem OO. Obviamente, algumas linguagens OO também têm suporte para funções diretamente, portanto, isso não é necessário.

Referência: http://en.wikipedia.org/wiki/Function_object

Kevin Greer
fonte
Na verdade, "objeto de função" não é uma descrição correta de um functor. Por exemplo, Arrayé um functor, mas Array(value)fornece apenas matrizes de 1 elemento.
Dmitri Zaitsev
0

BEIJO: Um functor é um objeto que possui um método de mapa.

As matrizes no JavaScript implementam o mapa e, portanto, são functores. Promessas, fluxos e árvores geralmente implementam o mapa em linguagens funcionais e, quando o fazem, são considerados functores. O método map do functor pega seu próprio conteúdo e transforma cada um deles usando o retorno de chamada de transformação passado para mapear e retorna um novo functor, que contém a estrutura como o primeiro functor, mas com os valores transformados.

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

soundyogi
fonte
1
Com a observação lateral, 'objeto' deve ser tomado de maneira muito ampla e significa apenas 'algo'. Para idiomas OOP, por exemplo, substitua objeto por classe . Pode-se dizer 'um functor é uma classe que implementa a interface Functor' (é claro que essa interface pode não estar fisicamente lá, mas você pode elevar a lógica do 'map' para essa interface e ter todas as suas classes mapeadas compartilhadas) - desde que o seu sistema de digitação permita digitar coisas dessa maneira geral).
Qqwy
1
Acho as Classes super confusas para ser honesta, de um lado elas são apenas um modelo para algo concreto / mas também podem ter métodos (coisas estáticas) e podem se comportar como objetos. A classe implementa a interface ou a instância que cria?
soundyogi
1
Sim, eles podem ser confusos. Mas: As classes implementam interfaces (elas 'preenchem' os espaços em branco que foram dados nos métodos de interfaces. Em outras palavras: elas transformam as diretrizes abstratas da interface em uma diretriz concreta que pode ser instantaneamente perdoada pelo trocadilho). Quanto a 'classes se comportam como objetos': em linguagens verdadeiramente OOP como Ruby, Classes são instâncias da classe 'Class'. São tartarugas até o fim.
precisa
ArrayA construção de tipo define um único functor. Suas instâncias também são chamadas de "matrizes", mas não são functores. A descrição aqui deve ser mais precisa.
Dmitri Zaitsev
@DmitriZaitsev Você poderia elaborar? Então, o que você está dizendo é que instâncias não são functores? Não vejo sentido nisso, já que você obtém um novo functor mapeando um.
Soundyogi
-4

Na prática, functor significa um objeto que implementa o operador de chamada em C ++. No ocaml, acho que functor se refere a algo que recebe um módulo como entrada e gera outro módulo.

feng
fonte
-6

Simplificando, um functor, ou objeto de função, é um objeto de classe que pode ser chamado como uma função.

Em C ++:

É assim que você escreve uma função

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

É assim que você escreve um functor

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

Agora você pode fazer isso:

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

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

O que os torna tão bons é que você pode manter o estado na classe - imagine se você quiser perguntar a uma função quantas vezes ela foi chamada. Não há como fazer isso de maneira organizada e encapsulada. Com um objeto de função, é como qualquer outra classe: você teria alguma variável de instância na qual incrementa operator ()e algum método para inspecionar essa variável, e tudo ficará bem como desejar.

Matt
fonte
12
Não, esses functores não são a noção de teoria de tipos usada pelas linguagens FP.
Tobu
1
Eu posso ver como alguém poderia provar que FunctorClasscumpre a primeira Lei de Functor, mas você poderia esboçar uma prova para a segunda Lei? Eu não vejo isso direito.
Jörg W Mittag
3
Bah, vocês estão certos. Fiz uma tentativa de resolver a "web forneceu descrições extremamente técnicas" e superei, tentando evitar: "Na família de idiomas ML, um functor é um módulo que usa um ou mais outros módulos como parâmetro". Essa resposta, no entanto, é ruim. Simplificado demais e subespecificado. Estou tentado a ragedelete-lo, mas vou deixar para as gerações futuras para agitar suas cabeças em :)
Matt
Fico feliz que você tenha deixado a resposta e os comentários, porque isso ajuda a enquadrar o problema. Obrigado! Estou tendo problemas, pois a maioria das respostas está escrita em termos de Haskell ou OCaml, e para mim é um pouco como explicar jacarés em termos de crocodilos.
11444 Rob
-10

O Functor não está especificamente relacionado à programação funcional. É apenas um "ponteiro" para uma função ou algum tipo de objeto, que pode ser chamado como seria uma função.

alemjerus
fonte
8
Existe um conceito específico de FP de um functor (da teoria das categorias), mas você está certo de que a mesma palavra também é usada para outras coisas em linguagens não-FP.
Craig Stuntz
Tem certeza de que os ponteiros de função são Functors? Não vejo como os indicadores de função cumprem as duas Leis de Functor, especialmente a Segunda Lei de Functor (preservação da composição do morfismo). Você tem uma prova disso? (Apenas um esboço.)
Jörg W Mittag