W Functional Programming, czym jest funktor?

224

Kilka razy spotkałem się z terminem „Functor” podczas czytania różnych artykułów na temat programowania funkcjonalnego, ale autorzy zazwyczaj zakładają, że czytelnik już rozumie ten termin. Rozglądanie się w Internecie dostarczyło albo zbyt technicznych opisów (patrz artykuł Wikipedii ), albo niezwykle niejasne opisy (patrz sekcja Functors na tej stronie z samouczkiem ocaml ).

Czy ktoś może uprzejmie zdefiniować termin, wyjaśnić jego użycie i być może podać przykład tworzenia i używania Functors?

Edycja : Chociaż jestem zainteresowany teorią tego terminu, mniej interesuję się teorią niż wdrażaniem i praktycznym wykorzystaniem tej koncepcji.

Edycja 2 : Wygląda na to, że zachodzi pewna cross-terminoligia: Mam na myśli w szczególności Functors programowania funkcjonalnego, a nie obiekty funkcyjne C ++.

Erik Forbes
źródło
4
Zobacz też: adit.io/posts/…
Vlad the Impala
Całkiem dobra odpowiedź: stackoverflow.com/a/45149475/1498178
toraritte
Jeśli jesteś bardziej zainteresowany praktycznym wdrożeniem i użytkowaniem niż terminologią i teorią stratosferyczną leżącą u podstaw tej koncepcji, potrzebujesz tylko jednej linijki: funktor ujawnia funkcję „mapy”.
Richard Gomes
@RichardGomes IMHO Myślę, że redukuje rolę funktora do prostego interfejsu podobnego do Javy, ale tak nie jest. Funktor przekształca rzeczy, buduje nowe typy z istniejących (w Haskell), co oznacza, że ​​typy są również mapowane. fmapmapuje funkcje. W grę wchodzą dwa rodzaje mapowań. Taki sposób widzenia rzeczy pomoże zrozumieć teorię kategorii (która jest bardziej ogólna). Chodzi o to, że warto zrozumieć podstawową teorię kategorii, aby pomóc nam we wszystkich zagadnieniach teorii kategorii w Haskell (funktor, monady, ...).
Ludovic Kuty,
@VladtheImpala Wpis na blogu jest fantastyczny, ale nawet jeśli bardzo pomaga, lubię pamiętać, że funktor buduje (odwzorowuje) inny typ. Szczególnie podoba mi się zdanie „Funktor F bierze każdy typ T i odwzorowuje go na nowy typ FT” Monadach są jak burrito . IMHO nie jest tylko kontekstem (ramką) wokół wartości, nawet jeśli jest to praktyczne, aby zobaczyć takie rzeczy (Haskell PoV vs. teoria kategorii PoV?)
Ludovic Kuty

Odpowiedzi:

273

