Dalam Pemrograman Fungsional, apa itu functor?

224

Saya telah menemukan istilah 'Functor' beberapa kali saat membaca berbagai artikel tentang pemrograman fungsional, tetapi penulis biasanya menganggap pembaca sudah memahami istilah tersebut. Melihat-lihat di web telah memberikan deskripsi teknis yang berlebihan (lihat artikel Wikipedia ) atau deskripsi yang sangat kabur (lihat bagian tentang Functors di situs web tutorial-ocaml ini ).

Dapatkah seseorang dengan ramah mendefinisikan istilah tersebut, menjelaskan penggunaannya, dan mungkin memberikan contoh bagaimana Functors dibuat dan digunakan?

Sunting : Sementara saya tertarik pada teori di balik istilah, saya kurang tertarik pada teori daripada saya dalam implementasi dan penggunaan praktis dari konsep.

Sunting 2 : Sepertinya ada beberapa terminologi lintas yang terjadi: Saya secara khusus merujuk pada Functors dari pemrograman fungsional, bukan objek fungsi C ++.

Erik Forbes
sumber
4
Lihat juga: adit.io/posts/…
Vlad the Impala
Jawaban yang cukup bagus juga: stackoverflow.com/a/45149475/1498178
toraritte
Jika Anda lebih tertarik pada implementasi dan penggunaan praktis daripada pada terminologi stratosfer dan teori di balik konsep, Anda hanya perlu satu liner: seorang functor memperlihatkan fungsi "peta".
Richard Gomes
@RichardGomes IMHO Saya pikir ini mengurangi peran functor ke antarmuka sederhana seperti Java, yang tidak. Sebuah functor mengubah barang, ia membangun tipe baru dari yang sudah ada (dalam Haskell) yang berarti bahwa tipe tersebut juga dipetakan. fmapmemetakan fungsi. Ada dua jenis pemetaan yang terlibat. Cara melihat hal-hal itu akan membantu memahami teori kategori (yang lebih umum). Maksud saya menarik untuk memahami teori kategori dasar untuk membantu kami dengan semua hal teori kategori di Haskell (functor, monads, ...).
Ludovic Kuty
@VladtheImpala Posting blog fantastis tetapi, meskipun sangat membantu, saya ingin diingat bahwa functor membangun (memetakan ke) jenis lain. Saya terutama menyukai kalimat "F functor mengambil setiap tipe T dan memetakannya ke tipe FT baru" di Monads seperti burrito . IMHO itu bukan hanya konteks (kotak) di sekitar nilai bahkan jika itu terbukti praktis untuk melihat hal-hal seperti ini (Haskell PoV vs teori kategori PoV?)
Ludovic Kuty

Jawaban:

273

