En Programación Funcional, ¿qué es un funtor?

Otras respuestas aquí están completas, pero intentaré otra explicación del uso FP de functor. Toma esto como analogía:

Un funtor es un contenedor de tipo a que, cuando está sujeto a una función que mapea desde a→b , produce un contenedor de tipo b.

A diferencia del uso del puntero-función-abstracted en C++, aquí el funtor es no la función; más bien, es algo que se comporta consistentemente cuando se somete a una función .

¡Hay tres significados diferentes, no muy relacionados!

• En Ocaml es un módulo parametrizado. Véase manual . Creo que la mejor manera de grok ellos es por ejemplo: (escrito rápidamente, podría 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);;
  

Ahora puede agregar rápidamente muchas órdenes posibles, formas de formar nuevas órdenes, hacer una búsqueda binaria o lineal fácilmente sobre ellas. Programación genérica FTW.

• En lenguajes de programación funcionales como Haskell, significa algún tipo constructores (tipos parametrizados como listas, conjuntos) que pueden ser "mapeados". Para ser precisos, un funtor f está equipado con (a -> b) -> (f a -> f b). Esto tiene orígenes en la teoría de categorías. El artículo de Wikipedia al que enlazaste es este 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
  

Por lo tanto, este es un tipo especial de constructores de tipo a, y tiene poco que ver con los funtores en Ocaml!

• En lenguajes imperativos, es un puntero a la función.

En OCaml, es un módulo parametrizado.

Si conoce C++, piense en un funtor OCaml como una plantilla. C++ solo tiene plantillas de clase, y los funtores funcionan a escala de módulo.

Un ejemplo de funtor es Map.Make; module StringMap = Map.Make (String);; construye un módulo de mapa que funciona con mapas con claves de cadena.

No se podría lograr algo como StringMap con solo polimorfismo; es necesario hacer algunas suposiciones sobre las claves. El módulo String contiene las operaciones (comparación, etc.) en un tipo de cadena ordenada, y el funtor se enlazará con las operaciones que contiene el módulo de cadena. Podría hacer algo similar con la programación orientada a objetos, pero tendría una sobrecarga de indirección de métodos.

Tienes bastantes buenas respuestas. Echaré una mano:

Un functor, en el sentido matemático, es un tipo especial de función en un álgebra. Es una función mínima que asigna un álgebra a otro álgebra. La "minimalidad" es expresada por las leyes funtor.

Hay dos maneras de ver esto. Por ejemplo, las listas son funtores sobre algún tipo. Es decir, dado un álgebra sobre un tipo' a', puede generar un álgebra compatible de listas que contengan cosas de tipo'a'. (Para ejemplo: el mapa que lleva un elemento a una lista singleton que lo contiene: f (a) = [a]) De nuevo, la noción de compatibilidad se expresa por las leyes del funtor.

Por otro lado, dado un functor f "más de un" tipo a, (es decir, f es el resultado de aplicar el functor f para el álgebra de tipo a), y la función de g: a -> b, se puede calcular un nuevo functor F = (fmap g) que los mapas de f a a f b. En resumen, fmap es la parte de F que asigna "functor partes" a "functor partes", y g es la parte de la función que asigna "partes de álgebra" a "partes de álgebra". Se toma una función, un functor, y una vez completado, ES un functor demasiado.

Puede parecer que diferentes lenguajes están usando diferentes nociones de funtores, pero no lo son. Simplemente están usando funtores sobre diferentes álgebras. OCamls tiene un álgebra de módulos, y los funtores sobre ese álgebra le permiten adjuntar nuevas declaraciones a un módulo de una manera" compatible".

Un funtor de Haskell NO es una clase de tipo. Es un tipo de datos con una variable libre que satisface la clase type. Si está dispuesto a profundizar en las entrañas de un tipo de datos (sin variables libres), puede reinterpretar un tipo de datos como un funtor sobre un álgebra subyacente. Por ejemplo:

Datos F = F Int

Es isomorfo a la clase de Ints. Así que F, como un constructor de valor, es una función que asigna Int a F Int, un álgebra equivalente. Es un functor. Por otro lado, no se obtiene fmap gratis aquí. Eso es lo que es la coincidencia de patrones para.

Los funtores son buenos para "unir" cosas a elementos de álgebras, de una manera algebraicamente compatible.

Hay un buen ejemplo en el libro O'Reilly OCaml que está en el sitio web de Inria (que al momento de escribir esto está desafortunadamente abajo). Encontré un ejemplo muy similar en este libro usado por caltech: Introducción a OCaml (enlace pdf). La sección relevante es el capítulo sobre los funtores (Página 139 en el libro, página 149 en el PDF).