Słowo „funktor” pochodzi od teorii kategorii, która jest bardzo ogólną, bardzo abstrakcyjną gałęzią matematyki. Został pożyczony przez projektantów języków funkcjonalnych na co najmniej dwa różne sposoby.

  • W rodzinie języków ML funktor to moduł, który przyjmuje jeden lub więcej innych modułów jako parametr. Jest uważany za zaawansowaną funkcję, a większość początkujących programistów ma z nią trudności.

    Jako przykład implementacji i praktycznego zastosowania można zdefiniować ulubioną formę zrównoważonego drzewa wyszukiwania binarnego raz na zawsze jako funktor, a jako parametr przyjmie on moduł, który zapewnia:

    • Typ klucza do użycia w drzewie binarnym

    • Funkcja całkowitego uporządkowania na klawiszach

    Gdy to zrobisz, możesz zawsze używać tej samej zrównoważonej implementacji drzewa binarnego. (Typ wartości przechowywanej w drzewie jest zwykle pozostawiony polimorficzny - drzewo nie musi patrzeć na wartości inne niż je kopiować, podczas gdy drzewo zdecydowanie musi być w stanie porównywać klucze i otrzymuje funkcję porównania z parametr funktora).

    Innym zastosowaniem funktorów ML jest warstwowe protokoły sieciowe . Link jest do naprawdę wspaniałego artykułu grupy CMU Fox; pokazuje, jak używać funktorów do budowania bardziej złożonych warstw protokołu (takich jak TCP) na typach prostszych warstw (takich jak IP lub nawet bezpośrednio przez Ethernet). Każda warstwa jest implementowana jako funktor, który przyjmuje jako parametr warstwę pod nią. Struktura oprogramowania faktycznie odzwierciedla sposób, w jaki ludzie myślą o problemie, w przeciwieństwie do warstw istniejących tylko w umyśle programisty. W 1994 r., Kiedy ta praca została opublikowana, była to wielka sprawa.

    Dla dzikiego przykładu funktorów ML w akcji można zobaczyć artykuł ML Module Mania , który zawiera publikowalny (tj. Przerażający) przykład funktorów w pracy. Aby uzyskać genialne, jasne i przejrzyste wyjaśnienie systemu modułów ML (w porównaniu z innymi rodzajami modułów), przeczytaj kilka pierwszych stron genialnego dokumentu POPL z 1994 roku autorstwa Xaviera Leroya, Typy, moduły i oddzielna kompilacja .

  • W Haskell i w niektórych powiązanych czystych językach funkcjonalnych Functorjest to klasa typów . Typ należy do klasy typu (lub technicznie rzecz biorąc, typ „jest instancją” klasy typu), gdy typ zapewnia pewne operacje o określonych oczekiwanych zachowaniach. Typ Tmoże należeć do klasy, Functorjeśli ma pewne zachowanie podobne do kolekcji:

    • Typ Tjest sparametryzowany na innym typie, który należy traktować jako typ elementu kolekcji. Rodzaj pełnej kolekcji jest wtedy coś T Int, T String, T Bool, jeśli zawierający liczby całkowite, ciągi lub logicznych odpowiednio. Jeśli typ elementu jest nieznany, jest zapisywany jako parametr typu a , jak w T a.

      Przykłady obejmują listy (zero lub więcej elementów typu a), Maybetyp (zero lub jeden element typu a), zestawy elementów typu a, tablice elementów typu a, wszelkiego rodzaju drzewa wyszukiwania zawierające wartości typua i wiele innych mogę wymyślić.

    • Inną właściwością, Tktórą należy spełnić, jest to, że jeśli masz funkcję typu a -> b(funkcję na elementach), musisz mieć możliwość przyjęcia tej funkcji i wygenerowania powiązanej funkcji w kolekcjach. Robisz to za pomocą operatora fmap, który jest wspólny dla każdego typu w Functorklasie typów. Operator jest przeciążony, więc jeśli masz funkcję eventypu Int -> Bool, to

      fmap even

      to przeciążona funkcja, która potrafi wiele wspaniałych rzeczy:

      • Konwertuj listę liczb całkowitych na listę wartości logicznych

      • Konwertuj drzewo liczb całkowitych na drzewo boolean

      • Konwertuj Nothingna Nothingi Just 7naJust False

      W Haskell właściwość ta jest wyrażona przez podanie typu fmap:

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

      gdzie mamy teraz małe t, co oznacza „dowolny typ w Functorklasie”.

    Krótko mówiąc, w Haskell funktor jest rodzajem kolekcji, dla której jeśli otrzymasz funkcję na elementach, fmapzwróci ci funkcję na kolekcjach . Jak możesz sobie wyobrazić, jest to pomysł, który można szeroko wykorzystać ponownie, dlatego jest błogosławiony jako część standardowej biblioteki Haskella.

Jak zwykle ludzie nadal wymyślają nowe, przydatne abstrakty, a może warto przyjrzeć się funktorom aplikacyjnym , do których najlepszym odniesieniem może być artykuł Conor McBride i Ross Paterson, zatytułowany Programowanie aplikacyjne z efektami .

Norman Ramsey
źródło
7
Rozumiem zarówno funktory ML, jak i funktory Haskella, ale brakuje mi wglądu, by powiązać je ze sobą. Jaki jest związek między nimi w sensie teoretycznym?
Wei Hu
6
@Wei Hu: Teoria kategorii nigdy nie miała dla mnie żadnego sensu. Najlepsze, co mogę powiedzieć, to to, że wszystkie trzy pojęcia obejmują mapowanie.
Norman Ramsey
16
Według tej wiki Haskell: en.wikibooks.org/wiki/Haskell/Category_theory wygląda to tak: Kategoria to zbiór obiektów i morfizmów (funkcji), gdzie morfizmy są od obiektów w kategorii do innych obiektów w tej kategorii . Funktor to funkcja, która odwzorowuje obiekty i morfizmy z jednej kategorii na obiekty i morfizmy w innej. Przynajmniej tak to rozumiem. Co to dokładnie oznacza dla programowania, którego jeszcze nie rozumiem.
Paul
5
@ norman-ramsey, czy spojrzałeś na matematykę konceptualną Lawvere i Schanuela? Jestem całkowitym nowicjuszem w tej dziedzinie, ale książka jest niezwykle czytelna i - śmiem powiedzieć - przyjemna. (Podobało mi się twoje wyjaśnienie.)
Ram Rajamony
2
then you have to be able to take that function and product a related function on collectionsMiałeś na myśli producezamiast product?
problemofficer
64