Kata "functor" berasal dari teori kategori, yang merupakan cabang matematika yang sangat umum dan sangat abstrak. Ini telah dipinjam oleh desainer bahasa fungsional setidaknya dalam dua cara yang berbeda.

  • Dalam keluarga bahasa ML, functor adalah modul yang mengambil satu atau lebih modul lainnya sebagai parameter. Ini dianggap sebagai fitur canggih, dan kebanyakan programmer pemula mengalami kesulitan dengannya.

    Sebagai contoh implementasi dan penggunaan praktis, Anda dapat mendefinisikan bentuk favorit pohon pencarian biner seimbang Anda sekali dan untuk semua sebagai functor, dan sebagai parameter, sebuah modul yang menyediakan:

    • Jenis kunci yang akan digunakan dalam pohon biner

    • Fungsi pemesanan total pada tombol

    Setelah Anda melakukan ini, Anda dapat menggunakan implementasi pohon biner seimbang yang sama selamanya. (Jenis nilai yang disimpan dalam pohon biasanya dibiarkan polimorfik — pohon tidak perlu melihat nilai-nilai selain menyalinnya, sedangkan pohon pasti harus dapat membandingkan kunci, dan mendapatkan fungsi perbandingan dari parameter functor.)

    Aplikasi lain dari functors ML adalah protokol jaringan berlapis . Tautannya ke makalah yang sangat hebat oleh kelompok CMU Fox; ini menunjukkan bagaimana menggunakan functors untuk membangun lapisan protokol yang lebih kompleks (seperti TCP) pada jenis lapisan yang lebih sederhana (seperti IP atau bahkan langsung melalui Ethernet). Setiap lapisan diimplementasikan sebagai functor yang mengambil sebagai parameter, lapisan di bawahnya. Struktur perangkat lunak sebenarnya mencerminkan cara orang berpikir tentang masalah, sebagai lawan dari lapisan yang ada hanya di benak programmer. Pada tahun 1994 ketika karya ini diterbitkan, itu adalah masalah besar.

    Untuk contoh liar dari functors ML yang sedang bekerja, Anda bisa melihat makalah ML Module Mania , yang berisi contoh functors yang dapat dipublikasikan (yaitu, menakutkan) di tempat kerja. Untuk penjelasan yang cemerlang, jelas, dan pucat mengenai sistem modul ML (dengan perbandingan untuk modul jenis lain), bacalah beberapa halaman pertama dari kertas POPL 1994 karya Xavier Leroy yang brilian , Jenis Manifest, Modul, dan Kompilasi Terpisah .

  • Dalam Haskell, dan dalam beberapa bahasa fungsional murni terkait, Functoradalah kelas tipe . Tipe milik kelas tipe (atau lebih teknis, tipe "adalah turunan dari" kelas tipe) ketika tipe menyediakan operasi tertentu dengan perilaku yang diharapkan tertentu. Tipe Tdapat menjadi milik kelas Functorjika memiliki perilaku seperti koleksi tertentu:

    • Tipe Tini diparameterisasi daripada tipe lain, yang harus Anda anggap sebagai tipe elemen koleksi. Jenis koleksi penuh kemudian sesuatu seperti T Int, T String, T Bool, jika Anda mengandung bilangan bulat, string, atau boolean masing-masing. Jika tipe elemen tidak diketahui, ini ditulis sebagai parameter tipe a , seperti pada T a.

      Contohnya termasuk daftar (nol atau lebih elemen tipe a), Maybetipe (nol atau satu elemen tipe a), set elemen tipe a, array elemen tipe a, semua jenis pohon pencarian yang mengandung nilai tipe a, dan banyak lagi yang Anda dapat memikirkan.

    • Properti lain yang Tharus dipenuhi adalah bahwa jika Anda memiliki fungsi tipe a -> b(fungsi pada elemen), maka Anda harus dapat mengambil fungsi itu dan produk terkait fungsi pada koleksi. Anda melakukan ini dengan operator fmap, yang dibagikan oleh setiap jenis di Functorkelas tipe. Operator sebenarnya kelebihan beban, jadi jika Anda memiliki fungsi evendengan tipe Int -> Bool, maka

      fmap even

      adalah fungsi kelebihan beban yang dapat melakukan banyak hal luar biasa:

      • Konversikan daftar bilangan bulat menjadi daftar Boolean

      • Ubah pohon bilangan bulat menjadi pohon Boolean

      • Konversikan Nothingke Nothingdan Just 7keJust False

      Di Haskell, properti ini diekspresikan dengan memberikan jenis fmap:

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

      di mana kita sekarang memiliki yang kecil t, yang berarti "semua tipe di Functorkelas."

    Untuk membuat cerita panjang pendek, di Haskell functor adalah semacam koleksi yang jika Anda diberi fungsi pada elemen, fmapakan memberi Anda kembali fungsi pada koleksi . Seperti yang dapat Anda bayangkan, ini adalah sebuah ide yang dapat digunakan kembali secara luas, itulah sebabnya ia diberkati sebagai bagian dari perpustakaan standar Haskell.

Seperti biasa, orang-orang terus menciptakan baru, abstraksi berguna, dan Anda mungkin ingin melihat ke dalam aplikatif functors, yang referensi terbaik mungkin kertas yang disebut Aplikatif Programming dengan Efek oleh Conor McBride dan Ross Paterson.

Norman Ramsey
sumber
7
Saya mengerti baik fungsi-ML dan fungsi-Haskell, tetapi tidak memiliki wawasan untuk menghubungkannya bersama. Apa hubungan antara keduanya, dalam arti kategori-teoretis?
Wei Hu
6
@ Wei Hu: Teori kategori tidak pernah masuk akal bagi saya. Yang terbaik yang bisa saya katakan adalah bahwa ketiga gagasan tersebut melibatkan pemetaan.
Norman Ramsey
16
Menurut wiki Haskell ini: en.wikibooks.org/wiki/Haskell/Category_theory , itu seperti ini: Kategori adalah kumpulan objek dan morfisme (fungsi), di mana morfisme dari objek dalam kategori ke objek lain dalam kategori itu . Functor adalah fungsi yang memetakan objek dan morfisme dari satu kategori ke objek dan morfisme di kategori lain. Setidaknya begitulah aku memahaminya. Apa artinya tepatnya untuk pemrograman yang belum saya mengerti.
paul
5
@ norman-ramsey, sudahkah Anda melihat Matematika Konseptual oleh Lawvere dan Schanuel? Saya benar-benar pemula di daerah ini tetapi buku ini benar-benar dapat dibaca dan - berani-saya-katakan - menyenangkan. (Senang penjelasan Anda.)
Ram Rajamony
2
then you have to be able to take that function and product a related function on collectionsApakah maksud Anda producealih-alih product?
problemofficer
64

Jawaban lain di sini sudah lengkap, tetapi saya akan mencoba penjelasan lain tentang penggunaan FP dari functor . Anggap ini sebagai analogi:

Sebuah functor adalah wadah dari jenis yang yang, ketika mengalami fungsi yang peta dari suatub , menghasilkan sebuah wadah dari jenis b .

Berbeda dengan penggunaan fungsi-pointer-abstrak di C ++, di sini functor bukanlah fungsi; melainkan, itu adalah sesuatu yang berperilaku konsisten ketika mengalami suatu fungsi .

seh
sumber
3
Wadah tipe b berarti "wadah yang sama dengan wadah input, tetapi sekarang diisi dengan b's". Jadi jika kita memiliki daftar pisang, dan kita memetakan fungsi yang mengambil pisang dan menghasilkan salad buah, kita sekarang memiliki daftar salad buah. Demikian juga, jika kita memiliki pohon pisang, dan kita memetakan fungsi yang sama, kita sekarang akan memiliki pohon apel. Dll pohon dan daftar adalah dua Functors di sini.
Qqwy
3
"Seorang functor adalah sebuah wadah bertipe a yang, ketika mengalami suatu fungsi" - sebenarnya adalah sebaliknya - fungsi (morfisme) tunduk pada functor, untuk dipetakan ke dalam morfisme lain
Dmitri Zaitsev
38

Ada tiga arti berbeda, tidak banyak terkait!

  • Dalam Ocaml itu adalah modul parametrized. Lihat manual . Saya pikir cara terbaik untuk grok mereka adalah dengan contoh: (ditulis dengan cepat, mungkin 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);;

Anda sekarang dapat menambahkan dengan cepat banyak pesanan yang mungkin, cara untuk membentuk pesanan baru, melakukan pencarian biner atau linear dengan mudah. Pemrograman generik FTW.

  • Dalam bahasa pemrograman fungsional seperti Haskell, itu berarti beberapa konstruktor tipe (tipe parametrized seperti daftar, set) yang dapat "dipetakan". Tepatnya, functor fdilengkapi dengan (a -> b) -> (f a -> f b). Ini berasal dari teori kategori. Artikel Wikipedia yang Anda tautkan adalah penggunaan ini.

    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

Jadi, ini adalah jenis khusus konstruktor tipe, dan tidak ada hubungannya dengan functors di Ocaml!

  • Dalam bahasa imperatif, ini adalah penunjuk untuk berfungsi.
sdcvvc
sumber
Bukankah <q> peta </q> dalam 3 baris terakhir dari komentar ini memang <q> fmap </q>?
imz - Ivan Zakharyaschev
1
Saya selalu membaca bahwa functors adalah wadah - tetapi ini hanya penyederhanaan yang buruk. Jawaban Anda akhirnya memberikan tautan yang hilang: Functors adalah kelas tipe (tipe kendala) untuk tipe parameter (tipe konstruktor). Sesederhana itu!
16

Di OCaml, ini adalah modul parameter.

Jika Anda tahu C ++, pikirkan functor OCaml sebagai templat. C ++ hanya memiliki templat kelas, dan fungsi berfungsi pada skala modul.

Contoh dari functor adalah Map.Make; module StringMap = Map.Make (String);;membangun modul peta yang berfungsi dengan peta yang dikunci menggunakan String.

Anda tidak dapat mencapai sesuatu seperti StringMap hanya dengan polimorfisme; Anda perlu membuat beberapa asumsi pada tombol. Modul String berisi operasi (perbandingan, dll) pada tipe string yang benar-benar dipesan, dan functor akan menghubungkan ke operasi yang berisi modul String. Anda bisa melakukan sesuatu yang mirip dengan pemrograman berorientasi objek, tetapi Anda akan memiliki metode overhead tipuan.

Tobu
sumber
Saya mendapatkannya dari situs web ocaml - tapi saya tidak mengerti apa yang akan digunakan oleh modul parameter.
Erik Forbes
4
@ Kornel Ya, apa yang saya jelaskan adalah konsep OCaml. Konsep lainnya hanyalah "nilai fungsional", yang tidak ada bedanya dalam FP. @ Erik saya sedikit berkembang, tetapi dokumen referensi lambat dimuat.
Tobu
13

Anda mendapat beberapa jawaban yang bagus. Saya akan melempar:

Sebuah functor, dalam pengertian matematika, adalah jenis fungsi khusus pada aljabar. Ini adalah fungsi minimal yang memetakan aljabar ke aljabar lain. "Minimalitas" dinyatakan oleh hukum functor.

Ada dua cara untuk melihatnya. Sebagai contoh, daftar adalah fungsi atas beberapa tipe. Artinya, diberi aljabar di atas tipe 'a', Anda bisa menghasilkan aljabar daftar yang berisi hal-hal tipe 'a' yang kompatibel. (Misalnya: peta yang membawa elemen ke daftar tunggal yang mengandungnya: f (a) = [a]) Sekali lagi, gagasan kompatibilitas dinyatakan oleh hukum functor.

