Dalam bahasa fungsional murni, apakah ada algoritma untuk mendapatkan fungsi invers?

100

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?

MaiaVictor
sumber
5
Secara matematis tidak salah untuk mengatakan bahwa, dalam kasus 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.
Karolis Juodelė
2
Jawaban yang benar adalah YA, tetapi tidak efisien. Misalkan f: A -> B dan A finite, maka, jika b € B, Anda "hanya" harus memeriksa semua f (A) untuk menemukan semua a € A yang f (a) = b. Dalam komputer kuantum, mungkin akan memiliki kompleksitas O (ukuran (a)). Tentu saja, Anda mencari algoritme praktis. Itu tidak (memiliki O (2 ^ size (a))), tetapi ada ...
josejuan
QuickCheck melakukannya dengan tepat (mereka mencari False di f: A -> Bool).
josejuan
4
@ KarolisJuodelė: Saya tidak setuju; itu tidak biasanya yang dimaksud dengan invers. Hampir setiap kali saya menemukan istilah tersebut, kebalikan dari fadalah fungsi gseperti itu f . g = iddan g . f = id. Kandidat Anda bahkan tidak mengecek dalam kasus itu.
Ben Millwood
3
@ Benillwood, Anda benar. Apa yang saya katakan disebut gambar terbalik, bukan fungsi terbalik. Maksud saya adalah bahwa jawaban yang menunjukkan yang f x = 1tidak memiliki kebalikan mengambil pendekatan yang sangat sempit dan mengabaikan seluruh kompleksitas masalah.
Karolis Juodelė

Jawaban:

101

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.

Daniel Wagner
sumber
3
Berikut adalah makalah yang lebih baru yang mensurvei keadaan seni dalam dua arah. Ini mencakup tiga kelompok teknik, termasuk "sintaksis" dan pendekatan berbasis kombinator juga: iai.uni-bonn.de/~jv/ssgip-bidirectional-final.pdf
sclv
Dan hanya untuk menyebutkan, pada tahun 2008 ada pesan ini ke -cafe, dengan peretasan jahat untuk membalikkan putfungsi ke dalam struktur record apa pun yang berasal Data: 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".
sclv
Sekarang tahun 2017 dan tentu saja tautan ke makalah tidak berlaku lagi di sini adalah yang diperbarui: pdfs.semanticscholar.org/5f0d/…
Mina Gabriel
37

Tidak, itu tidak mungkin secara umum.

Bukti: pertimbangkan fungsi bijektiva dari tipe

type F = [Bit] -> [Bit]

dengan

data Bit = B0 | B1

Asumsikan kita memiliki inverter inv :: F -> Fseperti itu inv f . f ≡ id. Katakanlah kita telah mengujinya untuk fungsinya f = id, dengan mengonfirmasi itu

inv f (repeat B0) -> (B0 : ls)

Karena ini pertama B0dalam keluaran pasti datang setelah beberapa waktu yang terbatas, kami memiliki batas atas npada kedua kedalaman yang invsebenarnya telah mengevaluasi masukan pengujian kami untuk mendapatkan hasil ini, serta berapa kali ia dapat dipanggil f. Definisikan sekarang keluarga fungsi

g j (B1 : B0 : ... (n+j times) ... B0 : ls)
   = B0 : ... (n+j times) ... B0 : B1 : ls
g j (B0 : ... (n+j times) ... B0 : B1 : ls)
   = B1 : B0 : ... (n+j times) ... B0 : ls
g j l = l

Jelas, untuk semua 0<j≤n, g jadalah bijeksi, sebenarnya pembalikan diri. Jadi kita harus bisa memastikannya

inv (g j) (replicate (n+j) B0 ++ B1 : repeat B0) -> (B1 : ls)

tetapi untuk memenuhi ini, inv (g j)akan membutuhkan keduanya

  • evaluasi g j (B1 : repeat B0)ke kedalamann+j > n
  • mengevaluasi head $ g j lsetidaknya npencocokan daftar yang berbedareplicate (n+j) B0 ++ B1 : ls