Inne odpowiedzi tutaj są kompletne, ale spróbuję wyjaśnić użycie funktora FP . Weź to jako analogię:

Funktor jest kontenerem typu a który poddany funkcji odwzorowującej od ab daje kontener typu b .

W przeciwieństwie do użycia wskaźnika abstrakcji funkcji w C ++, tutaj funktor nie jest funkcją; raczej jest to coś, co zachowuje się konsekwentnie, kiedy podlega funkcji .

seh
źródło
3
Kontener typu b oznacza „ten sam rodzaj kontenera, co kontener wejściowy, ale teraz jest wypełniony literami b”. Więc jeśli mamy listę bananów i mapujemy funkcję, która bierze banana i wytwarza sałatkę owocową, mamy teraz listę sałatek owocowych. Podobnie, gdybyśmy mieli drzewo bananów i zmapowalibyśmy tę samą funkcję, mielibyśmy teraz drzewo jabłek. Itd. Drzewo i lista są tutaj dwoma Functors.
Qqwy,
3
„Funktor jest kontenerem typu a, który po poddaniu się funkcji” - w rzeczywistości jest na odwrót - funkcja (morfizm) podlega funktorowi, który ma być odwzorowany na inny morfizm
Dmitri Zaitsev,
38

Istnieją trzy różne znaczenia, niewiele powiązane!

  • W Ocaml jest to sparametryzowany moduł. Zobacz instrukcję . Myślę, że najlepszym sposobem, aby je pogłaskać jest przykład: (napisane szybko, może być błędne)

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

Możesz teraz szybko dodawać wiele możliwych zamówień, sposoby tworzenia nowych zamówień, łatwo wyszukiwać binarne lub liniowe nad nimi. Programowanie ogólne FTW.

  • W funkcjonalnych językach programowania, takich jak Haskell, oznacza to niektóre konstruktory typów (typy sparametryzowane, takie jak listy, zestawy), które można „mapować”. Mówiąc ściślej, funktor fjest wyposażony (a -> b) -> (f a -> f b). Ma to swoje źródło w teorii kategorii. Artykuł w Wikipedii, do którego linkujesz, dotyczy tego użycia.

    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

Jest to więc szczególny rodzaj konstruktora typu i ma niewiele wspólnego z funktorami w Ocaml!

  • W językach imperatywnych jest to wskaźnik do działania.
sdcvvc
źródło
Czy <q> mapowanie </q> w ostatnich 3 wierszach tego komentarza nie powinno być rzeczywiście <q> fmap </q>?
imz - Ivan Zakharyaschev
1
Zawsze czytałem, że funktory są pojemnikami - ale to tylko słabe uproszczenie. Twoja odpowiedź w końcu podała brakujący link: Functors to klasa typu (ograniczenie typu) dla sparametryzowanych typów (konstruktorów typów). To takie proste!
16

W OCaml jest to sparametryzowany moduł.

Jeśli znasz C ++, pomyśl o funktorze OCaml jako szablonie. C ++ ma tylko szablony klas, a funktory działają w skali modułu.

Przykładem funktora jest Map.Make; module StringMap = Map.Make (String);;buduje moduł mapy, który działa z mapami z kluczem ciągowym.

Nie można osiągnąć czegoś takiego jak StringMap tylko z polimorfizmem; musisz poczynić pewne założenia dotyczące kluczy. Moduł String zawiera operacje (porównanie itp.) Na całkowicie uporządkowanym typie ciągu, a funktor połączy się z operacjami, które zawiera moduł String. Mógłbyś zrobić coś podobnego z programowaniem obiektowym, ale miałbyś narzut pośredniej metody.

Tobu
źródło
Dostałem to ze strony ocaml - ale nie rozumiem, jakie byłoby zastosowanie sparametryzowanego modułu.
Erik Forbes
4
@Kornel Tak, to, co opisałem, to koncepcja OCaml. Druga koncepcja to po prostu „wartość funkcjonalna”, która nie jest niczym szczególnym w FP. @Erik Rozszerzyłem nieznacznie, ale dokumenty referencyjne ładują się powoli.
Tobu,
13

Masz kilka dobrych odpowiedzi. Wrzucę:

Funkt, w sensie matematycznym, jest szczególnym rodzajem funkcji algebry. Jest to minimalna funkcja, która odwzorowuje algebrę na inną algebrę. „Minimalność” wyraża się w prawach funktora.

Są na to dwa sposoby. Na przykład, listy są funktorami nad jakimś typem. Oznacza to, że biorąc pod uwagę algebrę nad typem „a”, można wygenerować zgodną algebrę list zawierających elementy typu „a”. (Na przykład: mapa, która przenosi element do listy singletonów zawierającej go: f (a) = [a]) Ponownie pojęcie zgodności wyraża się w prawach funktora.

