Czy czysto funkcjonalne rozwiązanie tego problemu może być tak czyste jak konieczność?

Mam ćwiczenie w języku Python w następujący sposób:

• wielomian podano jako krotkę współczynników, tak że moce są określone przez indeksy, np .: (9,7,5) oznacza 9 + 7 * x + 5 * x ^ 2

• napisz funkcję do obliczenia jej wartości dla danego x

Ponieważ ostatnio interesuję się programowaniem funkcjonalnym, napisałem

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)

które uważam za nieczytelne, więc napisałem

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]

co jest co najmniej tak samo nieczytelne, jak napisałem

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

co może być mniej wydajne (edytuj: pomyliłem się!), ponieważ wykorzystuje wiele mnożeń zamiast potęgowania, w zasadzie nie dbam o pomiary tutaj (edytuj: Jak głupio ze mnie! Mierzenie wskazałoby moje błędne przekonanie!) i wciąż nie jest tak czytelny (prawdopodobnie) jak iteracyjne rozwiązanie:

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

Czy istnieje czysto funkcjonalne rozwiązanie tak czytelne, jak konieczne i bliskie wydajności?

Wprawdzie zmiana reprezentacji pomogłaby, ale dało to ćwiczenie.

Może to być również Haskell lub Lisp, nie tylko Python.

Metoda Hornera jest prawdopodobnie bardziej wydajna obliczeniowo, jak wskazuje @delnan, ale nazwałbym to dość czytelnym w Pythonie dla rozwiązania potęgującego:

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

Wiele języków funkcjonalnych ma implementacje mapi, które pozwalają na przeszukanie indeksu przez mapę. Połącz to z sumą, a otrzymasz następujące w F #:

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

Nie rozumiem, w jaki sposób twój kod odnosi się do zdefiniowanego przez ciebie zakresu problemu, dlatego podam moją wersję tego, co robi twój kod, ignorując zakres problemu (na podstawie napisanego przez ciebie kodu rozkazującego).

Dość czytelny haskell (to podejście można łatwo przetłumaczyć na dowolny język FP, który ma destrukcyjną listę i jest czysty i czytelny):

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

Czasami takie naiwne proste podejście w haskell jest czystsze niż bardziej zwięzłe podejście do osób mniej przyzwyczajonych do FP.

Bardziej wyraźnie imperatywnym podejściem, które wciąż jest całkowicie czyste, jest:

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)

premią za drugie podejście jest bycie w monadzie ST, która będzie działać bardzo dobrze.

Choć dla pewności, najbardziej prawdopodobną rzeczywistą implementacją Haskellera byłby zip wspomniany w innej odpowiedzi powyżej. zipWithjest bardzo typowym podejściem i wierzę, że Python może naśladować podejście polegające na łączeniu funkcji i indeksatora, który można zmapować.

Jeśli tylko masz (stałe) krotki, dlaczego nie jest to (w Haskell) zrobić:

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

Jeśli zamiast tego masz listę współczynników, możesz użyć:

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

lub z obniżką taką, jaką miałeś:

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

Istnieje ogólny zestaw kroków, których można użyć, aby poprawić czytelność algorytmów funkcjonalnych:

• Umieść nazwy na swoich wynikach pośrednich, zamiast próbować wcisnąć wszystko w jednym wierszu.
• Używaj nazwanych funkcji zamiast lambdas, szczególnie w językach z pełną składnią lambda. O wiele łatwiej jest odczytać coś takiego evaluateTermniż długie wyrażenie lambda. Tylko dlatego, że można użyć lambda niekoniecznie znaczy, że powinien .
• Jeśli jedna z twoich nazwanych funkcji wygląda na coś, co pojawiałoby się dość często, istnieje prawdopodobieństwo, że jest już w standardowej bibliotece. Rozejrzeć się. Mój python jest trochę zardzewiały, ale wygląda na to, że w zasadzie wymyśliłeś enumeratelub zipWith.
• Często widzenie nazw funkcji i wyników pośrednich ułatwia rozumowanie o tym, co się dzieje i upraszcza, w którym to momencie sensowne może być ponowne umieszczenie lambdy lub połączenie niektórych linii.
• Jeśli imperatyw dla pętli wydaje się bardziej czytelny, istnieje szansa, że ​​zrozumienie zadziałałoby dobrze.