En el libro tienen un funtor llamado MakeSet que crea una estructura de datos que consiste en una lista, y funciones para agregar un elemento, determinar si un elemento está en la lista, y para encontrar el elemento. La función de comparación que se utiliza para determinar si está en/no en el conjunto ha sido parametrizada (que es lo que hace que MakeSet sea un funtor en lugar de un módulo).

También tienen un módulo que implementa la función de comparación para que haga una comparación de cadenas insensible a mayúsculas y minúsculas.

Usando el funtor y el módulo que implementa la comparación pueden crear un nuevo módulo en una línea:

module SSet = MakeSet(StringCaseEqual);;

Que crea un módulo para una estructura de datos de conjunto que utiliza comparaciones insensibles a mayúsculas y minúsculas. Si desea crear un conjunto que utilice comparaciones sensibles a mayúsculas y minúsculas, solo tendrá que implementar un nuevo módulo de comparación en lugar de un nuevo módulo de estructura de datos.

Tobu comparó funtores con plantillas en C++, lo que creo que es bastante adecuado.

La mejor respuesta a esa pregunta se encuentra en "Typeclassopedia" de Brent Yorgey.

Este número de Monad Reader contiene una definición precisa de lo que es un funtor, así como muchas definiciones de otros conceptos, así como un diagrama. (Monoide, Aplicativo, Mónada y otros conceptos se explican y se ven en relación con un funtor).

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

Extracto de Typeclassopedia para Functor: "Una simple intuición es que un Functor representa un "contenedor" de algunos ordenar, junto con la capacidad de aplicar una función de manera uniforme a cada elemento en el contenedor"

Pero realmente toda la typeclassopedia es una lectura muy recomendable que es sorprendentemente fácil. De alguna manera se puede ver la clase de tipo presentada allí como un patrón paralelo al diseño en objeto en el sentido de que le dan un vocabulario para un comportamiento o capacidad dada.

Salud

Aquí hay un artículo sobre funtores de un POV de programación, seguido de más específicamente cómo emergen en los lenguajes de programación.

El uso práctico de un funtor está en una mónada, y puedes encontrar muchos tutoriales sobre mónadas si buscas eso.

Dadas las otras respuestas y lo que voy a publicar ahora, diría que es una palabra bastante sobrecargada, pero de todos modos...

Para una pista con respecto al significado de la palabra 'funtor' en Haskell, pregunte a 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

Así que, básicamente, un funtor en Haskell es algo que se puede mapear. Otra forma de decirlo es que un funtor es algo que puede ser considerado como un contenedor al que se le puede pedir que use una función dada para transformar el valor que contiene; por lo tanto, para las listas, fmap coincide con map, para Maybe, fmap f (Just x) = Just (f x), fmap f Nothing = Nothing etc.

La subsección Functor typeclass y la sección sobre Functors, Functors Aplicativos y Monoides de Learn You a Haskell for Great Good dan algunos ejemplos de donde este concepto particular es útil. (Un resumen: muchos lugares! :-))

Tenga en cuenta que cualquier mónada puede ser tratada como un funtor, y de hecho, como Craig Stuntz señala, los funtores más utilizados tienden a ser mónadas... OTOH, lo es. conveniente a veces para hacer un tipo una instancia de la clase de tipo Funtor sin tener que molestarse en convertirlo en una Mónada. (E. g. in the case of ZipList from Control.Applicative, mentioned on one of the aforementioned pages.)

En un comentario a la respuesta más votada , el usuario Wei Hu pregunta:

Entiendo tanto ML-funtores y Haskell-funtores, pero carecen de la perspicacia para relacionarlos juntos. Cuál es la relación entre estos dos, en un sentido teórico de la categoría?

Nota: No conozco ML, así que por favor perdone y corrija cualquier error relacionado.

Asumamos inicialmente que todos estamos familiarizados con las definiciones de 'categoría' y 'functor'.

Una respuesta compacta sería que "Haskell-functors" son (endo-)functors F : Hask -> Hask mientras que "ML-functors" son functors G : ML -> ML'.

Aquí, Hask es la categoría formada por tipos y funciones de Haskell entre ellos, y de manera similar ML y ML' son categorías definidas por estructuras ML.

Nota: Hay algunos problemas técnicos con hacer Hask una categoría, pero hay maneras alrededor de ellos.

Desde una perspectiva teórica de categorías, este significa que un Hask-funtor es un mapa F de tipos Haskell:

data F a = ...

Junto con un mapa fmap de las funciones de Haskell:

instance Functor F where
    fmap f = ...

ML es más o menos lo mismo, aunque no hay una abstracción canónica fmap de la que sea consciente, así que definamos una:

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

Es decir f mapas ML-tipos y fmap mapas ML-funciones, así que

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

Es un funtor F: StructA -> StructB.

"Funtor es un mapeo de objetos y morfismos que preserva la composición e identidad de una categoría."

Vamos a definir qué es una categoría ?

¡Es un montón de objetos!