Z drugiej strony, biorąc pod uwagę funktor f „nad” typem a (to znaczy fa jest wynikiem zastosowania funktora f do algebry typu a) i funkcji z g: a -> b, możemy obliczyć nowy funktor F = (fmap g), który odwzorowuje fa na f b. Krótko mówiąc, fmap jest częścią F, która mapuje „części funktora” na „części funktora”, a g jest częścią funkcji, która mapuje „części algebry” na „części algebry”. Pobiera funkcję, funktor, a po zakończeniu JEST funktorem.

Może się wydawać, że różne języki używają różnych pojęć funktorów, ale tak nie jest. Używają po prostu funktorów w różnych algebrach. OCamls ma algebrę modułów, a funktory tej algebry pozwalają dołączać nowe deklaracje do modułu w „zgodny” sposób.

Funktor Haskell NIE jest klasą typu. Jest to typ danych z dowolną zmienną, która spełnia klasę typu. Jeśli chcesz zagłębić się w wnętrzności typu danych (bez wolnych zmiennych), możesz ponownie zinterpretować typ danych jako funktor nad podstawową algebrą. Na przykład:

dane F = F Int

jest izomorficzny do klasy Ints. Zatem F, jako konstruktor wartości, jest funkcją odwzorowującą Int na F Int, równoważną algebrę. To jest funktor. Z drugiej strony nie dostajesz tutaj fmap za darmo. Do tego właśnie służy dopasowanie wzorca.

Functory są dobre do „przyczepiania” rzeczy do elementów algebry w sposób algebraicznie zgodny.

użytkownik276631
źródło
8

Najlepsza odpowiedź na to pytanie znajduje się w „Typeclassopedia” Brenta Yorgeya.

To wydanie Monad Reader zawiera dokładną definicję tego, czym jest funktor, a także wiele innych definicji, a także schemat. (Pojęcie monoidalne, aplikacyjne, monadowe i inne są wyjaśnione i postrzegane w odniesieniu do funktora).

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

fragment Typeclassopedia for Functor: „Prostą intuicją jest to, że Functor reprezentuje pewnego rodzaju„ pojemnik ”, wraz z możliwością równomiernego zastosowania funkcji do każdego elementu w pojemniku”

Ale tak naprawdę cała ta typeclassopedia jest wysoce zalecaną lekturą, która jest zaskakująco łatwa. W taki sposób można zobaczyć prezentowaną tam typkę jako wzór równoległy do ​​wzorca projektowego w obiekcie, w tym sensie, że dają ci słownictwo dotyczące danego zachowania lub możliwości.

Twoje zdrowie

JFT
źródło
7

Jest całkiem dobry przykład w książce O'Reilly OCaml, która znajduje się na stronie internetowej Inrii (która w chwili pisania tego niestety nie działa). Znalazłem bardzo podobny przykład w tej książce używanej przez caltech: Wprowadzenie do OCaml (link pdf) . Odpowiednią sekcją jest rozdział dotyczący funktorów (strona 139 w książce, strona 149 w pliku PDF).

W książce mają funktor o nazwie MakeSet, który tworzy strukturę danych, która składa się z listy, i funkcje dodawania elementu, określania, czy element znajduje się na liście i znajdowania elementu. Sparametryzowano funkcję porównawczą, która służy do określenia, czy jest w zestawie, czy nie. (Co czyni MakeSet funktorem zamiast modułu).

Mają także moduł, który implementuje funkcję porównania, dzięki czemu porównuje ciąg znaków bez rozróżniania wielkości liter.

Za pomocą funktora i modułu, który implementuje porównanie, mogą utworzyć nowy moduł w jednym wierszu:

module SSet = MakeSet(StringCaseEqual);;

który tworzy moduł dla ustalonej struktury danych, która wykorzystuje porównania bez rozróżniania wielkości liter. Jeśli chcesz utworzyć zestaw, w którym używane są rozróżnienia wielkości liter, wystarczy zaimplementować nowy moduł porównania zamiast nowego modułu struktury danych.

Tobu porównał funktory do szablonów w C ++, które moim zdaniem są całkiem trafne.

Niki Yoshiuchi
źródło
6

Biorąc pod uwagę inne odpowiedzi i to, co zamierzam teraz opublikować, powiedziałbym, że to dość mocno przeciążone słowo, ale w każdym razie ...

Aby uzyskać podpowiedź dotyczącą znaczenia słowa „funktor” w języku Haskell, zapytaj 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

