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

10

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.

użytkownik1358
źródło
7
Z mojego doświadczenia wynika, że ​​czysto funkcjonalny kod w tym sensie, że nie używa zmiennych zmiennych (co forna przykład oznacza również nieużywanie pętli) jest złym celem w Pythonie. Ponowne wiązanie zmiennych rozsądnie i brak mutowania obiektów daje prawie wszystkie korzyści i sprawia, że ​​kod jest nieskończenie bardziej czytelny. Ponieważ obiekty liczbowe są niezmienne i odsyła tylko dwie nazwy lokalne, twoje „imperatywne” rozwiązanie lepiej realizuje funkcjonalne zalety programowania niż jakikolwiek „ściśle czysty” kod Pythona.
2
BTW Metoda mnożenia jest metodą Hornera i na każdym etapie jest bardziej wydajna niż potęgowanie, ponieważ potęgowanie wymaga tych samych zwielokrotnień, a następnie kilku innych.
1
Python jest nieco brzydki, kiedy się go używa lambda, w porównaniu do języków z lżejszą anonimową funkcją składni. Część tego prawdopodobnie przyczynia się do „nieczystego” wyglądu.
KChaloux,
@KChalhal właśnie to chciałem powiedzieć. Wsparcie programowania funkcjonalnego jest w Pythonie pod pewnymi względami i jest swego rodzaju pokazem. Mimo to nie sądzę, aby nawet pierwsza wersja była tak okropnie nieczytelna, że ​​nie można zrozumieć, co się dzieje.
Evicatos,
Jestem naprawdę zdezorientowany twoim kodem, podczas gdy zakres problemu ma równanie matematyczne, które jest wyjątkowo jasne, dlaczego po prostu nie użyjesz tego równania matematycznego dosłownie? Dość łatwo przekształca się w funkcję w dowolnym języku ... nie jestem pewien, co chcesz zmapować, zredukować lub iterować, gdy pytanie dotyczy funkcji, która ocenia pojedyncze równanie i daje to równanie - nie prosi o iteracja w ogóle ...
Jimmy Hoffa,

Odpowiedzi:

13

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)] )
aelfric5578
źródło
17
Upuść nawiasy kwadratowe i nadaj zmiennym bardziej opisowe nazwy, a nawet lepiej: sum(coeff * X**power for power, coeff in enumerate(poly))
Izkata,
1
Trochę mnie to zasmuca, że ​​inne opublikowane odpowiedzi są tak złożone. Użyj języka na swoją korzyść!
Izkata,
rozumienie jest jak „przemycona” pętla for do programowania funkcjonalnego
user1358
7
@ user1358 Nie, to cukier składniowy do składu mapi filter. Można również myśleć o tym jak o pętli for określonego kształtu, ale pętle tego kształtu są równoważne z wyżej wspomnianym kombinatorem funkcjonalnym.
7

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
Steven Evers
źródło
2
A nawet jeśli nie, o ile rozumiesz, jak to mapdziała, napisanie własnego powinno być dość proste.
KChaloux,
4

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

Jimmy Hoffa
źródło
4

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..]
Paweł
źródło
1
To nie jest praca domowa! Nie wspominając już o tym, że zrobiłem już 3 rozwiązania.
user1358,
Połowa czasu w Pythonie (w tym w tym przypadku) „krotka” oznacza „niezmienną listę” i dlatego ma dowolną długość.
oczywiście dowolna długość
użytkownik1358,
1
nie z powodu pytona, ale ponieważ wielomian implikuje dowolną długość, a ustalony rozmiar nie byłby dużym ćwiczeniem
użytkownik1358,
1
@delnan To ciekawe. Zawsze uważałem, że ma tuplena myśli zestaw wartości o stałym rozmiarze, każdy z potencjalnie różnych typów, których nie można dodawać ani usuwać. Nigdy tak naprawdę nie rozumiałem, dlaczego dynamiczny język z listami, które akceptują różnorodne dane wejściowe, będzie im potrzebny.
KChaloux,
3

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.
Karl Bielefeldt
źródło