Dalam bahasa fungsional murni seperti Haskell, apakah ada algoritma untuk mendapatkan kebalikan dari suatu fungsi, (sunting) jika itu bersifat bijektiva? Dan adakah cara khusus untuk memprogram fungsi Anda?
haskell
clojure
functional-programming
ocaml
MaiaVictor
sumber
sumber
f x = 1
, invers dari 1 adalah himpunan bilangan bulat dan invers dari yang lainnya adalah himpunan kosong. Terlepas dari apa yang dikatakan beberapa jawaban, fungsi bukan bijective bukanlah masalah terbesar.f
adalah fungsig
seperti ituf . g = id
dang . f = id
. Kandidat Anda bahkan tidak mengecek dalam kasus itu.f x = 1
tidak memiliki kebalikan mengambil pendekatan yang sangat sempit dan mengabaikan seluruh kompleksitas masalah.Jawaban:
Dalam beberapa kasus, ya! Ada makalah indah yang disebut Bidirectionalization for Free!yang membahas beberapa kasus - jika fungsi Anda cukup polimorfik - jika memungkinkan, secara otomatis mendapatkan fungsi invers. (Ini juga membahas apa yang membuat masalah menjadi sulit bila fungsinya tidak polimorfik.)
Apa yang Anda dapatkan jika fungsi Anda dapat dibalik adalah kebalikannya (dengan input palsu); dalam kasus lain, Anda mendapatkan fungsi yang mencoba "menggabungkan" nilai masukan lama dan nilai keluaran baru.
sumber
put
fungsi ke dalam struktur record apa pun yang berasalData
: haskell.org/pipermail/haskell-cafe/2008-April/042193.html menggunakan pendekatan yang mirip dengan yang kemudian disajikan (lebih ketat, lebih umum, lebih berprinsip, dll.) dalam "gratis".Tidak, itu tidak mungkin secara umum.
Bukti: pertimbangkan fungsi bijektiva dari tipe
dengan
Asumsikan kita memiliki inverter
inv :: F -> F
seperti ituinv f . f ≡ id
. Katakanlah kita telah mengujinya untuk fungsinyaf = id
, dengan mengonfirmasi ituKarena ini pertama
B0
dalam keluaran pasti datang setelah beberapa waktu yang terbatas, kami memiliki batas atasn
pada kedua kedalaman yanginv
sebenarnya telah mengevaluasi masukan pengujian kami untuk mendapatkan hasil ini, serta berapa kali ia dapat dipanggilf
. Definisikan sekarang keluarga fungsiJelas, untuk semua
0<j≤n
,g j
adalah bijeksi, sebenarnya pembalikan diri. Jadi kita harus bisa memastikannyatetapi untuk memenuhi ini,
inv (g j)
akan membutuhkan keduanyag j (B1 : repeat B0)
ke kedalamann+j > n
head $ g j l
setidaknyan
pencocokan daftar yang berbedareplicate (n+j) B0 ++ B1 : ls
Hingga saat itu, setidaknya satu file
g j
tidak dapat dibedakan darif
, dan karenainv f
tidak melakukan salah satu dari evaluasi ini,inv
tidak mungkin dapat membedakannya - selain melakukan beberapa pengukuran waktu proses sendiri, yang hanya mungkin diIO Monad
.⬜
sumber
Anda dapat mencarinya di wikipedia, ini disebut Komputasi Terbalik .
Secara umum Anda tidak dapat melakukannya dan tidak ada bahasa fungsional yang memiliki opsi itu. Sebagai contoh:
Fungsi ini tidak memiliki kebalikan.
sumber
f
memang memiliki invers, hanya saja invers tersebut adalah fungsi non-deterministik?g :: Int -> a
yang merupakan kebalikan darif
, bahkan jika Anda dapat menggambarkan kebalikan darif
matematis.f x = 2 * x
menjadif' x = [x / 2]
, dan kemudian kebalikan darif _ = 1
adalahf' 1 = [minBound ..]; f' _ = []
. Artinya, ada banyak pembalikan untuk 1, dan tidak ada untuk nilai lain.Tidak dalam sebagian besar bahasa fungsional, tetapi dalam pemrograman logika atau pemrograman relasional, sebagian besar fungsi yang Anda tetapkan sebenarnya bukanlah fungsi tetapi "relasi", dan ini dapat digunakan di kedua arah. Lihat misalnya prolog atau kanren.
sumber
Tugas seperti ini hampir selalu tidak dapat diputuskan. Anda dapat memiliki solusi untuk beberapa fungsi tertentu, tetapi tidak secara umum.
Di sini, Anda bahkan tidak dapat mengenali fungsi mana yang memiliki kebalikan. Mengutip Barendregt, HP The Lambda Calculus: Sintaks dan Semantiknya. Holland Utara, Amsterdam (1984) :
Mari kita ambil A sebagai himpunan suku lambda yang mewakili fungsi yang dapat dibalik dan B sisanya. Keduanya tidak kosong dan ditutup dalam persamaan beta. Jadi tidak mungkin untuk memutuskan apakah suatu fungsi dapat dibalik atau tidak.
(Ini berlaku untuk kalkulus lambda yang tidak berjenis. TBH Saya tidak tahu apakah argumennya dapat langsung disesuaikan dengan kalkulus lambda yang diketik ketika kita mengetahui jenis fungsi yang ingin kita balikkan. Tapi saya cukup yakin itu akan terjadi serupa.)
sumber
Jika Anda dapat menghitung domain fungsi dan dapat membandingkan elemen rentang untuk persamaan, Anda dapat - dengan cara yang cukup mudah. Dengan menyebutkan maksud saya memiliki daftar semua elemen yang tersedia. Saya akan tetap menggunakan Haskell, karena saya tidak tahu Ocaml (atau bahkan cara memanfaatkannya dengan benar ;-)
Apa yang ingin Anda lakukan adalah menjalankan melalui elemen domain dan melihat apakah mereka sama dengan elemen rentang yang Anda coba balikkan, dan ambil yang pertama yang berfungsi:
Karena Anda telah menyatakan itu
f
sebuah perhiasan, pasti ada satu dan hanya satu elemen semacam itu. Triknya, tentu saja, adalah memastikan bahwa penghitungan domain Anda benar-benar mencapai semua elemen dalam waktu yang terbatas . Jika Anda mencoba membalikkan bijeksi dariInteger
menjadiInteger
, penggunaan[0,1 ..] ++ [-1,-2 ..]
tidak akan berhasil karena Anda tidak akan pernah mendapatkan angka negatif. Secara konkret,inv ([0,1 ..] ++ [-1,-2 ..]) (+1) (-3)
tidak akan pernah menghasilkan nilai.Namun,
0 : concatMap (\x -> [x,-x]) [1..]
akan berfungsi, karena ini berjalan melalui bilangan bulat dalam urutan berikut[0,1,-1,2,-2,3,-3, and so on]
. Memanginv (0 : concatMap (\x -> [x,-x]) [1..]) (+1) (-3)
segera kembali-4
!The Control.Monad.Omega paket dapat membantu Anda menjalankan melalui daftar tupel sebagainya dengan cara yang baik; Saya yakin ada lebih banyak paket seperti itu - tetapi saya tidak mengetahuinya.
Tentu saja, pendekatan ini agak kasar dan kasar, belum lagi jelek dan tidak efisien! Jadi saya akan mengakhiri dengan beberapa komentar di bagian terakhir pertanyaan Anda, tentang bagaimana 'menulis' bijections. Sistem tipe Haskell tidak cukup untuk membuktikan bahwa suatu fungsi adalah sesuatu yang bijak - Anda benar-benar menginginkan sesuatu seperti Agda untuk itu - tetapi ia bersedia mempercayai Anda.
(Peringatan: mengikuti kode yang belum diuji)
Jadi, dapatkah Anda menentukan tipe data
Bijection
antara tipea
danb
:bersama dengan banyak konstanta (di mana Anda dapat mengatakan 'Saya tahu itu bijections!') sesuka Anda, seperti:
dan beberapa kombinator cerdas, seperti:
Saya pikir Anda kemudian bisa melakukan
invert (mapBi add1Bi) [1,5,6]
dan mendapatkan[0,4,5]
. Jika Anda memilih kombinator dengan cara yang cerdas, saya rasa berapa kali Anda harus menulis fileBi
konstanta dengan tangan bisa sangat terbatas.Lagi pula, jika Anda tahu suatu fungsi adalah bijeksi, semoga Anda memiliki sketsa bukti fakta itu di kepala Anda, yang seharusnya dapat diubah oleh isomorfisme Curry-Howard menjadi sebuah program :-)
sumber
Saya baru-baru ini berurusan dengan masalah seperti ini, dan tidak, saya akan mengatakan bahwa (a) tidak sulit dalam banyak kasus, tetapi (b) tidak efisien sama sekali.
Pada dasarnya, anggap saja Anda punya
f :: a -> b
, dan ituf
memang bjiection. Anda dapat menghitung kebalikannyaf' :: b -> a
dengan cara yang sangat bodoh:Jika
f
bijection danenumerate
benar - benar menghasilkan semua nilaia
, maka pada akhirnya Anda akan mencapaia
sedemikian rupaf a == b
.Jenis yang memiliki a
Bounded
danEnum
instance dapat dibuat dengan mudahRecursivelyEnumerable
. PasanganEnumerable
jenis juga bisa dibuatEnumerable
:Hal yang sama berlaku untuk disjungsi
Enumerable
tipe:Fakta bahwa kita bisa melakukan ini berdua
(,)
danEither
mungkin berarti bahwa kita bisa melakukannya untuk tipe data aljabar apa pun.sumber
Tidak setiap fungsi memiliki kebalikan. Jika Anda membatasi pembahasan pada fungsi satu-ke-satu, kemampuan untuk membalikkan fungsi arbitrer memberikan kemampuan untuk memecahkan kriptosistem apa pun. Kami agak berharap ini tidak mungkin, bahkan secara teori!
sumber
String encrypt(String key, String text)
tanpa kunci, Anda tetap tidak dapat melakukan apa pun. EDIT: Ditambah apa yang dikatakan delnan.Dalam beberapa kasus, dimungkinkan untuk menemukan kebalikan dari fungsi bijektiva dengan mengubahnya menjadi representasi simbolik. Berdasarkan contoh ini , saya menulis program Haskell ini untuk menemukan invers dari beberapa fungsi polinomial sederhana:
Contoh ini hanya berfungsi dengan ekspresi aritmatika, tetapi mungkin dapat digeneralisasikan untuk bekerja dengan daftar juga.
sumber
Tidak, bahkan tidak semua fungsi memiliki invers. Misalnya, apa invers dari fungsi ini?
sumber