Zasadniczo funktor w Haskell jest czymś, co można zmapować. Innym sposobem na powiedzenie jest to, że funktor to coś, co można uznać za kontener, o który można poprosić o użycie danej funkcji do przekształcenia zawartej w niej wartości; Zatem, na listach, fmapzbiega się z map, na Maybe, fmap f (Just x) = Just (f x), fmap f Nothing = Nothingitd.

Podsekcja typu Functor oraz sekcja Functors, Functors Applicative i Monoids of Learn You a Haskell for Great Good podają przykłady przydatności tej konkretnej koncepcji. (Podsumowanie: wiele miejsc! :-))

Zauważ, że każdą monadę można traktować jako funktor, a tak naprawdę, jak zauważa Craig Stuntz, najczęściej używanymi funktorami są zwykle monady ... OTOH, wygodnie jest czasami zrobić typ instancji klasy Functor bez kłopotów z robieniem z niego Monady. (Np. W przypadku ZipListz Control.Applicative, wymienionego na jednej z wyżej wymienionych stron .)

Michał Marczyk
źródło
5

Oto artykuł na temat funktorów z POV programowania , a następnie dokładniej, jak ukazują się one w językach programowania .

Praktyczne użycie funktora jest w monadzie, a jeśli o to chodzi, możesz znaleźć wiele samouczków na temat monad.

Craig Stuntz
źródło
1
„Praktyczne zastosowanie funktora jest w monadzie” - nie tylko. Wszystkie monady są funktorami, ale istnieje wiele zastosowań funktorów niemonadowych.
amindfv
1
Powiedziałbym, że studiowanie monad w celu użycia funktorów jest jak oszczędzanie na bułki, aby kupić artykuły spożywcze.
Marco Faustinelli,
5

W komentarzu do najczęściej głosowanej odpowiedzi użytkownik Wei Hu pyta:

Rozumiem zarówno funktory ML, jak i funktory Haskella, ale brakuje mi wglądu, by powiązać je ze sobą. Jaki jest związek między nimi w sensie teoretycznym?

Uwaga : nie znam ML, więc proszę wybacz i popraw wszelkie powiązane błędy.

Załóżmy początkowo, że wszyscy znamy definicje „kategorii” i „funktora”.

Krótka odpowiedź brzmiałaby, że „funktory Haskella” są funktorami (endo-), F : Hask -> Haskpodczas gdy „funktory ML” są funktoramiG : ML -> ML' .

Tutaj Haskjest kategoria utworzona przez typy Haskell i funkcje między nimi, i podobnie MLi ML'są kategoriami zdefiniowanymi przez struktury ML.

Uwaga : istnieją pewne problemy techniczne z tworzeniemHask kategorii, ale istnieją sposoby ich obejścia.

Z teoretycznego punktu widzenia kategorii oznacza to, że Haskfunkcja jest mapą Ftypów Haskella:

data F a = ...

wraz z mapą fmapfunkcji Haskell:

instance Functor F where
    fmap f = ...

ML jest prawie taki sam, chociaż nie fmapznam kanonicznej abstrakcji, więc zdefiniujmy jedną:

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

To znaczy fmapy - MLtypy i fmapmapy - MLfunkcje, więc

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

jest funktorem F: StructA -> StructB.

Ncat
źródło
5

„Functor to mapowanie obiektów i morfizmów, które zachowuje kompozycję i tożsamość kategorii”.

Zdefiniujmy, co to jest kategoria?

To mnóstwo przedmiotów!

Narysuj kilka kropek (na razie 2 kropki, jedna to „a”, druga to „b”) wewnątrz koła i nazwij na razie to koło A (kategoria).

Co obejmuje kategoria?

Kompozycja między obiektami a funkcją tożsamości dla każdego obiektu.

Musimy więc zmapować obiekty i zachować kompozycję po zastosowaniu naszego Functora.

Wyobraźmy sobie, że „A” to nasza kategoria, która ma obiekty [„a”, „b”] i istnieje morfizm a -> b

Teraz musimy zdefiniować funktor, który może zmapować te obiekty i morfizmy do innej kategorii „B”.

Powiedzmy, że funktor nazywa się „Może”

data Maybe a = Nothing | Just a

Tak więc kategoria „B” wygląda następująco.

Narysuj kolejne koło, ale tym razem za pomocą „Może a” i „Może b” zamiast „a” i „b”.

Wszystko wydaje się dobre, a wszystkie obiekty są mapowane

„a” stało się „Może a”, a „b” stało się „Być może b”.

Problem polega jednak na tym, że musimy zmapować morfizm również z „a” na „b”.

Oznacza to, że morfizm a -> b w „A” powinien odwzorowywać na morfizm „Może a” -> „Może b”