Dibuja unos cuantos puntos (por ahora 2 puntos, uno es 'a' otro es 'b') dentro de a círculo y nombre que el círculo A (Categoría) por ahora.

¿Qué contiene la categoría ?

Composición entre objetos y función de identidad para cada objeto.

Así que, tenemos para mapear los objetos y preservar la composición después de aplicar nuestro Funtor.

Imaginemos que' A ' es nuestra categoría que tiene objetos ['a', 'b'] y existe un morfismo a - > b

Ahora, tenemos que definir un funtor que pueda mapear estos objetos y morfismos en otra categoría 'B'.

Digamos que el funtor se llama 'Maybe'

data Maybe a = Nothing | Just a

Entonces, la categoría 'B' se ve así.

Por favor, dibuja otro círculo, pero esta vez con 'Tal vez a' y 'Tal vez b' en lugar de 'a' y 'b'.

Todo parece bueno y todos los objetos están mapeados

'a' se convirtió en 'Tal vez a' y 'b' se convirtió en 'Tal vez b'.

Pero el problema es que tenemos que mapear el morfismo de 'a' a 'b' también.

Eso significa que el morfismo a - > b en' A 'debería mapearse con el morfismo' Maybe a ' - > 'Maybe b'

El morfismo de a - > b se llama f, luego el morfismo de 'Maybe a' -> 'Maybe b' se llama 'fmap f'

Ahora veamos qué función ' f 'estaba haciendo en' A ' y veamos si podemos replicarlo en " B "

Definición de función de ' f ' en 'A':

f :: a -> b

F toma a y devuelve b

Definición de función de ' f ' en 'B':

f :: Maybe a -> Maybe b

F toma Tal vez a y devuelve Tal vez b

Veamos cómo usar fmap para mapear la función ' f ' de ' A 'a la función' fmap f 'en'B'

Definición de fmap

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

Entonces, ¿qué estamos haciendo aquí ?

Estamos aplicando la función 'f' a 'x', que es de tipo 'a'. Coincidencia de patrón especial de' Nada ' viene de la definición de Functor Maybe.

Entonces, mapeamos nuestros objetos [a, b ] y morfismos [ f] de la categoría 'A' a la categoría 'B'.

Eso es Funtor!

No contradice las respuestas teóricas o matemáticas anteriores, sino que un Funtor es también un Objeto (en un lenguaje de programación Orientado a Objetos) que tiene un solo método y se usa efectivamente como función.

Un ejemplo es la interfaz ejecutable en Java, que solo tiene un método: run.

Considere este ejemplo, primero en Javascript, que tiene funciones de primera clase:

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

Salida: [1, 4, 25, 100]

El método map toma una función y devuelve una nueva array con cada elemento siendo el resultado de la aplicación de esa función al valor en la misma posición en el array original.

Para hacer lo mismo es Java, usando un Funtor, primero tendría que definir una interfaz, decir:

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

Entonces, si agrega una clase de colección que tenga una función de mapa, podría hacer:

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

Esto utiliza una subclase en línea de IntMapFunction para crear un Funtor, que es el equivalente OO de la función del JavaScript anterior ejemplo.

El uso de funtores le permite aplicar técnicas funcionales en un lenguaje OO. Por supuesto, algunos lenguajes OO también tienen soporte para funciones directamente, por lo que esto no es necesario.

Referencia: http://en.wikipedia.org/wiki/Function_object

Panorama general

En programación funcional, un functor es esencialmente una construcción de elevación ordinaria unary funciones (es decir, aquellos con un argumento) a funciones entre variables de nuevos tipos. Es mucho más fácil escribir y mantener funciones simples entre objetos simples y usar funtores para levantarlos, luego escribir manualmente funciones entre objetos contenedores complicados. Otra ventaja es escribir funciones simples solo una vez y luego reutilizarlas a través de diferentes funtores.