Di sisi lain, diberi functor f "over" tipe a, (yaitu, fa adalah hasil dari penerapan functor f pada aljabar tipe a), dan fungsi dari g: a -> b, kita dapat menghitung functor baru F = (fmap g) yang memetakan fa ke f b. Singkatnya, fmap adalah bagian dari F yang memetakan "bagian-bagian functor" ke "bagian-bagian functor", dan g adalah bagian dari fungsi yang memetakan "bagian-bagian aljabar" ke "bagian-bagian aljabar". Dibutuhkan fungsi, functor, dan setelah selesai, itu IS functor juga.

Tampaknya bahasa yang berbeda menggunakan gagasan yang berbeda tentang functors, tetapi mereka tidak. Mereka hanya menggunakan functors pada aljabar yang berbeda. OCamls memiliki aljabar modul, dan fungsi atas aljabar itu memungkinkan Anda melampirkan deklarasi baru ke modul dengan cara yang "kompatibel".

Functor Haskell BUKAN kelas tipe. Ini adalah tipe data dengan variabel bebas yang memenuhi kelas tipe. Jika Anda ingin menggali ke dalam tipe data (tanpa variabel gratis), Anda dapat menafsirkan kembali tipe data sebagai functor atas aljabar yang mendasarinya. Sebagai contoh:

data F = F Int

isomorfik untuk kelas Ints. Jadi F, sebagai konstruktor nilai, adalah fungsi yang memetakan Int ke F Int, aljabar yang setara. Ini adalah functor. Di sisi lain, Anda tidak mendapatkan fmap secara gratis di sini. Untuk itulah pencocokan pola.

Functor bagus untuk "menempelkan" benda ke elemen aljabar, dengan cara yang sesuai secara aljabar.

pengguna276631
sumber
8

Jawaban terbaik untuk pertanyaan itu ditemukan di "Typeclassopedia" oleh Brent Yorgey.

Edisi Monad Reader ini memuat definisi yang tepat tentang apa itu functor dan juga banyak konsep lainnya serta diagram. (Monoid, Aplikatif, Monad, dan konsep lainnya dijelaskan dan dilihat sehubungan dengan functor).

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

kutipan dari Typeclassopedia for Functor: "Intuisi sederhana adalah bahwa Functor mewakili" wadah "dari beberapa jenis, bersama dengan kemampuan untuk menerapkan fungsi secara seragam untuk setiap elemen dalam wadah"

Tapi sebenarnya seluruh typeclassopedia adalah bacaan yang sangat direkomendasikan yang sangat mudah. Di satu sisi Anda bisa melihat typeclass yang disajikan di sana sebagai paralel dengan pola desain dalam objek dalam arti bahwa mereka memberi Anda kosa kata untuk perilaku atau kemampuan yang diberikan.

Bersulang

JFT
sumber
7

Ada contoh yang cukup bagus dalam buku O'Reilly OCaml yang ada di situs web Inria (yang saat ini sayangnya sedang down). Saya menemukan contoh yang sangat mirip dalam buku ini yang digunakan oleh caltech: Pengantar OCaml (tautan pdf) . Bagian yang relevan adalah bab tentang functors (Halaman 139 dalam buku, halaman 149 dalam PDF).

Dalam buku itu mereka memiliki functor yang disebut MakeSet yang membuat struktur data yang terdiri dari daftar, dan fungsi untuk menambahkan elemen, menentukan apakah suatu elemen ada dalam daftar, dan untuk menemukan elemen. Fungsi perbandingan yang digunakan untuk menentukan apakah itu di / tidak di set telah parametrized (yang membuat MakeSet sebagai functor bukan modul).

Mereka juga memiliki modul yang mengimplementasikan fungsi perbandingan sehingga tidak bisa dibandingkan dengan case string.

Menggunakan functor dan modul yang mengimplementasikan perbandingan, mereka dapat membuat modul baru dalam satu baris:

module SSet = MakeSet(StringCaseEqual);;

yang membuat modul untuk struktur data yang menggunakan perbandingan case-sensitive. Jika Anda ingin membuat set yang menggunakan perbandingan case sensitif maka Anda hanya perlu menerapkan modul perbandingan baru alih-alih modul struktur data baru.

Tobu membandingkan functors dengan templat di C ++ yang menurut saya cukup tepat.

Niki Yoshiuchi
sumber
6

Mengingat jawaban lain dan apa yang akan saya poskan sekarang, saya akan mengatakan bahwa itu adalah kata yang agak kelebihan beban, tapi tetap saja ...

Untuk petunjuk tentang arti kata 'functor' di Haskell, tanyakan 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

Jadi, pada dasarnya, functor di Haskell adalah sesuatu yang bisa dipetakan. Cara lain untuk mengatakannya adalah bahwa functor adalah sesuatu yang dapat dianggap sebagai wadah yang dapat diminta untuk menggunakan fungsi yang diberikan untuk mengubah nilai yang dikandungnya; dengan demikian, untuk daftar, fmapbertepatan dengan map, untuk Maybe, fmap f (Just x) = Just (f x), fmap f Nothing = Nothingdll