morfizm z a -> b nazywa się f, następnie morfizm z „Może a” -> „Może b” nazywa się „fmap f”

Zobaczmy teraz, jaką funkcję „f” pełniła w „A” i zobaczmy, czy możemy ją replikować w „B”

definicja funkcji „f” w „A”:

f :: a -> b

f bierze a i zwraca b

definicja funkcji „f” w „B”:

f :: Maybe a -> Maybe b

f bierze Może a i zwraca Może b

zobaczmy, jak używać fmap do mapowania funkcji „f” z „A” na funkcję „fmap f” w „B”

definicja fmap

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

Co my tu robimy?

Stosujemy funkcję „f” do „x”, który jest typu „a”. Specjalne dopasowanie wzorca „Nic” pochodzi z definicjiFunctor Maybe .

Tak więc zamapowaliśmy nasze obiekty [a, b] i morfizmy [f] z kategorii „A” na kategorię „B”.

To jest Functor!

wprowadź opis zdjęcia tutaj

Sumanth Kumar Mora
źródło
Ciekawa odpowiedź. Chciałbym uzupełnić go o Monady są jak burrito (zabawna odpowiedź na abstrakcję, intuicję i „błąd samouczka monady” ), a jego zdanie „Funktor F bierze każdy typ T i mapuje go na nowy typ FT”, czyli konstruktor typów . Przydatne było także programowanie funkcjonalne i teoria kategorii - kategorie i funktory .
Ludovic Kuty,
3

Szorstki przegląd

W programowaniu funkcjonalnym funktor jest zasadniczo konstrukcją podnoszenia zwykłych funkcji jednoargumentowych (tj. Tych z jednym argumentem) do funkcji między zmiennymi nowych typów. Znacznie łatwiej jest pisać i utrzymywać proste funkcje między prostymi obiektami i używać funktorów do ich podnoszenia, a następnie ręcznie pisać funkcje między skomplikowanymi obiektami kontenerowymi. Kolejną zaletą jest napisanie prostych funkcji tylko raz, a następnie ponowne użycie ich za pomocą różnych funktorów.

