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.
źródło
for
na 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.lambda
, w porównaniu do języków z lżejszą anonimową funkcją składni. Część tego prawdopodobnie przyczynia się do „nieczystego” wyglądu.Odpowiedzi:
Metoda Hornera jest prawdopodobnie bardziej wydajna obliczeniowo, jak wskazuje @delnan, ale nazwałbym to dość czytelnym w Pythonie dla rozwiązania potęgującego:
źródło
sum(coeff * X**power for power, coeff in enumerate(poly))
map
ifilter
. 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.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 #:
źródło
map
działa, napisanie własnego powinno być dość proste.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):
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:
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.
zipWith
jest 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ć.źródło
Jeśli tylko masz (stałe) krotki, dlaczego nie jest to (w Haskell) zrobić:
Jeśli zamiast tego masz listę współczynników, możesz użyć:
lub z obniżką taką, jaką miałeś:
źródło
tuple
na 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.Istnieje ogólny zestaw kroków, których można użyć, aby poprawić czytelność algorytmów funkcjonalnych:
evaluateTerm
niż długie wyrażenie lambda. Tylko dlatego, że można użyć lambda niekoniecznie znaczy, że powinien .enumerate
lubzipWith
.źródło