Sub- bagian typeclass Functor dan bagian tentang Functors, Functors Applicative dan Monoids of Learn You a Haskell for Great Good memberikan beberapa contoh di mana konsep khusus ini berguna. (Rangkuman: banyak tempat! :-))

Perhatikan bahwa monad apa pun dapat diperlakukan sebagai functor, dan pada kenyataannya, seperti yang ditunjukkan Craig Stuntz, functors yang paling sering digunakan cenderung menjadi monads ... OTOH, kadang-kadang lebih mudah untuk membuat jenis instance dari typeclass Functor tanpa harus bersusah payah menjadikannya Monad. (Misalnya dalam hal ZipListdari Control.Applicative, disebutkan pada salah satu halaman yang disebutkan sebelumnya .)

Michał Marczyk
sumber
5

Berikut ini adalah artikel tentang functors dari POV pemrograman , diikuti oleh lebih spesifik bagaimana mereka muncul dalam bahasa pemrograman .

Penggunaan praktis dari functor ada di monad, dan Anda dapat menemukan banyak tutorial tentang monad jika Anda mencarinya.

Craig Stuntz
sumber
1
"Penggunaan praktis dari functor adalah dalam monad" - tidak hanya. Semua monad adalah functors, tetapi ada banyak kegunaan untuk functors non-monad.
amindfv
1
Saya akan mengatakan bahwa mempelajari monad untuk menggunakan functors seperti menabung untuk Rolls untuk membeli bahan makanan.
Marco Faustinelli
5

Dalam komentar untuk jawaban yang terpilih , pengguna Wei Hu bertanya:

Saya mengerti baik fungsi-ML dan fungsi-Haskell, tetapi tidak memiliki wawasan untuk menghubungkannya bersama. Apa hubungan antara keduanya, dalam arti kategori-teoretis?

Catatan : Saya tidak tahu ML, jadi tolong maafkan dan perbaiki kesalahan terkait.

Pada awalnya mari kita asumsikan bahwa kita semua akrab dengan definisi 'kategori' dan 'functor'.

Jawaban yang ringkas adalah "Haskell-functors" adalah (endo-) functors F : Hask -> Hasksementara "ML-functors" adalah functors G : ML -> ML'.

Di sini, Haskadalah kategori yang dibentuk oleh jenis Haskell dan fungsi antara mereka, dan sama MLdan ML'merupakan kategori yang didefinisikan oleh struktur ML.

Catatan : Ada beberapa masalah teknis dengan membuat Haskkategori, tetapi ada beberapa cara untuk mengatasinya.

Dari perspektif teori kategori, ini berarti bahwa Hask-functor adalah peta Fjenis Haskell:

data F a = ...

bersama dengan peta fmapfungsi Haskell:

instance Functor F where
    fmap f = ...

ML hampir sama, meskipun tidak ada fmapabstraksi kanonik yang saya sadari, jadi mari kita mendefinisikan satu:

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

Itu adalah fpeta ML-tipe dan fmappeta ML-fungsi, jadi

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

adalah functor F: StructA -> StructB.

Ncat
sumber
5

"Functor adalah pemetaan objek dan morfisme yang mempertahankan komposisi dan identitas suatu kategori."

Mari kita tentukan apa itu kategori?

Itu banyak benda!

Gambar beberapa titik (untuk saat ini 2 titik, satu adalah 'a' yang lain adalah 'b') di dalam lingkaran dan beri nama lingkaran itu A (Kategori) untuk saat ini.

Apa yang dimiliki oleh kategori tersebut?

Komposisi antara objek dan fungsi Identitas untuk setiap objek.

Jadi, kita harus memetakan objek dan mempertahankan komposisi setelah menerapkan Functor kita.

Mari kita bayangkan 'A' adalah kategori kami yang memiliki objek ['a', 'b'] dan ada morfisme a -> b

Sekarang, kita harus mendefinisikan functor yang dapat memetakan objek dan morfisma ini ke dalam kategori lain 'B'.

Katakanlah functor disebut 'Maybe'

data Maybe a = Nothing | Just a

Jadi, kategori 'B' terlihat seperti ini.

Harap gambar lingkaran lain tetapi kali ini dengan 'Mungkin a' dan 'Mungkin b' alih-alih 'a' dan 'b'.

Semuanya tampak baik dan semua benda dipetakan

'a' menjadi 'Maybe a' dan 'b' menjadi 'Maybe b'.

Tetapi masalahnya adalah kita harus memetakan morfisme dari 'a' ke 'b' juga.

Itu berarti morfisme a -> b dalam 'A' harus memetakan ke morfisme 'Mungkin a' -> 'Mungkin b'