Przykłady funktorów obejmują tablice, funty „może” i „albo”, futures (patrz np. Https://github.com/Avaq/Fluture ) i wiele innych.

Ilustracja

Rozważ funkcję konstruującą pełne imię i nazwisko osoby na podstawie imienia i nazwiska. Możemy to zdefiniować fullName(firstName, lastName)jako funkcję dwóch argumentów, co jednak nie byłoby odpowiednie dla funktorów, które zajmują się funkcjami tylko jednego argumentu. Aby temu zaradzić, zbieramy wszystkie argumenty w jednym obiekcie name, który teraz staje się pojedynczym argumentem funkcji:

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

Co teraz, jeśli mamy wiele osób w jednym szeregu? Zamiast ręcznie przeglądać listę, możemy po prostu ponownie użyć naszej funkcji fullNameza pomocą mapmetody przewidzianej dla tablic z krótkim pojedynczym wierszem kodu:

fullNameList = nameList => nameList.map(fullName)

i używaj go jak

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

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

Będzie to działać, ilekroć każdy wpis w naszym nameListobiekcie jest obiektem zapewniającym zarówno właściwości, jak firstNamei lastNamewłaściwości. Ale co, jeśli niektóre obiekty nie (a nawet wcale nie są)? Aby uniknąć błędów i uczynić kod bezpieczniejszym, możemy owinąć nasze obiekty w Maybetyp (patrz np. 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()

gdzie Just(name)jest pojemnikiem zawierającym tylko prawidłowe nazwy i Nothing()jest specjalną wartością używaną do wszystkiego innego. Teraz zamiast przerywać (lub zapominać) sprawdzanie poprawności naszych argumentów, możemy po prostu ponownie użyć (podnieść) naszą oryginalną fullNamefunkcję z innym pojedynczym wierszem kodu, ponownie opartym na mapmetodzie, tym razem przewidzianym dla typu Może:

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

i używaj go jak

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 kategorii

Funktora w teorii kategorii znajduje się mapa dwie kategorie poszanowaniem skład swoich morfizmów. W języku komputerowym główną kategorią zainteresowań jest ta, której obiektamitypy (określone zestawy wartości) i której morfizmy są funkcjami f:a->bjednego typu ana inny b.

Na przykład, weźmy asię za Stringtyp,b Liczba i fjest funkcją odwzorowującą ciąg znaków na jego długość:

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

Tutaj a = Stringreprezentuje zestaw wszystkich ciągów i b = Numberzestaw wszystkich liczb. W tym sensie, jak ai breprezentacji obiektów w Set Kategorii (co jest ściśle związane z kategorią typów, z tą różnicą, nieistotne tutaj). W kategorii zestawu morfizmy między dwoma zestawami są dokładnie wszystkimi funkcjami od pierwszego zestawu do drugiego. Zatem naszą funkcją długości fjest morfizm ze zbioru ciągów na zbiór liczb.

Ponieważ bierzemy pod uwagę tylko zestaw kategorii, odpowiedni funktorami z niej samych są mapy wysyłające obiekty do obiektów i morfizmy do morfizmów, które spełniają pewne prawa algebraiczne.

Przykład: Array

Arraymoże oznaczać wiele rzeczy, ale tylko jedna rzecz to Functor - konstrukcja typu, mapująca typ ana typ [a]wszystkich tablic typu a. Na przykład Arrayfunktor odwzorowuje typ String na typ [String](zbiór wszystkich tablic ciągów o dowolnej długości), a zestaw typ Numberna odpowiedni typ [Number](zbiór wszystkich tablic liczb).

Ważne jest, aby nie mylić mapy Functor

Array :: a => [a]

z morfizmem a -> [a]. Funktor po prostu odwzorowuje (kojarzy) typ ana typ [a]jako jedna rzecz na drugą. To, że każdy typ jest w rzeczywistości zestawem elementów, nie ma tutaj znaczenia. Natomiast morfizm jest faktyczną funkcją między tymi zbiorami. Na przykład występuje naturalny morfizm (funkcja)

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

który wysyła wartość do tablicy 1-elementowej z tą wartością jako pojedynczy wpis. Ta funkcja nie jest częściąArray Functora! Z punktu widzenia tego funktora purejest to jak każda inna funkcja, nic specjalnego.

Z drugiej strony ArrayFunctor ma swoją drugą część - część morfizmu. Który f :: a -> bzamienia morfizm w morfizm [f] :: [a] -> [b]:

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

Oto arrdowolna tablica o dowolnej długości z wartościami typu ai arr.map(f)jest tablicą o tej samej długości z wartościami typu b, których wpisy są wynikiem zastosowania fdo wpisów z arr. Aby uczynić go funktorem, muszą obowiązywać matematyczne prawa odwzorowywania tożsamości na tożsamość i kompozycji na kompozycje, które łatwo sprawdzić w tym Arrayprzykładzie.

Dmitri Zaitsev
źródło
2

Aby nie zaprzeczyć poprzednim teoretycznym lub matematycznym odpowiedziom, ale Functor to także Obiekt (w języku programowania obiektowego), który ma tylko jedną metodę i jest skutecznie wykorzystywany jako funkcja.

Przykładem jest interfejs Runnable w Javie, który ma tylko jedną metodę: uruchom.

Rozważ ten przykład, najpierw w JavaScript, który ma pierwszorzędne funkcje:

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

Wyjście: [1, 4, 25, 100]

Metoda map przyjmuje funkcję i zwraca nową tablicę, przy czym każdy element jest wynikiem zastosowania tej funkcji do wartości w tej samej pozycji w oryginalnej tablicy.

Aby zrobić to samo, co Java, używając Functora, najpierw musisz zdefiniować interfejs, powiedz:

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

Następnie, jeśli dodasz klasę kolekcji, która miała funkcję mapy, możesz:

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

Wykorzystuje on wbudowaną podklasę IntMapFunction, aby utworzyć Functor, który jest odpowiednikiem OO funkcji z wcześniejszego przykładu JavaScript.

Korzystanie z Functors pozwala stosować techniki funkcjonalne w języku OO. Oczywiście niektóre języki OO również obsługują funkcje bezpośrednio, więc nie jest to wymagane.

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

Kevin Greer
źródło
W rzeczywistości „obiekt funkcji” nie jest poprawnym opisem funktora. Np. ArrayJest funktorem, ale Array(value)daje tylko tablice 1-elementowe.
Dmitri Zaitsev
0

KISS: Funktor to obiekt posiadający metodę mapy.

Tablice w JavaScript implementują mapę i dlatego są funktorami. Obietnice, strumienie i drzewa często implementują mapę w językach funkcjonalnych, a kiedy to robią, są uważane za funktory. Metoda mapy funktora pobiera własną zawartość i przekształca każdą z nich za pomocą wywołania zwrotnego transformacji przekazanego do mapy, i zwraca nowy funktor, który zawiera strukturę jako pierwszy funktor, ale z przekształconymi wartościami.

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

soundyogi
źródło
1
Na marginesie należy zauważyć, że „przedmiot” należy interpretować bardzo szeroko i po prostu znaczy „coś”. Na przykład w przypadku języków OOP zamień obiekt na klasę . Można powiedzieć, że „funktor to klasa, która implementuje interfejs Functor” (Oczywiście, interfejs ten może fizycznie nie istnieć, ale można podnieść logikę „mapy” do tego interfejsu i pozwolić wszystkim klasom, które można odwzorować, udostępnić go - o ile twój system pisma pozwala na pisanie rzeczy tak ogólnie, to znaczy).
Qqwy,
1
Uważam, że Klasy są bardzo mylące, szczerze mówiąc, z jednej strony są one jedynie schematem dla czegoś konkretnego / ale mogą również mieć metody (rzeczy statyczne) i mogą zachowywać się jak przedmioty. Czy klasa implementuje interfejs lub instancję, którą tworzy?
soundyogi,
1
Tak, mogą być mylące. Ale: Klasy implementują interfejsy („wypełniają” puste pola podane w metodach interfejsów. Innymi słowy: zmieniają abstrakcyjne wytyczne interfejsu w konkretne wytyczne, które mogą być natychmiastowe (wybaczenie kalambury) tworzone). Jeśli chodzi o „klasy zachowują się jak obiekty”: w prawdziwych językach OOP, takich jak Ruby, klasy są instancjami klasy „Class”. Żółwie są na dole.
Qqwy,
ArrayKonstrukcja typu definiuje pojedynczy funktor. Jego instancje są również nazywane „tablicami”, ale nie są funktorami. Opis tutaj powinien być bardziej precyzyjny.
Dmitri Zaitsev,
@DmitriZaitsev Czy mógłbyś opracować? Mówisz więc, że instancje nie są funktorami? Nie widzę w tym sensu, ponieważ otrzymujesz nowy funktor, mapując go na jeden.
soundyogi
-4

W praktyce funktor oznacza obiekt, który implementuje operator wywołania w C ++. W ocaml myślę, że funktor odnosi się do czegoś, co przyjmuje moduł jako dane wejściowe i wyjściowe innego modułu.

feng
źródło
-6

Mówiąc prościej, funktor lub obiekt funkcji jest obiektem klasy, który można wywołać tak jak funkcję.

W C ++:

Tak piszesz funkcję

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

Tak piszesz funktor

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

Teraz możesz to zrobić:

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

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

To, co sprawia, że ​​są tak świetne, to to, że możesz zachować stan w klasie - wyobraź sobie, że chcesz zapytać funkcję, ile razy została wywołana. Nie da się tego zrobić w zgrabny, zamknięty sposób. Z obiektem funkcyjnym jest jak każda inna klasa: miałbyś jakąś zmienną instancji, którą zwiększasz, operator ()i jakąś metodę sprawdzania tej zmiennej, i wszystko jest w porządku, jak chcesz.

Matt
źródło
12
Nie, te funktory nie są pojęciem teorii typów stosowanym w językach FP.
Tobu,
1
Rozumiem, w jaki sposób można udowodnić, że FunctorClassspełnia on pierwsze Prawo Funktora, ale czy mógłbyś naszkicować dowód na drugie Prawo? Nie do końca to widzę.
Jörg W Mittag
3
Bah, macie rację. Zrobiłem pchnięcie nożem w rozwiązywaniu problemu „sieć dostarczyła niezwykle techniczne opisy” i przeszedłem, starając się unikać: „W rodzinie języków ML funktor to moduł, który przyjmuje jeden lub więcej innych modułów jako parametr”. Ta odpowiedź jest jednak zła. Zbyt uproszczone i nieokreślone. Kusi mnie, by to zrobić, ale zostawię to przyszłym pokoleniom, aby potrząsnęły głowami :)
Matt
Cieszę się, że zostawiłeś odpowiedź i komentarze, ponieważ pomaga to rozwiązać problem. Dziękuję Ci! Mam problem z tym, że większość odpowiedzi jest napisana w kategoriach Haskell lub OCaml, a dla mnie to trochę jak wyjaśnienie aligatorów w kategoriach krokodyli.
Rob
-10

Functor nie jest ściśle związany z programowaniem funkcjonalnym. To tylko „wskaźnik” do funkcji lub jakiegoś obiektu, który można wywołać tak, jakby był funkcją.

alemjerus
źródło
8
Istnieje specyficzna koncepcja funktora FP (z teorii kategorii), ale masz rację, że to samo słowo jest również używane do innych rzeczy w językach innych niż FP.
Craig Stuntz
Czy jesteś pewien, że wskaźniki funkcji są Functors? Nie widzę, w jaki sposób wskaźniki funkcji spełniają dwa prawa funktorów, zwłaszcza drugie prawo funktorów (zachowanie składu morfizmu). Czy masz na to dowód? (Tylko przybliżony szkic.)
Jörg W Mittag