Apa persamaan fungsional pernyataan break imperatif dan pemeriksaan loop lainnya?

Katakanlah, saya memiliki logika di bawah ini. Bagaimana cara menulis itu dalam Pemrograman Fungsional?

    public int doSomeCalc(int[] array)
    {
        int answer = 0;
        if(array!=null)
        {
            for(int e: array)
            {
                answer += e;
                if(answer == 10) break;
                if(answer == 150) answer += 100;
            }
        }
        return answer;
    }

Contoh-contoh di sebagian besar blog, artikel ... Saya melihat hanya menjelaskan kasus sederhana dari satu fungsi matematika lurus mengatakan 'Jumlah'. Tapi, saya punya logika yang mirip dengan yang tertulis di atas di Jawa dan ingin memigrasikannya ke kode fungsional di Clojure. Jika kami tidak dapat melakukan hal di atas dalam FP, maka jenis promosi untuk FP tidak menyatakan ini secara eksplisit.

Saya tahu bahwa kode di atas benar-benar penting. Itu tidak ditulis dengan pemikiran untuk bermigrasi ke FP di masa depan.

Persamaan terdekat dengan pengulangan array dalam sebagian besar bahasa fungsional adalah foldfungsi, yaitu fungsi yang memanggil fungsi yang ditentukan pengguna untuk setiap nilai array, meneruskan nilai akumulasi di sepanjang rantai. Dalam banyak bahasa fungsional, foldditambah dengan berbagai fungsi tambahan yang menyediakan fitur tambahan, termasuk opsi untuk berhenti lebih awal ketika beberapa kondisi muncul. Dalam bahasa-bahasa malas (misalnya Haskell), berhenti lebih awal dapat dicapai hanya dengan tidak mengevaluasi lebih jauh di sepanjang daftar, yang akan menyebabkan nilai-nilai tambahan tidak pernah dihasilkan. Karenanya, menerjemahkan contoh Anda ke Haskell, saya akan menuliskannya sebagai:

doSomeCalc :: [Int] -> Int
doSomeCalc values = foldr1 combine values
  where combine v1 v2 | v1 == 10  = v1
                      | v1 == 150 = v1 + 100 + v2
                      | otherwise = v1 + v2

Memecah baris ini demi baris jika Anda tidak terbiasa dengan sintaksis Haskell, ini bekerja seperti ini:

doSomeCalc :: [Int] -> Int

Menentukan jenis fungsi, menerima daftar int dan mengembalikan satu int.

doSomeCalc values = foldr1 combine values

Bagian utama dari fungsi: argumen yang diberikan values, return foldr1dipanggil dengan argumen combine(yang akan kita definisikan di bawah) dan values. foldr1adalah varian dari primitif lipatan yang dimulai dengan akumulator yang disetel ke nilai pertama daftar (maka 1dalam nama fungsi), kemudian menggabungkannya menggunakan fungsi yang ditentukan pengguna dari kiri ke kanan (yang biasanya disebut lipatan kanan , maka rdalam nama fungsi). Jadi foldr1 f [1,2,3]sama dengan f 1 (f 2 3)(atau f(1,f(2,3))dalam sintaksis mirip C yang lebih konvensional).

  where combine v1 v2 | v1 == 10  = v1

Menentukan combinefungsi lokal: ia menerima dua argumen, v1dan v2. Kapan v110, itu hanya kembali v1. Dalam hal ini, v2 tidak pernah dievaluasi , sehingga loop berhenti di sini.

                      | v1 == 150 = v1 + 100 + v2

Atau, ketika v1 adalah 150, tambahkan 100 tambahan untuk itu, dan tambahkan v2.

                      | otherwise = v1 + v2

Dan, jika tidak satu pun dari kondisi itu benar, tambahkan saja v1 ke v2.

Sekarang, solusi ini agak spesifik untuk Haskell, karena fakta bahwa lipatan kanan berakhir jika fungsi menggabungkan tidak mengevaluasi argumen kedua disebabkan oleh strategi evaluasi malas Haskell. Saya tidak tahu Clojure, tetapi saya percaya itu menggunakan evaluasi yang ketat, jadi saya berharap itu memiliki foldfungsi di perpustakaan standar yang mencakup dukungan khusus untuk penghentian awal. Ini sering disebut foldWhile, foldUntilatau serupa.

Melihat sekilas pada dokumentasi perpustakaan Clojure menunjukkan bahwa itu sedikit berbeda dari kebanyakan bahasa fungsional dalam penamaan, dan itu foldbukan yang Anda cari (ini adalah mekanisme yang lebih maju yang bertujuan mengaktifkan komputasi paralel) tetapi reducelebih langsung setara. Pengakhiran dini terjadi jika reducedfungsi tersebut disebut dalam fungsi kombinasi Anda. Saya tidak 100% yakin saya mengerti sintaksnya, tetapi saya curiga apa yang Anda cari adalah sesuatu seperti ini:

(reduce 
    (fn [v1 v2]
        (if (= v1 10) 
             (reduced v1)
             (+ v1 v2 (if (= v1 150) 100 0))))
    array)

NB: kedua terjemahan, Haskell dan Clojure, tidak tepat untuk kode khusus ini; tetapi mereka menyampaikan intinya secara umum - lihat diskusi dalam komentar di bawah untuk masalah spesifik dengan contoh-contoh ini.

Anda dapat dengan mudah mengubahnya menjadi rekursi. Dan itu memiliki panggilan rekursif dioptimalkan ekor bagus.

Kodesemu:

public int doSomeCalc(int[] array)
{
    return doSomeCalcInner(array, 0);
}

public int doSomeCalcInner(int[] array, int answer)
{
    if (array is empty) return answer;

    // not sure how to efficiently implement head/tails array split in clojure
    var head = array[0] // first element of array
    var tail = array[1..] // remainder of array

    answer += head;
    if (answer == 10) return answer;
    if (answer == 150) answer += 100;

    return doSomeCalcInner(tail, answer);
}

Saya benar-benar menyukai jawaban Jules , tetapi saya juga ingin menunjukkan sesuatu yang sering orang lewatkan tentang pemrograman fungsional yang malas, yaitu bahwa segala sesuatu tidak harus "di dalam lingkaran." Sebagai contoh:

baseSums = scanl (+) 0

offsets = scanl (\offset sum -> if sum == 150 then offset + 100 else offset) 0

zipWithOffsets xs = zipWith (+) xs (offsets xs)

stopAt10 xs = if 10 `elem` xs then 10 else last xs

result = stopAt10 . zipWithOffsets . baseSums

result [1..]         -- 10
result [11..1000000] -- 500000499945

Anda dapat melihat bahwa setiap bagian dari logika Anda dapat dihitung dalam fungsi terpisah kemudian disusun bersama. Ini memungkinkan untuk fungsi yang lebih kecil yang biasanya lebih mudah untuk dipecahkan. Sebagai contoh mainan Anda, mungkin ini menambah lebih banyak kerumitan daripada menghilangkannya, tetapi dalam kode dunia nyata fungsi terpisah seringkali jauh lebih sederhana daripada keseluruhan.

Sebagian besar contoh pemrosesan daftar Anda akan melihat menggunakan fungsi suka map , filter, sumdll yang beroperasi pada daftar secara keseluruhan. Tetapi dalam kasus Anda, Anda memiliki keluar awal bersyarat - pola yang agak tidak biasa yang tidak didukung oleh operasi daftar yang biasa. Jadi, Anda perlu menurunkan tingkat abstraksi dan menggunakan rekursi - yang juga lebih dekat dengan bagaimana contoh imperatif terlihat.

Ini adalah terjemahan yang agak langsung (mungkin bukan idiomatik) ke Clojure:

(defn doSomeCalc 
  ([lst] (doSomeCalc lst 0))
  ([lst sum]
    (if (empty? lst) sum
        (if (= sum 10) sum
            (let [sum (+ sum (first lst))]
                 [sum (if (= sum 150) (+ sum 100) sum)]
               (recur (rest lst) sum))))))) 

Edit: Jules titik bahwa reducedi Clojure lakukan mendukung keluar awal. Menggunakan ini lebih elegan:

(defn doSomeCalc [lst]  
  (reduce (fn [sum val]
    (if (= sum 10) (reduced sum)
        (let [sum (+ sum val)]
             [sum (if (= sum 150) (+ sum 100) sum)]
           sum))
   lst)))

Bagaimanapun, Anda dapat melakukan apa saja dalam bahasa fungsional seperti yang Anda bisa dalam bahasa imperatif, tetapi Anda sering harus mengubah pola pikir Anda untuk menemukan solusi yang elegan. Dalam pengkodean imperatif Anda memikirkan memproses daftar langkah demi langkah, sementara dalam bahasa fungsional Anda mencari operasi untuk diterapkan ke semua elemen dalam daftar.

Seperti yang ditunjukkan oleh jawaban lain, Clojure memiliki reduceduntuk menghentikan pengurangan lebih awal:

(defn some-calc [coll]
  (reduce (fn [answer e]
            (let [answer (+ answer e)]
               (case answer
                 10  (reduced answer)
                 150 (+ answer 100)
                 answer)))
          0 coll))

Ini adalah solusi terbaik untuk situasi khusus Anda. Anda juga bisa mendapatkan banyak jarak tempuh dari penggabungan reduceddengan transduce, yang memungkinkan Anda menggunakan transduser dari map, filterdll. Namun itu jauh dari jawaban lengkap untuk pertanyaan umum Anda.