Los ejemplos de funtores incluyen arrays, "maybe" y "either" functors, futures (véase, por ejemplo, https://github.com/Avaq/Fluture ), y muchos otros.

Ilustración

Considere la función que construye el nombre completo de la persona a partir de los nombres y apellidos. Podríamos definirlo como fullName(firstName, lastName) como función de dos argumentos, lo que sin embargo no sería adecuado para funtores que solo tratan con funciones de un argumento. Para remediar, recogemos todos los argumentos en un único objeto name, que ahora se convierte en el único argumento de la función:

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

Ahora, ¿qué pasa si tenemos muchas personas en una matriz? En lugar de revisar manualmente la lista, simplemente podemos reutilizar nuestra función fullName a través del método map proporcionado para matrices con una sola línea de código corta:

fullNameList = nameList => nameList.map(fullName)

Y usarlo como

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

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

Que funcionará, siempre que cada entrada en nuestro nameList es un objeto que proporciona ambas propiedades firstName y lastName. Pero ¿qué pasa si algunos objetos no (o incluso no son objetos en absoluto)? Para evitar los errores y hacer que el código sea más seguro, podemos envolver nuestros objetos en el tipo Maybe (por ejemplo, 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()

Donde Just(name) es un contenedor que contiene solo nombres válidos y Nothing() es el valor especial utilizado para todo lo demás. Ahora, en lugar de interrumpir (u olvidar) para comprobar la validez de nuestros argumentos, podemos simplemente reutilizar (levantar) nuestra función original fullName con otra sola línea de código, basado de nuevo en el método map, esta vez proporcionado para el tipo Maybe:

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

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

Teoría de categorías

Un Funtor en La Teoría de Categorías es un mapa entre dos categorías respetando la composición de sus morfismos. En un Lenguaje de Computación , la principal Categoría de interés es aquella cuyos objetos son tipos (ciertos conjuntos de valores), y cuyos morfismos son funciones f:a->b de una escriba a a otro tipo b.

Por ejemplo, tome a para ser el tipo String, b el tipo de Número, y f es la función que asigna una cadena a su longitud:

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

Aquí a = String representa el conjunto de todas las cadenas y b = Number el conjunto de todos los números. En ese sentido, tanto a como b representan objetos en la Categoría de Conjunto (que está estrechamente relacionada con la categoría de tipos, con la diferencia que no es esencial aquí). En la Categoría Set, los morfismos entre dos conjuntos son precisamente todas las funciones del primer conjunto al segundo. Así que nuestra función de longitud f aquí es un morfismo del conjunto de cadenas en el conjunto de números.

Como solo consideramos la categoría de conjunto, los Funtores relevantes de ella en sí mismos son mapas que envían objetos a objetos y morfismos a morfismos, que satisfacen ciertas leyes algebraicas.

Ejemplo: Array

Array puede significar muchas cosas, pero solo una cosa es un Funtor construct la construcción type, mapeando un type a en el type [a] de todos los arrays de type a. Por ejemplo, el funtor Array mapea el tipo String en el tipo [String] (el conjunto de todos los arrays de cadenas de longitud arbitraria), y establece el tipo Number en el tipo correspondiente [Number] (el conjunto de todos los arrays de números).

Es importante no confundir el mapa de Funtores

Array :: a => [a]

Con un morfismo a -> [a]. El funtor simplemente mapea (asocia) el tipo a en el tipo [a] como una cosa a otra. Que cada tipo es en realidad un conjunto de elementos, no es de relevancia aquí. En contraste, un morfismo es una función real entre esos conjuntos. Por ejemplo, hay un morfismo natural (función)

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

Que envía un valor al array de 1 elemento con ese valor como entrada única. Esa función es no una parte del Funtor Array! Desde el punto de vista de este funtor, pure es solo una función como cualquier otra, nada especial.

Por otro lado, el Funtor Array tiene su segunda parte the la parte del morfismo. Que mapea un morfismo f :: a -> b en un morfismo [f] :: [a] -> [b]:

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

Aquí arr es cualquier matriz de longitud arbitraria con valores de tipo a, y arr.map(f) es la matriz de la misma longitud con valores de tipo b, cuyas entradas son resultados de aplicar f a las entradas de arr. Para convertirlo en un funtor, las leyes matemáticas de mapear identidad a identidad y composiciones a composiciones must hold, que son fáciles de comprobar en este ejemplo Array.

KISS: Un funtor es un objeto que tiene un método map.

Los arrays en JavaScript implementan map y por lo tanto son funtores. Las promesas, los arroyos y los árboles a menudo implementan map en lenguajes funcionales, y cuando lo hacen, se consideran funtores. El método map del funtor toma su propio contenido y transforma cada uno de ellos usando la devolución de llamada de transformación pasada a map, y devuelve un nuevo funtor, que contiene la estructura como el primer funtor, pero con el transformado valor.

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

En la práctica, functor significa un objeto que implementa el operador de llamada en C++. En ocaml creo que funtor se refiere a algo que toma un módulo como entrada y salida de otro módulo.

En pocas palabras, un funtor, u objeto de función, es un objeto de clase que se puede llamar al igual que una función.

En C++:

Así es como se escribe una función

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

Así es como se escribe un funtor

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

Ahora puedes hacer esto:

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

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

Lo que hace que estos sean tan grandes es que puede mantener el estado en la clase - imagine si desea preguntar a una función cuántas veces se ha llamado. No hay manera de hacer esto de una manera ordenada y encapsulada. Con una función objeto, es como cualquier otra clase: tendrías alguna variable de instancia que incrementas en operator () y algún método para inspeccionar esa variable, y todo está ordenado como quieras.

Functor no está específicamente relacionado con la programación funcional. Es solo un "puntero" a una función o algún tipo de objeto, que se puede llamar como sería una función.