[Functional-Programming] In Programmazione funzionale, cos'è un functor?


Answers

Altre risposte qui sono complete, ma proverò un'altra spiegazione dell'uso FP del functor . Prendi questo come analogia:

Un funtore è un contenitore di tipo a che, se sottoposto a una funzione che mappa da ab , produce un contenitore di tipo b .

Diversamente dall'uso del puntatore a funzioni astratte in C ++, qui il functor non è la funzione; piuttosto, è qualcosa che si comporta in modo coerente quando sottoposto a una funzione .

Question

Ho letto il termine "Functor" alcune volte mentre leggevo vari articoli sulla programmazione funzionale, ma gli autori in genere presuppongono che il lettore comprenda già il termine. Guardare in giro sul web ha fornito descrizioni eccessivamente tecniche (vedi l' articolo di Wikipedia ) o descrizioni incredibilmente vaghe (vedi la sezione su Functors in questo sito di ocaml -tutorial ).

Qualcuno può gentilmente definire il termine, spiegarne l'uso e forse fornire un esempio di come vengono creati e utilizzati i Functional?

Edit : Mentre sono interessato alla teoria alla base del termine, sono meno interessato alla teoria di quanto lo sia io nell'implementazione e nell'uso pratico del concetto.

Modifica 2 : Sembra che ci sia qualche cross-terminoligy in corso: mi riferisco in particolare ai Functional of functional programming, non agli oggetti funzione di C ++.







C'è un bell'esempio nel libro O'Reilly OCaml presente sul sito di Inria (che purtroppo è in fase di scrittura). Ho trovato un esempio molto simile in questo libro usato da caltech: Introduzione a OCaml (link pdf) . La sezione pertinente è il capitolo sui funtori (Pagina 139 nel libro, pagina 149 nel PDF).

Nel libro hanno un functor chiamato MakeSet che crea una struttura di dati che consiste in un elenco e le funzioni per aggiungere un elemento, determinare se un elemento è presente nell'elenco e trovare l'elemento. La funzione di confronto che viene utilizzata per determinare se è in / non nell'insieme è stata parametrizzata (che è ciò che rende MakeSet un functor invece di un modulo).

Hanno anche un modulo che implementa la funzione di confronto in modo che faccia un confronto di stringa insensibile al maiuscolo / minuscolo.

Utilizzando il functor e il modulo che implementa il confronto, è possibile creare un nuovo modulo in una riga:

module SSet = MakeSet(StringCaseEqual);;

crea un modulo per una struttura dati impostata che utilizza confronti tra maiuscole e minuscole. Se si desidera creare un set che utilizza confronti con maiuscole e minuscole, sarà necessario implementare un nuovo modulo di confronto anziché un nuovo modulo della struttura dati.

Tobu ha paragonato i funtori ai modelli in C ++ che penso sia abbastanza adatto.




In un commento alla answer votata, l'utente Wei Hu chiede:

Capisco sia i funtori ML sia i funtori Haskell, ma manca l'intuizione per metterli insieme. Qual è la relazione tra questi due, in un senso teorico di categoria?

Nota : non conosco ML, quindi ti preghiamo di perdonare e correggere eventuali errori correlati.

Inizialmente assumiamo che tutti noi conosciamo le definizioni di "categoria" e "functor".

Una risposta compatta sarebbe che "Haskell-functors" sono (endo-) funtori F : Hask -> Hask mentre "ML-functors" sono funtori G : ML -> ML' .

Qui, Hask è la categoria formata da Haskell, i tipi e le funzioni tra loro, e allo stesso modo ML e ML' sono categorie definite da strutture ML.

Nota : ci sono alcuni problemi tecnici nel rendere Hask una categoria, ma ci sono modi per aggirarli.

Da una prospettiva teorica di categoria, ciò significa che un Hask functor è una mappa F di tipi Haskell:

data F a = ...

insieme a una mappa fmap delle funzioni di Haskell:

instance Functor F where
    fmap f = ...

ML è praticamente la stessa cosa, anche se non sono presente astrazione fmap canonica di cui sono a conoscenza, quindi definiamone una:

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

Questo è f mappe ML fmap e fmap maps ML -functions, quindi

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

è un functor F: StructA -> StructB .




In OCaml, è un modulo parametrizzato.

Se conosci C ++, pensa a un functor OCaml come modello. C + + ha solo modelli di classe, e i funtori lavorano alla scala del modulo.

Un esempio di functor è Map.Make; module StringMap = Map.Make (String);; crea un modulo mappa che funziona con mappe con chiave stringa.

Non è possibile ottenere qualcosa come StringMap con il solo polimorfismo; è necessario fare alcune ipotesi sulle chiavi. Il modulo String contiene le operazioni (confronto, ecc.) Su un tipo di stringa completamente ordinato e il functor si collegherà alle operazioni contenute nel modulo String. Potresti fare qualcosa di simile con la programmazione orientata agli oggetti, ma avresti un overhead di metodo indiretto.




In parole povere, un funtore, o un oggetto funzione, è un oggetto di classe che può essere chiamato proprio come una funzione.

In C ++:

Questo è il modo in cui scrivi una funzione

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

Questo è il modo in cui scrivi un funtore

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

Ora puoi fare questo:

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

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

Ciò che rende questi così grandi è che puoi mantenere lo stato in classe - immagina se volevi chiedere a una funzione quante volte è stato chiamato. Non c'è modo di farlo in un modo pulito e incapsulato. Con un oggetto funzione, è proprio come qualsiasi altra classe: avresti qualche variabile di istanza che incrementerai in operator () e qualche metodo per ispezionare quella variabile, e tutto è pulito come ti pare.




Non per contraddire le precedenti risposte teoriche o matematiche, ma un Functor è anche un oggetto (in un linguaggio di programmazione orientato agli oggetti) che ha un solo metodo ed è effettivamente usato come una funzione.

Un esempio è l'interfaccia Runnable in Java, che ha un solo metodo: run.

Considera questo esempio, prima in Javascript, che ha funzioni di prima classe:

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

Uscita: [1, 4, 25, 100]

Il metodo map accetta una funzione e restituisce una nuova matrice con ciascun elemento che è il risultato dell'applicazione di tale funzione sul valore nella stessa posizione nell'array originale.

Per fare la stessa cosa è Java, usando un Functor, dovresti prima definire un'interfaccia, per esempio:

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

Quindi, se aggiungi una classe di raccolta con una funzione mappa, puoi eseguire:

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

Questo utilizza una sottoclasse in-linea di IntMapFunction per creare un Functor, che è l'equivalente OO della funzione dall'esempio JavaScript precedente.

L'uso di Funcitors ti consente di applicare tecniche funzionali in un linguaggio OO. Naturalmente, alcuni linguaggi OO supportano direttamente le funzioni, quindi non è necessario.

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




Panoramica approssimativa

Nella programmazione funzionale, un funtore è essenzialmente una costruzione di funzioni ordinarie unarie di sollevamento (cioè quelle con un argomento) a funzioni tra variabili di nuovi tipi. È molto più semplice scrivere e mantenere semplici funzioni tra oggetti semplici e utilizzare i funtori per sollevarle, quindi per scrivere manualmente le funzioni tra oggetti contenitore complicati. Ulteriore vantaggio è quello di scrivere semplici funzioni solo una volta e quindi riutilizzarle tramite diversi funtori.

Esempi di funtori includono matrici, "forse" e "entrambi" funtori, futures (si veda ad esempio https://github.com/Avaq/Fluture ) e molti altri.

Illustrazione

Considera la funzione di costruire il nome della persona completa dal nome e dal cognome. Potremmo definirlo come fullName(firstName, lastName) come funzione di due argomenti, che tuttavia non sarebbero adatti per i funtori che si occupano solo di funzioni di un argomento. Per rimediare, raccogliamo tutti gli argomenti in un singolo name oggetto, che ora diventa il singolo argomento della funzione:

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

E se avessimo molte persone in un array? Invece di passare manualmente all'elenco, possiamo semplicemente riutilizzare la nostra funzione fullName tramite il metodo map fornito per gli array con una breve riga di codice:

fullNameList = nameList => nameList.map(fullName)

e usalo come

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

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

Questo funzionerà, ogni volta che ogni voce nel nostro nameList è un oggetto che fornisce sia proprietà firstName che lastName . Ma cosa succede se alcuni oggetti non (o addirittura non sono affatto oggetti)? Per evitare errori e rendere il codice più sicuro, possiamo avvolgere i nostri oggetti nel tipo Maybe (ad esempio 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()

dove Just(name) è un contenitore che contiene solo nomi validi e Nothing() è il valore speciale utilizzato per tutto il resto. Ora invece di interrompere (o dimenticare) per verificare la validità dei nostri argomenti, possiamo semplicemente riutilizzare (sollevare) la nostra funzione fullName originale con un'altra singola riga di codice, basata nuovamente sul metodo map , questa volta fornito per il tipo Maybe:

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

e usalo come

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 delle categorie

Un Functional in Category Theory è una mappa tra due categorie che rispetta la composizione dei loro morfismi. In una lingua del computer , la categoria principale di interesse è quella i cui oggetti sono tipi (determinati insiemi di valori) e i cui morfismi sono funzioni f:a->b da un tipo a all'altro tipo b .

Ad esempio, prendi a per essere il tipo String , b il tipo Number, e f è la funzione che mappa una stringa nella sua lunghezza:

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

Qui a = String rappresenta l'insieme di tutte le stringhe b = Number l'insieme di tutti i numeri. In questo senso, sia a che b rappresentano oggetti nella categoria Set (che è strettamente correlata alla categoria dei tipi, con la differenza che non è essenziale qui). Nella categoria Set, i morfismi tra due set sono precisamente tutte le funzioni dal primo set al secondo. Quindi la nostra funzione di lunghezza f qui è un morfismo dall'insieme di stringhe nell'insieme di numeri.

Poiché consideriamo solo la categoria dell'insieme, i relativi Functional da esso in se stessi sono mappe che inviano oggetti agli oggetti e morfismi ai morfismi, che soddisfano certe leggi algebriche.

Esempio: Array

Array può significare molte cose, ma solo una cosa è un Functor - il costrutto del tipo, mappando un tipo a nel tipo [a] di tutti gli array di tipo a . Ad esempio, il funcray Array esegue il mapping del tipo String nel tipo [String] (l'insieme di tutti gli array di stringhe di lunghezza arbitraria) e imposta Type Number nel tipo corrispondente [Number] (l'insieme di tutte le matrici di numeri).

È importante non confondere la mappa di Functor

Array :: a => [a]

con un morfismo a -> [a] . Il functor mappa semplicemente (associa) il tipo a nel tipo [a] come una cosa a un'altra. Che ogni tipo sia in realtà un insieme di elementi, qui non ha alcuna rilevanza. Al contrario, un morfismo è una funzione effettiva tra quelle serie. Per esempio, c'è un morfismo naturale (funzione)

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

che invia un valore nell'array a 1 elemento con quel valore come singola voce. Quella funzione non fa parte Array Functor! Dal punto di vista di questo funtore, pure è solo una funzione come le altre, niente di speciale.

D'altra parte, l' Array Functor ha la sua seconda parte, la parte del morfismo. Che mappa un morfismo f :: a -> b in un morfismo [f] :: [a] -> [b] :

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

Qui arr è qualsiasi array di lunghezza arbitraria con valori di tipo a , e arr.map(f) è la matrice della stessa lunghezza con valori di tipo b , le cui voci sono i risultati dell'applicazione di f alle voci di arr . Per renderlo un funtore, le leggi matematiche di mappatura dell'identità per l'identità e le composizioni per le composizioni devono essere mantenute, che sono facili da controllare in questo esempio di Array .




Links