Hingga saat itu, setidaknya satu file g j tidak dapat dibedakan dari f, dan karena inv ftidak melakukan salah satu dari evaluasi ini, invtidak mungkin dapat membedakannya - selain melakukan beberapa pengukuran waktu proses sendiri, yang hanya mungkin di IO Monad.

                                                                                                                                   ⬜

kiri sekitar
sumber
19

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:

f :: a -> Int
f _ = 1

Fungsi ini tidak memiliki kebalikan.

mck
sumber
1
Apakah salah jika mengatakan bahwa fmemang memiliki invers, hanya saja invers tersebut adalah fungsi non-deterministik?
Matt Fenwick
10
@MattFenwick Dalam bahasa seperti Haskell misalnya, fungsi bukanlah non-deterministik (tanpa mengubah jenis dan cara Anda menggunakannya). Tidak ada fungsi Haskell g :: Int -> ayang merupakan kebalikan dari f, bahkan jika Anda dapat menggambarkan kebalikan dari fmatematis.
Ben
2
@ Matt: Cari "bawah" dalam pemrograman dan logika fungsional. Sebuah "bottom" adalah nilai "tidak mungkin", baik karena kontradiktif, non-terminating, atau solusi untuk masalah yang tidak dapat diputuskan (ini lebih dari sekedar kontradiktif - kita secara metodis dapat "mengejar" solusi saat kita mengeksplorasi desain spasi menggunakan "tidak ditentukan" dan "kesalahan" selama pengembangan). A "bottom" x memiliki tipe a. Itu "mendiami" (atau merupakan "nilai") dari setiap jenis. Ini adalah kontradiksi logis, karena tipe adalah proposisi dan tidak ada nilai yang memenuhi setiap proposisi. Lihat Haskell-Cafe untuk diskusi yang bagus
nomen
2
@ Mat: Daripada mencirikan tidak adanya invers dalam istilah non-determinisme, seseorang harus mencirikannya dalam istilah dasar. Kebalikan dari f _ = 1 adalah bagian bawah, karena ia harus menempati setiap jenis (sebagai alternatif, ia adalah bagian bawah karena f tidak memiliki fungsi pembalikan untuk jenis apa pun dengan lebih dari satu elemen - aspek yang Anda fokuskan, menurut saya). Menjadi terbawah dapat diambil baik secara positif maupun negatif sebagai pernyataan tentang nilai. Seseorang dapat dengan bijaksana berbicara tentang kebalikan dari fungsi arbitrer sebagai "nilai" yang paling bawah. (Meskipun itu bukan nilai yang "benar-benar")
nomen
1
Setelah berjalan kembali ke sini lama kemudian, saya pikir saya melihat apa yang Matt maksudkan: kita sering membuat model nondeterminisme melalui daftar, dan kita dapat melakukan hal yang sama untuk invers. Misalkan kebalikan dari f x = 2 * xmenjadi f' x = [x / 2], dan kemudian kebalikan dari f _ = 1adalah f' 1 = [minBound ..]; f' _ = []. Artinya, ada banyak pembalikan untuk 1, dan tidak ada untuk nilai lain.
amalloy
16

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.

amalloy
sumber
1
Atau Mercury , yang memiliki semangat Haskell yang sama. - Poin bagus, +1.
kiri sekitar sekitar
11

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

Satu set istilah lambda adalah nontrivial jika tidak kosong maupun set lengkap. Jika A dan B adalah dua himpunan suku lambda nontrivial yang ditutup di bawah persamaan (beta), maka A dan B tidak dapat dipisahkan secara rekursif.

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

Petr Pudlák
sumber
11

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:

inv :: Eq b => [a] -> (a -> b) -> (b -> a)
inv domain f b = head [ a | a <- domain, f a == b ]

