Bisakah solusi murni-fungsional untuk masalah ini menjadi sebersih imperatif?

Saya memiliki latihan dengan Python sebagai berikut:

• polinomial diberikan sebagai tupel koefisien sehingga kekuatan ditentukan oleh indeks, misalnya: (9,7,5) berarti 9 + 7 * x + 5 * x ^ 2

• tulis fungsi untuk menghitung nilainya untuk diberikan x

Karena saya ke pemrograman fungsional belakangan ini, saya menulis

def evaluate1(poly, x):
  coeff = 0
  power = 1
  return reduce(lambda accu,pair : accu + pair[coeff] * x**pair[power],
                map(lambda x,y:(x,y), poly, range(len(poly))),
                0)

yang saya anggap tidak terbaca, jadi saya menulis

def evaluate2(poly, x):
  power = 0
  result = 1
  return reduce(lambda accu,coeff : (accu[power]+1, accu[result] + coeff * x**accu[power]),
                poly,
                (0,0)
               )[result]

yang setidaknya sama tidak terbaca, jadi saya menulis

def evaluate3(poly, x):
  return poly[0]+x*evaluate(poly[1:],x) if len(poly)>0 else 0

yang mungkin kurang efisien (sunting: saya salah!) karena menggunakan banyak perkalian alih-alih eksponensial, pada prinsipnya, saya tidak peduli tentang pengukuran di sini (sunting: Betapa bodohnya saya! Mengukur akan menunjukkan kesalahpahaman saya!) dan masih belum terbaca (bisa dibilang) sebagai solusi berulang:

def evaluate4(poly, x):
  result = 0
  for i in range(0,len(poly)):
      result += poly[i] * x**i
  return result

Apakah ada solusi murni fungsional yang dapat dibaca seperti keharusan dan mendekati efisiensi?

Memang, perubahan representasi akan membantu, tetapi ini diberikan oleh latihan.

Bisa juga Haskell atau Lisp, bukan hanya Python.

Metode Horner mungkin lebih efisien secara komputasi seperti yang ditunjukkan @delnan, tapi saya akan menyebut ini cukup mudah dibaca dengan Python untuk solusi eksponensial:

def eval_poly(poly, x):
    return sum( [a * x**i for i,a in enumerate(poly)] )

Banyak bahasa fungsional memiliki implementasi mapi yang memungkinkan Anda memiliki indeks yang dianyam melalui peta. Gabungkan itu dengan jumlah dan Anda memiliki yang berikut di F #:

let compute coefficients x = 
    coefficients 
        |> Seq.mapi (fun i c -> c * Math.Pow(x, (float)i))
        |> Seq.sum

Saya tidak mengerti bagaimana kode Anda berhubungan dengan ruang lingkup masalah yang Anda tentukan, jadi saya akan memberikan versi saya tentang apa yang kode Anda mengabaikan ruang lingkup masalahnya (berdasarkan pada kode imperatif yang Anda tulis).

Haskell yang mudah dibaca (pendekatan ini dapat dengan mudah diterjemahkan ke bahasa FP mana pun yang memiliki daftar yang merusak dan keluar murni dan dapat dibaca):

eval acc exp val [] = acc
eval acc exp val (x:xs) = eval (acc + execPoly) (exp+1) xs
  where execPoly = x * (val^exp)

Kadang-kadang pendekatan sederhana naif dalam haskell seperti itu lebih bersih daripada pendekatan yang lebih ringkas untuk orang yang kurang terbiasa dengan FP.

Pendekatan imperatif yang lebih jelas yang masih sepenuhnya murni adalah:

steval val poly = runST $ do
  accAndExp <- newSTRef (0,1)
  forM_ poly $ \x -> do
    modifySTRef accAndExp (updateAccAndExp x)
  readSTRef accAndExp
  where updateAccAndExp x (acc, exp) = (acc + x*(val^exp), exp + 1)

bonus untuk pendekatan kedua sedang di ST monad itu akan berkinerja sangat baik.

Meskipun untuk memastikan, implementasi nyata yang paling mungkin dari Haskeller adalah zipwith yang disebutkan dalam jawaban lain di atas. zipWithadalah pendekatan yang sangat khas dan saya percaya Python dapat meniru pendekatan zipping menggabungkan fungsi dan pengindeks yang dapat dipetakan.

Jika Anda hanya memiliki tuple (tetap), mengapa tidak melakukan ini (di Haskell):

evalPolyTuple (c, b, a) x = c + b*x + a*x^2

Jika Anda memiliki daftar koefisien, Anda dapat menggunakan:

evalPolyList coefs x = sum $ zipWith (\c p -> c*x^p) coefs [0..]

atau dengan potongan seperti yang Anda miliki:

evalPolyList' coefs x = foldl' (\sum (c, p) -> sum + c*x^p) 0 $ zip coefs [0..]

Ada serangkaian langkah umum yang dapat Anda gunakan untuk meningkatkan keterbacaan algoritma fungsional:

• Letakkan nama pada hasil antara Anda, alih-alih mencoba menjejalkan semuanya pada satu baris.
• Gunakan fungsi bernama alih-alih lambdas, terutama dalam bahasa dengan sintaks verbose lambda. Jauh lebih mudah untuk membaca evaluateTermdaripada ekspresi lambda yang panjang. Hanya karena Anda dapat menggunakan lambda tidak selalu berarti Anda harus melakukannya .
• Jika salah satu dari fungsi Anda yang sekarang bernama tampak seperti sesuatu yang akan muncul cukup sering, kemungkinan itu sudah ada di perpustakaan standar. Lihatlah sekeliling. Python saya sedikit berkarat, tetapi sepertinya Anda pada dasarnya diciptakan kembali enumerateatau zipWith.
• Seringkali, melihat fungsi dan hasil antara bernama membuatnya lebih mudah untuk alasan tentang apa yang terjadi dan menyederhanakannya, pada titik itu mungkin masuk akal untuk memasukkan lambda kembali atau menggabungkan beberapa garis kembali bersama.
• Jika suatu keharusan untuk loop terlihat lebih mudah dibaca, kemungkinan untuk pemahaman akan bekerja dengan baik.