Nilai "Mengingat" dalam pemrograman fungsional

Saya telah memutuskan untuk mengambil sendiri tugas belajar pemrograman fungsional. Sejauh ini merupakan ledakan, dan saya 'melihat cahaya' seolah-olah. Sayangnya, saya tidak benar-benar tahu ada programmer fungsional yang saya dapat memunculkan pertanyaan. Memperkenalkan Stack Exchange.

Saya mengambil kursus pengembangan web / perangkat lunak, tetapi instruktur saya tidak terbiasa dengan pemrograman fungsional. Dia baik-baik saja dengan saya menggunakannya, dan dia hanya meminta saya untuk membantunya memahami cara kerjanya sehingga dia dapat membaca kode saya lebih baik.

Saya memutuskan cara terbaik untuk melakukan ini adalah dengan menggambarkan fungsi matematika sederhana, seperti meningkatkan nilai ke kekuatan. Secara teori saya bisa dengan mudah melakukan itu dengan fungsi prebuilt, tetapi itu akan mengalahkan tujuan contoh.

Ngomong-ngomong, saya mengalami beberapa kesulitan mencari tahu bagaimana cara mempertahankan nilai. Karena ini adalah pemrograman fungsional saya tidak dapat mengubah variabel. Jika saya harus kode ini secara imperatif, itu akan terlihat seperti ini:

(Berikut ini semua kodesemu)

f(x,y) {
  int z = x;
  for(int i = 0, i < y; i++){
    x = x * z;
  }
  return x;
}

Dalam pemrograman fungsional, saya tidak yakin. Inilah yang saya pikirkan:

f(x,y,z){
  if z == 'null',
    f(x,y,x);
  else if y > 1,
    f(x*z,y-1,z);
  else
    return x;
}

Apakah ini benar? Saya perlu memegang nilai, zdalam kedua kasus, tetapi saya tidak yakin bagaimana melakukan ini dalam pemrograman fungsi. Secara teori, cara saya melakukannya, tetapi saya tidak yakin apakah itu 'benar'. Apakah ada cara yang lebih baik untuk melakukannya?

Pertama-tama, selamat atas "melihat cahaya". Anda telah menjadikan dunia perangkat lunak tempat yang lebih baik dengan memperluas wawasan Anda.

Kedua, sejujurnya tidak ada seorang profesor yang tidak memahami pemrograman fungsional akan dapat mengatakan sesuatu yang berguna tentang kode Anda, selain dari komentar basi seperti "lekukan yang terlihat". Ini tidak terlalu mengejutkan dalam kursus pengembangan web, karena sebagian besar pengembangan web dilakukan menggunakan HTML / CSS / JavaScript. Bergantung pada seberapa besar Anda benar-benar peduli tentang belajar pengembangan web, Anda mungkin ingin berupaya mempelajari alat-alat yang diajarkan profesor Anda (meskipun mungkin menyakitkan - saya tahu dari pengalaman).

Untuk menjawab pertanyaan yang dinyatakan: jika kode imperatif Anda menggunakan loop, maka kemungkinan kode fungsional Anda akan bersifat rekursif.

(* raises x to the power of y *)
fun pow (x: real) (y: int) : real = 
    if y = 1 then x else x * (pow x (y-1))

Perhatikan bahwa algoritma ini sebenarnya kurang lebih identik dengan kode imperatif. Bahkan, orang dapat menganggap loop di atas sebagai gula sintaksis untuk proses rekursif berulang.

Sebagai catatan, tidak perlu nilai z kode imperatif atau fungsional Anda. Anda seharusnya menulis fungsi imperatif Anda seperti ini:

def pow(x, y):
    var ret = 1
    for (i = 0; i < y; i++)
         ret = ret * x
    return ret

alih-alih mengubah arti variabel x.

Ini benar-benar hanya tambahan untuk jawaban gardenhead, tapi saya ingin menunjukkan ada nama untuk pola yang Anda lihat: melipat.

Dalam pemrograman fungsional, lipatan adalah cara untuk menggabungkan serangkaian nilai yang "mengingat" nilai antara setiap operasi. Pertimbangkan untuk menambahkan daftar angka secara imperatif:

def sum_all(xs):
  total = 0
  for x in xs:
    total = total + x
  return total

Kami mengambil daftar nilai xsdan keadaan awal dari 0(diwakili oleh totaldalam hal ini). Kemudian, untuk masing-masing xdalam xs, kami menggabungkan nilai itu dengan keadaan saat ini sesuai dengan beberapa operasi penggabungan (dalam hal ini penambahan), dan menggunakan hasilnya sebagai keadaan baru . Intinya, sum_all([1, 2, 3])setara dengan (3 + (2 + (1 + 0))). Pola ini dapat diekstraksi menjadi fungsi urutan yang lebih tinggi , fungsi yang menerima fungsi sebagai argumen:

def fold(items, initial_state, combiner_func):
  state = initial_state
  for item in items:
    state = combiner_func(item, state)
  return state

def sum_all(xs):
  return fold(xs, 0, lambda x y: x + y)

Implementasi foldini masih sangat penting, tetapi dapat dilakukan secara rekursif juga:

def fold_recursive(items, initial_state, combiner_func):
  if not is_empty(items):
    state = combiner_func(initial_state, first_item(items))
    return fold_recursive(rest_items(items), state, combiner_func)
  else:
    return initial_state

Disajikan dalam bentuk lipatan, fungsi Anda hanyalah:

def exponent(base, power):
  return fold(repeat(base, power), 1, lambda x y: x * y))

... tempat repeat(x, n)mengembalikan daftar nsalinan x.