morfisme dari a -> b disebut f, lalu morfisme dari 'Mungkin a' -> 'Mungkin b' disebut 'fmap f'

Sekarang mari kita lihat fungsi apa yang dilakukan 'f' di 'A' dan lihat apakah kita dapat mereplikasi di 'B'

definisi fungsi 'f' di 'A':

f :: a -> b

f mengambil a dan mengembalikan b

definisi fungsi 'f' di 'B':

f :: Maybe a -> Maybe b

f mengambil Mungkin a dan kembali Mungkin b

mari kita lihat bagaimana cara menggunakan fmap untuk memetakan fungsi 'f' dari 'A' berfungsi 'fmap f' di 'B'

definisi fmap

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

Jadi, apa yang kita lakukan di sini?

Kami menerapkan fungsi 'f' ke 'x' yang bertipe 'a'. Pencocokan pola khusus 'Tidak Ada' berasal dari definisi Functor Maybe.

Jadi, kami memetakan objek kami [a, b] dan morfisme [f] dari kategori 'A' ke kategori 'B'.

Functor Itu!

masukkan deskripsi gambar di sini

Sumanth Kumar Mora
sumber
Jawaban yang menarik. Saya ingin melengkapinya dengan Monads seperti burrito (jawaban lucu untuk Abstraksi, intuisi, dan “tutorial keliru monad” ) dan kalimatnya "F functor mengambil setiap jenis T dan memetakannya ke tipe baru FT" alias konstruktor tipe . Pemrograman Fungsional dan Teori Kategori - Kategori dan Functor juga berguna.
Ludovic Kuty
3

Ikhtisar Kasar

Dalam pemrograman fungsional, functor pada dasarnya adalah konstruksi mengangkat fungsi unary biasa (yaitu yang dengan satu argumen) ke fungsi antara variabel tipe baru. Adalah jauh lebih mudah untuk menulis dan memelihara fungsi-fungsi sederhana antara objek-objek biasa dan menggunakan functors untuk mengangkatnya, kemudian untuk menulis fungsi-fungsi secara manual antara objek-objek kontainer yang rumit. Keuntungan selanjutnya adalah menulis fungsi sederhana hanya sekali dan kemudian menggunakannya kembali melalui fungsi yang berbeda.