Escape continuations adalah versi umum dari pernyataan break and return. Mereka secara langsung diimplementasikan dalam beberapa Skema ( call-with-escape-continuation), Common Lisp ( block+ return, catch+ throw) dan bahkan C (setjmp + longjmp). Kelanjutan yang dibatasi atau tidak umum yang lebih umum seperti yang ditemukan dalam Skema standar atau sebagai kelanjutan monad di Haskell dan Scala juga dapat digunakan sebagai kelanjutan pelarian.

Misalnya, di Racket Anda dapat menggunakan let/ecseperti ini:

(define (some-calc ls)
  (let/ec break ; let break be an escape continuation
    (foldl (lambda (answer e)
             (let ([answer (+ answer e)])
               (case answer
                 [(10)  (break answer)] ; return answer immediately
                 [(150) (+ answer 100)]
                 [else  answer])))
           0 ls)))

Banyak bahasa lain juga memiliki konstruksi yang mirip kontinuitas dalam bentuk penanganan pengecualian. Dalam Haskell Anda juga bisa menggunakan salah satu dari berbagai monads kesalahan dengan foldM. Karena mereka terutama menangani kesalahan konstruksi menggunakan pengecualian atau kesalahan monads untuk pengembalian awal biasanya tidak dapat diterima secara budaya dan mungkin sangat lambat.

Anda juga dapat drop-down dari fungsi tingkat tinggi untuk mengikuti panggilan.

Saat menggunakan loop, Anda memasukkan iterasi berikutnya secara otomatis ketika Anda mencapai ujung tubuh loop. Anda dapat memasukkan iterasi berikutnya lebih awal dengan continueatau keluar dari loop dengan break(atau return). Saat menggunakan panggilan ekor (atau loopkonstruksi Clojure yang meniru rekursi ekor), Anda harus selalu membuat panggilan eksplisit untuk memasukkan iterasi berikutnya. Untuk berhenti mengulang, Anda tidak melakukan panggilan rekursif tetapi langsung memberikan nilainya:

(defn some-calc [coll]
  (loop [answer 0, [e es :as coll] coll]
    (if (empty? coll)
      answer
      (let [answer (+ answer e)]
        (case answer
          10 answer
          150 (recur (+ answer 100) es)
          (recur answer es))))))

Bagian yang rumit adalah loop. Mari kita mulai dengan itu. Sebuah loop biasanya dikonversi ke gaya fungsional dengan mengekspresikan iterasi dengan fungsi tunggal. Iterasi adalah transformasi dari variabel loop.

Berikut ini adalah implementasi fungsional dari loop umum:

loop : v -> (v -> v) -> (v -> Bool) -> v
loop init iter cond_to_cont = 
    if cond_to_cont init 
        then loop (iter init) iter cond
        else init

Dibutuhkan (nilai awal dari variabel loop, fungsi yang mengekspresikan iterasi tunggal [pada variabel loop]) (suatu kondisi untuk melanjutkan loop).

Contoh Anda menggunakan loop pada array, yang juga rusak. Kemampuan ini dalam bahasa imperatif Anda dimasukkan ke dalam bahasa itu sendiri. Dalam pemrograman fungsional, kemampuan seperti itu biasanya diimplementasikan di tingkat perpustakaan. Berikut ini adalah kemungkinan implementasi

module Array (foldlc) where

foldlc : v -> (v -> e -> v) -> (v -> Bool) -> Array e -> v
foldlc init iter cond_to_cont arr = 
    loop 
        (init, 0)
        (λ (val, next_pos) -> (iter val (at next_pos arr), next_pos + 1))
        (λ (val, next_pos) -> and (cond_to_cont val) (next_pos < size arr))

Di dalamnya:

Saya menggunakan pasangan ((val, next_pos)) yang berisi variabel loop terlihat di luar dan posisi dalam array, yang menyembunyikan fungsi ini.

Fungsi iterasi sedikit lebih kompleks daripada di loop umum, versi ini memungkinkan untuk menggunakan elemen array saat ini. [Ini dalam bentuk kari .]

Fungsi seperti itu biasanya dinamai "lipat".

Saya meletakkan "l" dalam nama untuk menunjukkan bahwa akumulasi elemen-elemen array dilakukan dengan cara asosiatif-kiri; untuk meniru kebiasaan bahasa pemrograman imperatif untuk mengulangi array dari indeks rendah ke tinggi.

Saya meletakkan "c" dalam nama untuk menunjukkan bahwa versi lipatan ini mengambil kondisi yang mengontrol jika dan kapan loop harus dihentikan lebih awal.