Banyak bahasa, terutama yang diarahkan pada pemrograman fungsional, menawarkan pelipatan di perpustakaan standar mereka. Bahkan Javascript menyediakannya dengan nama reduce. Secara umum, jika Anda mendapati diri Anda menggunakan rekursi untuk "mengingat" suatu nilai pada suatu lingkaran, Anda mungkin menginginkan lipatan.

Ini adalah jawaban tambahan untuk membantu menjelaskan peta dan lipatan. Untuk contoh di bawah ini, saya akan menggunakan daftar ini. Ingat, daftar ini tidak dapat diubah, sehingga tidak akan pernah berubah:

var numbers = [1, 2, 3, 4, 5]

Saya akan menggunakan angka dalam contoh saya karena mereka menyebabkan kode mudah dibaca. Ingat juga, lipatan dapat digunakan untuk apa pun yang dapat digunakan untuk loop imperatif tradisional.

Sebuah peta mengambil daftar sesuatu, dan fungsi, dan mengembalikan daftar yang telah dimodifikasi menggunakan fungsi. Setiap item diteruskan ke fungsi, dan menjadi apa pun fungsi kembali.

Contoh termudah dari ini adalah hanya menambahkan nomor ke setiap nomor dalam daftar. Saya akan menggunakan pseudocode untuk menjadikannya agnostik bahasa:

function add-two(n):
    return n + 2

var numbers2 =
    map(add-two, numbers) 

Jika Anda mencetak numbers2, Anda akan melihat daftar [3, 4, 5, 6, 7]mana yang pertama dengan 2 ditambahkan ke setiap elemen. Perhatikan fungsi add-twoitu diberikan kepadamap untuk digunakan.

Lipatan serupa, kecuali fungsi yang Anda harus berikan harus mengambil 2 argumen. Argumen pertama biasanya akumulator (dalam lipatan kiri, yang paling umum). Akumulator adalah data yang dilewati saat perulangan. Argumen kedua adalah item saat ini dari daftar; seperti di atas untuk mapfungsi.

function add-together(n1, n2):
    return n1 + n2

var sum =
    fold(add-together, 0, numbers)

Jika Anda mencetak, sumAnda akan melihat jumlah dari daftar angka: 15.

Inilah yang harus dilakukan argumen fold:

1. Ini adalah fungsi yang kami beri lipatan. Lipatan akan melewati fungsi akumulator saat ini, dan item saat ini dari daftar. Apapun fungsi yang dikembalikan akan menjadi akumulator baru, yang akan diteruskan ke fungsi lain kali. Ini adalah bagaimana Anda "mengingat" nilai ketika Anda mengulang gaya FP. Saya memberinya fungsi yang mengambil 2 angka dan menambahkannya.

2. Ini adalah akumulator awal; apa akumulator mulai seperti sebelum item dalam daftar diproses. Saat Anda menjumlahkan angka, berapa totalnya sebelum Anda menambahkan angka apa pun? 0, yang saya sampaikan sebagai argumen kedua.

3. Terakhir, seperti halnya peta, kami juga memasukkan daftar angka untuk diproses.

Jika lipatan masih tidak masuk akal, pertimbangkan ini. Ketika Anda menulis:

# Notice I passed the plus operator directly this time, 
#  instead of wrapping it in another function. 
fold(+, 0, numbers)

Anda pada dasarnya menempatkan fungsi yang diteruskan antara setiap item dalam daftar, dan menambahkan akumulator awal ke kiri atau kanan (tergantung pada apakah itu lipatan kiri atau kanan), jadi:

[1, 2, 3, 4, 5]

Menjadi:

0 + 1 + 2 + 3 + 4 + 5
^ Note the initial accumulator being added onto the left (for a left fold).

Yang sama dengan 15.

Gunakan mapketika Anda ingin mengubah satu daftar menjadi daftar lain, dengan panjang yang sama.

Gunakan foldketika Anda ingin mengubah daftar menjadi nilai tunggal, seperti menjumlahkan daftar angka.

Sebagaimana @Jorg tunjukkan dalam komentar, "nilai tunggal" tidak perlu sesuatu yang sederhana seperti angka; bisa berupa objek tunggal, termasuk daftar atau tupel! Cara saya sebenarnya memiliki lipatan klik untuk saya adalah dengan mendefinisikan peta dalam bentuk lipatan. Perhatikan bagaimana akumulator adalah daftar:

function map(f, list):
    fold(
        function(xs, x): # xs is the list that has been processed so far
            xs.add( f(x) ) # Add returns the list instead of mutating it
        , [] # Before any of the list has been processed, we have an empty list
        , list) 

Jujur, begitu Anda memahami masing-masing, Anda akan menyadari bahwa hampir semua perulangan dapat diganti dengan lipatan atau peta.

Sulit menemukan masalah bagus yang tidak bisa diselesaikan dengan fungsionalitas bawaan. Dan jika itu dibangun, maka itu harus digunakan untuk menjadi contoh gaya yang baik dalam bahasa x.

Di haskell misalnya Anda sudah memiliki fungsi (^)di Prelude.

Atau jika Anda ingin melakukannya lebih terprogram product (replicate y x)

Apa yang saya katakan adalah sulit untuk menunjukkan kekuatan gaya / bahasa jika Anda tidak menggunakan fitur yang disediakannya. Namun itu mungkin merupakan langkah yang baik untuk menunjukkan cara kerjanya di belakang layar, tetapi saya pikir Anda harus memberi kode cara terbaik dalam bahasa apa pun yang Anda gunakan dan kemudian membantu orang dari sana untuk memahami apa yang terjadi jika diperlukan.