Karena Anda telah menyatakan itu fsebuah 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 dari Integermenjadi Integer, 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]. Memang inv (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 Bijectionantara tipe adan b:

data Bi a b = Bi {
    apply :: a -> b,
    invert :: b -> a 
}

bersama dengan banyak konstanta (di mana Anda dapat mengatakan 'Saya tahu itu bijections!') sesuka Anda, seperti:

notBi :: Bi Bool Bool
notBi = Bi not not

add1Bi :: Bi Integer Integer
add1Bi = Bi (+1) (subtract 1)

dan beberapa kombinator cerdas, seperti:

idBi :: Bi a a 
idBi = Bi id id

invertBi :: Bi a b -> Bi b a
invertBi (Bi a i) = (Bi i a)

composeBi :: Bi a b -> Bi b c -> Bi a c
composeBi (Bi a1 i1) (Bi a2 i2) = Bi (a2 . a1) (i1 . i2)

mapBi :: Bi a b -> Bi [a] [b]
mapBi (Bi a i) = Bi (map a) (map i)

bruteForceBi :: Eq b => [a] -> (a -> b) -> Bi a b
bruteForceBi domain f = Bi f (inv domain f)

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

yatima2975
sumber
6

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 itu fmemang bjiection. Anda dapat menghitung kebalikannya f' :: b -> adengan cara yang sangat bodoh:

import Data.List

-- | Class for types whose values are recursively enumerable.
class Enumerable a where
    -- | Produce the list of all values of type @a@.
    enumerate :: [a]

 -- | Note, this is only guaranteed to terminate if @f@ is a bijection!
invert :: (Enumerable a, Eq b) => (a -> b) -> b -> Maybe a
invert f b = find (\a -> f a == b) enumerate

Jika fbijection dan enumeratebenar - benar menghasilkan semua nilai a, maka pada akhirnya Anda akan mencapai asedemikian rupaf a == b .

Jenis yang memiliki a Bounded dan Enuminstance dapat dibuat dengan mudah RecursivelyEnumerable. Pasangan Enumerablejenis juga bisa dibuat Enumerable:

instance (Enumerable a, Enumerable b) => Enumerable (a, b) where
    enumerate = crossWith (,) enumerate enumerate

crossWith :: (a -> b -> c) -> [a] -> [b] -> [c]
crossWith f _ [] = []
crossWith f [] _ = []
crossWith f (x0:xs) (y0:ys) =
    f x0 y0 : interleave (map (f x0) ys) 
                         (interleave (map (flip f y0) xs)
                                     (crossWith f xs ys))

interleave :: [a] -> [a] -> [a]
interleave xs [] = xs
interleave [] ys = []
interleave (x:xs) ys = x : interleave ys xs

Hal yang sama berlaku untuk disjungsi Enumerabletipe:

instance (Enumerable a, Enumerable b) => Enumerable (Either a b) where
    enumerate = enumerateEither enumerate enumerate

enumerateEither :: [a] -> [b] -> [Either a b]
enumerateEither [] ys = map Right ys
enumerateEither xs [] = map Left xs
enumerateEither (x:xs) (y:ys) = Left x : Right y : enumerateEither xs ys

Fakta bahwa kita bisa melakukan ini berdua (,) dan Eithermungkin berarti bahwa kita bisa melakukannya untuk tipe data aljabar apa pun.

Luis Casillas
sumber
5

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!

Jeffrey Scofield
sumber
13
Sistem kriptografi apa pun (tidak termasuk beberapa yang aneh, seperti satu tombol waktu, yang tidak layak karena alasan lain) dapat dipecahkan dengan kekerasan. Itu tidak membuat mereka kurang berguna, dan juga tidak akan menjadi fungsi inversi yang mahal secara tidak praktis.
Benarkah? jika Anda menganggap fungsi enkripsi String encrypt(String key, String text)tanpa kunci, Anda tetap tidak dapat melakukan apa pun. EDIT: Ditambah apa yang dikatakan delnan.
mck
@MaciekAlbin Tergantung pada model serangan Anda. Serangan teks biasa yang dipilih, misalnya, memungkinkan ekstraksi kunci, yang kemudian akan memungkinkan penyerangan teks sandi lain yang dienkripsi dengan kunci itu.
Yang saya maksud dengan "layak" adalah, sesuatu yang dapat dilakukan dalam waktu berapa pun. Saya tidak bermaksud "dapat dihitung" (saya cukup yakin).
Jeffrey Scofield
@Jereyfield Saya mengerti maksud Anda. Tapi saya harus mengatakan, saya bingung dengan "layak dalam teori" - bukankah (definisi kami) kelayakan hanya mengacu pada seberapa sulit untuk dilakukan secara praktis?
5

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:

bijective_function x = x*2+1

main = do
    print $ bijective_function 3
    print $ inverse_function bijective_function (bijective_function 3)

data Expr = X | Const Double |
            Plus Expr Expr | Subtract Expr Expr | Mult Expr Expr | Div Expr Expr |
            Negate Expr | Inverse Expr |
            Exp Expr | Log Expr | Sin Expr | Atanh Expr | Sinh Expr | Acosh Expr | Cosh Expr | Tan Expr | Cos Expr |Asinh Expr|Atan Expr|Acos Expr|Asin Expr|Abs Expr|Signum Expr|Integer
       deriving (Show, Eq)

instance Num Expr where
    (+) = Plus
    (-) = Subtract
    (*) = Mult
    abs = Abs
    signum = Signum
    negate = Negate
    fromInteger a = Const $ fromIntegral a

instance Fractional Expr where
    recip = Inverse
    fromRational a = Const $ realToFrac a
    (/) = Div

instance Floating Expr where
    pi = Const pi
    exp = Exp
    log = Log
    sin = Sin
    atanh = Atanh
    sinh = Sinh
    cosh = Cosh
    acosh = Acosh
    cos = Cos
    tan = Tan
    asin = Asin
    acos = Acos
    atan = Atan
    asinh = Asinh

fromFunction f = f X

toFunction :: Expr -> (Double -> Double)
toFunction X = \x -> x
toFunction (Negate a) = \a -> (negate a)
toFunction (Const a) = const a
toFunction (Plus a b) = \x -> (toFunction a x) + (toFunction b x)
toFunction (Subtract a b) = \x -> (toFunction a x) - (toFunction b x)
toFunction (Mult a b) = \x -> (toFunction a x) * (toFunction b x)
toFunction (Div a b) = \x -> (toFunction a x) / (toFunction b x)


with_function func x = toFunction $ func $ fromFunction x

simplify X = X
simplify (Div (Const a) (Const b)) = Const (a/b)
simplify (Mult (Const a) (Const b)) | a == 0 || b == 0 = 0 | otherwise = Const (a*b)
simplify (Negate (Negate a)) = simplify a
simplify (Subtract a b) = simplify ( Plus (simplify a) (Negate (simplify b)) )
simplify (Div a b) | a == b = Const 1.0 | otherwise = simplify (Div (simplify a) (simplify b))
simplify (Mult a b) = simplify (Mult (simplify a) (simplify b))
simplify (Const a) = Const a
simplify (Plus (Const a) (Const b)) = Const (a+b)
simplify (Plus a (Const b)) = simplify (Plus (Const b) (simplify a))
simplify (Plus (Mult (Const a) X) (Mult (Const b) X)) = (simplify (Mult (Const (a+b)) X))
simplify (Plus (Const a) b) = simplify (Plus (simplify b) (Const a))
simplify (Plus X a) = simplify (Plus (Mult 1 X) (simplify a))
simplify (Plus a X) = simplify (Plus (Mult 1 X) (simplify a))
simplify (Plus a b) = (simplify (Plus (simplify a) (simplify b)))
simplify a = a

inverse X = X
inverse (Const a) = simplify (Const a)
inverse (Mult (Const a) (Const b)) = Const (a * b)
inverse (Mult (Const a) X) = (Div X (Const a))
inverse (Plus X (Const a)) = (Subtract X (Const a))
inverse (Negate x) = Negate (inverse x)
inverse a = inverse (simplify a)

inverse_function x = with_function inverse x

Contoh ini hanya berfungsi dengan ekspresi aritmatika, tetapi mungkin dapat digeneralisasikan untuk bekerja dengan daftar juga.

Anderson Green
sumber
4

Tidak, bahkan tidak semua fungsi memiliki invers. Misalnya, apa invers dari fungsi ini?

f x = 1
Dirk Holsopple
sumber
Fungsi Anda adalah konstanta, ini tentang fungsi bijektiva.
Soleil - Mathieu Prévot