Tentu saja fungsi utilitas seperti itu mungkin sudah tersedia di perpustakaan dasar yang dikirimkan dengan bahasa pemrograman fungsional yang digunakan. Saya menulisnya di sini untuk demonstrasi.

Sekarang kita memiliki semua alat yang ada dalam bahasa dalam kasus imperatif, kita dapat beralih untuk mengimplementasikan fungsionalitas spesifik dari contoh Anda.

Variabel dalam loop Anda adalah pasangan ('jawaban', boolean yang mengkodekan apakah akan melanjutkan).

iter : (Int, Bool) -> Int -> (Int, Bool)
iter (answer, cont) collection_element = 
  let new_answer = answer + collection_element
  in case new_answer of
    10 -> (new_answer, false)
    150 -> (new_answer + 100, true)
    _ -> (new_answer, true)

Perhatikan bahwa saya menggunakan "variabel" 'new_answer' baru. Ini karena dalam pemrograman fungsional saya tidak dapat mengubah nilai "variabel" yang sudah diinisialisasi. Saya tidak khawatir tentang kinerja, kompiler dapat menggunakan kembali memori 'jawaban' untuk 'new_answer' melalui analisis seumur hidup, jika dianggap lebih efisien.

Memasukkan ini ke dalam fungsi loop kami yang dikembangkan sebelumnya:

doSomeCalc :: Array Int -> Int
doSomeCalc arr = fst (Array.foldlc (0, true) iter snd arr)

"Array" di sini adalah nama modul yang mengekspor fungsi foldlc.

"kepalan", "kedua" singkatan dari fungsi yang mengembalikan komponen pertama, kedua dari parameter pasangannya

fst : (x, y) -> x
snd : (x, y) -> y

Dalam hal ini gaya "point-free" meningkatkan pembacaan implementasi doSomeCalc:

doSomeCalc = Array.foldlc (0, true) iter snd >>> fst

(>>>) adalah komposisi fungsi: (>>>) : (a -> b) -> (b -> c) -> (a -> c)

Sama seperti di atas, hanya parameter "arr" yang ditinggalkan dari kedua sisi persamaan yang menentukan.

Satu hal terakhir: memeriksa case (array == null). Dalam bahasa pemrograman yang dirancang lebih baik, tetapi bahkan dalam bahasa yang dirancang dengan buruk dengan beberapa disiplin dasar orang lebih suka menggunakan jenis opsional untuk mengekspresikan ketidak-ada-an. Ini tidak ada hubungannya dengan pemrograman fungsional, yang akhirnya menjadi pertanyaan, jadi saya tidak menghadapinya.

Pertama, tulis ulang loop sedikit, sehingga setiap iterasi loop keluar lebih awal, atau bermutasi answertepat sekali:

    public int doSomeCalc(int[] array)
    {
        int answer = 0;
        if(array!=null)
        {
            for(int e: array)
            {
                if(answer + e == 10) return answer + e;
                else if(answer + e == 150) answer = answer + e + 100;
                else answer = answer + e;
            }
        }
        return answer;
    }

Seharusnya jelas bahwa perilaku versi ini persis sama dengan sebelumnya, tetapi sekarang, jauh lebih mudah untuk mengkonversi ke gaya rekursif. Ini terjemahan Haskell langsung:

doSomeCalc :: [Int] -> Int
doSomeCalc = recurse 0
  where recurse :: Int -> [Int] -> Int
        recurse answer [] = answer
        recurse answer (e:array)
          | answer + e == 10 = answer + e
          | answer + e == 150 = recurse (answer + e + 100) array
          | otherwise = recurse (answer + e) array

Sekarang ini berfungsi murni, tetapi kita bisa memperbaikinya dari sudut pandang efisiensi dan keterbacaan dengan menggunakan lipatan alih-alih rekursi eksplisit:

import Control.Monad (foldM)

doSomeCalc :: [Int] -> Int
doSomeCalc = either id id . foldM go 0
  where go :: Int -> Int -> Either Int Int
        go answer e
          | answer + e == 10 = Left (answer + e)
          | answer + e == 150 = Right (answer + e + 100)
          | otherwise = Right (answer + e)

Dalam konteks ini, Leftawal keluar dengan nilainya, dan Rightmelanjutkan rekursi dengan nilainya.

Ini sekarang dapat disederhanakan sedikit lebih, seperti ini:

import Control.Monad (foldM)

doSomeCalc :: [Int] -> Int
doSomeCalc = either id id . foldM go 0
  where go :: Int -> Int -> Either Int Int
        go answer e
          | answer' == 10 = Left 10
          | answer' == 150 = Right 250
          | otherwise = Right answer'
          where answer' = answer + e

Ini lebih baik sebagai kode Haskell akhir, tetapi sekarang agak kurang jelas bagaimana memetakan kembali ke Jawa asli.