Contoh functors termasuk array, "mungkin" dan "baik" functors, futures (lihat misalnya https://github.com/Avaq/Fluture ), dan banyak lainnya.

Ilustrasi

Pertimbangkan fungsi membangun nama orang lengkap dari nama depan dan belakang. Kita dapat mendefinisikannya fullName(firstName, lastName)sebagai fungsi dari dua argumen, yang bagaimanapun tidak akan cocok untuk functors yang hanya berurusan dengan fungsi dari satu argumen. Untuk memperbaiki, kami mengumpulkan semua argumen dalam satu objek name, yang sekarang menjadi argumen tunggal fungsi:

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

Sekarang bagaimana jika kita memiliki banyak orang dalam array? Alih-alih membaca daftar secara manual, kita cukup menggunakan kembali fungsi kita fullNamemelalui mapmetode yang disediakan untuk array dengan satu baris kode pendek:

fullNameList = nameList => nameList.map(fullName)

dan menggunakannya seperti

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

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

Itu akan bekerja, setiap kali setiap entri di kami nameListadalah objek yang menyediakan keduanya firstNamedan lastNameproperti. Tetapi bagaimana jika beberapa objek tidak (atau bahkan tidak objek sama sekali)? Untuk menghindari kesalahan dan membuat kode lebih aman, kita dapat membungkus objek kita ke dalam Maybetipe (mis. 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()

di mana Just(name)sebuah wadah hanya membawa nama yang valid dan Nothing()merupakan nilai khusus yang digunakan untuk yang lainnya. Sekarang alih-alih menyela (atau lupa) untuk memeriksa validitas argumen kita, kita dapat menggunakan kembali (mengangkat) fullNamefungsi asli kita dengan satu baris kode, berdasarkan lagi pada mapmetode, kali ini disediakan untuk jenis Maybe:

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

dan menggunakannya seperti

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

Kategori Teori

Sebuah Functor di Teori Kategori adalah peta antara dua kategori menghormati komposisi morphisms mereka. Dalam Bahasa Komputer , Kategori utama yang diminati adalah yang objeknya adalah tipe (set nilai tertentu), dan yang morfismenya berfungsi f:a->bdari satu tipe ake tipe lainnya b.

Misalnya, anggap asebagai Stringtipe, btipe Number, dan ffungsi memetakan string menjadi panjangnya:

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

Di sini a = Stringmewakili himpunan semua string dan b = Numberhimpunan semua angka. Dalam pengertian itu, baik adan bmewakili objek dalam Set Kategori (yang terkait erat dengan kategori jenis, dengan perbedaan yang tidak penting di sini). Dalam Kategori Set, morfisme antara dua set adalah semua fungsi dari set pertama menjadi yang kedua. Jadi fungsi panjang kita di fsini adalah morfisme dari himpunan string ke himpunan angka.

Karena kita hanya mempertimbangkan kategori yang ditetapkan, Fungsi yang relevan dari itu ke dalam dirinya sendiri adalah peta yang mengirimkan objek ke objek dan morfisme ke morfisme, yang memenuhi hukum aljabar tertentu.

Contoh: Array

Arraydapat berarti banyak hal, tetapi hanya satu hal yang merupakan Functor - konstruk tipe, memetakan tipe amenjadi tipe [a]semua array tipe a. Misalnya, Arrayfunctor memetakan tipe String ke dalam tipe [String](himpunan semua array string dengan panjang sewenang-wenang), dan mengatur tipe Numberke dalam tipe yang sesuai [Number](himpunan semua array angka).

Penting untuk tidak membingungkan peta Functor

Array :: a => [a]

dengan morfisme a -> [a]. Functor hanya memetakan (mengaitkan) tipe ake dalam tipe [a]sebagai satu hal ke hal lainnya. Bahwa setiap jenis sebenarnya adalah serangkaian elemen, tidak ada relevansinya di sini. Sebaliknya, morfisme adalah fungsi aktual antara set tersebut. Misalnya, ada morfisme alami (fungsi)

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

yang mengirimkan nilai ke array 1-elemen dengan nilai itu sebagai entri tunggal. Fungsi itu bukan bagian dari ArrayFunctor! Dari sudut pandang functor ini, purehanya fungsi seperti yang lain, tidak ada yang istimewa.

Di sisi lain, ArrayFunctor memiliki bagian kedua - bagian morfisme. Yang memetakan morfisme f :: a -> bmenjadi morfisme [f] :: [a] -> [b]:

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

Berikut arrini adalah array dengan panjang sewenang-wenang dengan nilai tipe a, dan arr.map(f)merupakan array dengan panjang yang sama dengan nilai tipe b, yang entrinya merupakan hasil dari penerapan fentri arr. Untuk membuatnya berfungsi, hukum matematika pemetaan identitas ke identitas dan komposisi untuk komposisi harus dipegang, yang mudah diperiksa dalam Arraycontoh ini .

Dmitri Zaitsev
sumber
2

Tidak bertentangan dengan jawaban teoritis atau matematika sebelumnya, tetapi Functor juga merupakan Obyek (dalam bahasa pemrograman Berorientasi Objek) yang hanya memiliki satu metode dan secara efektif digunakan sebagai fungsi.

Contohnya adalah antarmuka Runnable di Jawa, yang hanya memiliki satu metode: jalankan.

Pertimbangkan contoh ini, pertama dalam Javascript, yang memiliki fungsi kelas satu:

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

Output: [1, 4, 25, 100]

Metode peta mengambil fungsi dan mengembalikan array baru dengan setiap elemen menjadi hasil dari penerapan fungsi tersebut ke nilai pada posisi yang sama di array asli.

Untuk melakukan hal yang sama adalah Java, menggunakan Functor, pertama-tama Anda perlu mendefinisikan antarmuka, katakan:

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

Kemudian, jika Anda menambahkan kelas koleksi yang memiliki fungsi peta, Anda bisa melakukan:

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

Ini menggunakan subclass in-line dari IntMapFunction untuk membuat Functor, yang merupakan OO yang setara dengan fungsi dari contoh JavaScript sebelumnya.

Menggunakan Functors memungkinkan Anda menerapkan teknik fungsional dalam bahasa OO. Tentu saja, beberapa bahasa OO juga memiliki dukungan untuk fungsi secara langsung, jadi ini tidak diperlukan.

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

Kevin Greer
sumber
Sebenarnya "objek fungsi" bukan deskripsi yang benar dari sebuah functor. Misalnya Arrayadalah functor, tetapiArray(value) hanya memberikan array 1 elemen.
Dmitri Zaitsev
0

KISS: functor adalah objek yang memiliki metode peta.

Array dalam JavaScript implement map dan karenanya berfungsi. Janji, Aliran, dan Pohon sering menerapkan peta dalam bahasa fungsional, dan ketika itu dilakukan, mereka dianggap sebagai pelaku. Metode peta functor mengambil kontennya sendiri dan mentransformasikan masing-masingnya menggunakan callback transformasi yang diteruskan ke peta, dan mengembalikan functor baru, yang berisi struktur sebagai functor pertama, tetapi dengan nilai yang diubah.

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

soundyogi
sumber
1
Dengan catatan samping bahwa 'objek' harus diambil secara luas dan hanya berarti 'sesuatu'. Untuk bahasa OOP, misalnya, ganti objek untuk kelas . Orang bisa mengatakan 'sebuah functor adalah kelas yang mengimplementasikan antarmuka Functor' (Tentu saja, antarmuka ini mungkin tidak ada secara fisik di sana, tetapi Anda dapat mengangkat logika 'peta' ke antarmuka itu, dan mintalah semua kelas pemetaan Anda membaginya - selama sistem tipe Anda memungkinkan mengetik hal-hal umum ini, yaitu).
Qqwy
1
Saya menemukan Kelas super membingungkan untuk jujur, di satu sisi mereka hanya cetak biru untuk sesuatu yang konkret / tetapi mereka mungkin juga memiliki metode (barang statis) dan dapat berperilaku seperti objek. Apakah Kelas mengimplementasikan antarmuka atau instance yang dibuatnya?
soundyogi
1
Ya, mereka bisa membingungkan. Tetapi: Kelas mengimplementasikan antarmuka (mereka 'mengisi' kekosongan yang diberikan dalam metode antarmuka. Dengan kata lain: Mereka mengubah pedoman abstrak antarmuka dalam pedoman konkret yang dapat langsung (maafkan permainan kata) yang dipakai). Mengenai 'kelas berperilaku seperti objek': Dalam bahasa yang benar-benar OOP seperti Ruby, Kelas adalah turunan dari Kelas 'Kelas'. Ini kura-kura sepanjang jalan.
Qqwy
Arraytipe konstruksi mendefinisikan sebuah fungsi tunggal. Contohnya juga disebut "array" tetapi mereka bukan functors. Deskripsi di sini harus dibuat lebih tepat.
Dmitri Zaitsev
@DmitriZaitsev Bisakah Anda menguraikan? Jadi apa yang Anda katakan adalah bahwa instance bukan functors? Saya tidak melihat perasaan karena Anda mendapatkan functor baru dengan memetakan satu.
soundyogi
-4

Dalam praktiknya, functor berarti objek yang mengimplementasikan operator panggilan di C ++. Dalam ocaml saya pikir functor mengacu pada sesuatu yang mengambil modul sebagai input dan output modul lain.

feng
sumber
-6

Sederhananya, sebuah functor, atau objek fungsi, adalah objek kelas yang bisa disebut seperti fungsi.

Dalam C ++:

Ini adalah bagaimana Anda menulis suatu fungsi

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

Ini adalah bagaimana Anda menulis functor

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

Sekarang Anda bisa melakukan ini:

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

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

Apa yang membuat ini sangat hebat adalah Anda dapat mempertahankan status di kelas - bayangkan jika Anda ingin menanyakan fungsi berapa kali ia dipanggil. Tidak ada cara untuk melakukan ini dengan cara yang rapi, dikemas. Dengan objek fungsi, sama seperti kelas lain: Anda akan memiliki beberapa variabel instan yang Anda tambahkanoperator () dan beberapa metode untuk memeriksa variabel itu, dan semuanya rapi seperti yang Anda inginkan.

Mat
sumber
12
Tidak, fungsi-fungsi itu bukan tipe teori yang digunakan oleh bahasa FP.
Tobu
1
Saya bisa melihat bagaimana seseorang dapat membuktikan bahwa FunctorClassmemenuhi Hukum Functor pertama, tetapi bisakah Anda membuat sketsa bukti untuk Hukum kedua? Saya tidak begitu melihatnya.
Jörg W Mittag
3
Bah, kalian benar. Saya mencoba memecahkan "web telah memberikan deskripsi teknis yang sangat banyak" dan melampaui, mencoba untuk menghindari, "Dalam keluarga bahasa ML, functor adalah modul yang mengambil satu atau lebih modul lain sebagai parameter." Namun, jawaban ini, yah, buruk. Terlalu disederhanakan dan tidak ditentukan. Saya tergoda untuk menghapusnya, tetapi saya akan membiarkan generasi mendatang menggelengkan kepala mereka :)
Matt
Saya senang Anda meninggalkan jawaban dan komentar, karena membantu membingkai masalah. Terima kasih! Saya mengalami kesulitan karena sebagian besar jawaban ditulis dalam bentuk Haskell atau OCaml, dan bagi saya itu sedikit mirip dengan menjelaskan buaya dalam hal buaya.
Rob
-10

Functor tidak secara spesifik terkait dengan pemrograman fungsional. Itu hanya "penunjuk" ke suatu fungsi atau beberapa jenis objek, yang dapat disebut sebagai fungsi.

alemjerus
sumber
8
Ada konsep FP spesifik dari functor (dari teori kategori), tetapi Anda benar bahwa kata yang sama juga digunakan untuk hal-hal lain dalam bahasa non-FP.
Craig Stuntz
Apakah Anda yakin bahwa pointer fungsi adalah Functors? Saya tidak melihat bagaimana fungsi pointer memenuhi dua Hukum Functor, terutama Hukum Functor Kedua (pelestarian komposisi morfisme). Apakah Anda punya bukti untuk itu? (Hanya sketsa kasar.)
Jörg W Mittag