Powiedzmy, że mam poniższą logikę. Jak to napisać w programowaniu funkcjonalnym?
public int doSomeCalc(int[] array)
{
int answer = 0;
if(array!=null)
{
for(int e: array)
{
answer += e;
if(answer == 10) break;
if(answer == 150) answer += 100;
}
}
return answer;
}
Przykłady w większości blogów, artykułów ... Widzę, że wyjaśnia prosty przypadek jednej prostej funkcji matematycznej: „Suma”. Ale mam logikę podobną do powyższej napisaną w Javie i chciałbym migrować ją do funkcjonalnego kodu w Clojure. Jeśli nie możemy zrobić powyższego w FP, to rodzaj promocji dla FP nie stanowi tego wprost.
Wiem, że powyższy kod jest absolutnie konieczny. Nie napisano go z myślą o migracji do FP w przyszłości.
break
ireturn answer
można zastąpićreturn
wewnętrzną pętlą. W FP możesz wdrożyć ten wczesny powrót, używając kontynuacji, patrz np. En.wikipedia.org/wiki/ContinuationtakeWhile
.Odpowiedzi:
Najbliższym odpowiednikiem zapętlania tablicy w większości języków funkcjonalnych jest
fold
funkcja, tj. Funkcja, która wywołuje funkcję określoną przez użytkownika dla każdej wartości tablicy, przekazując zakumulowaną wartość wzdłuż łańcucha. W wielu językach funkcjonalnychfold
jest wzbogacony o szereg dodatkowych funkcji, które zapewniają dodatkowe funkcje, w tym opcję wcześniejszego zatrzymania, gdy wystąpi jakiś stan. W leniwych językach (np. Haskell) wczesne zatrzymanie można osiągnąć po prostu nie oceniając dalej listy, co spowoduje, że dodatkowe wartości nigdy nie będą generowane. Dlatego tłumacząc twój przykład na Haskell, napisałbym go jako:Podział tej linii po linii w przypadku, gdy nie znasz składni Haskella, działa to tak:
Definiuje typ funkcji, akceptując listę liczb całkowitych i zwracając pojedynczą liczbę całkowitą.
Główny korpus funkcji: podany argument
values
, returnfoldr1
wywołany z argumentamicombine
(które zdefiniujemy poniżej) ivalues
.foldr1
jest wariantem prymitywu składania, który zaczyna się od zestawu akumulatorów ustawionego na pierwszą wartość listy (stąd1
nazwa funkcji), a następnie łączy go za pomocą funkcji określonej przez użytkownika od lewej do prawej (co jest zwykle nazywane składaniem prawym , stądr
nazwa funkcji).foldr1 f [1,2,3]
Jest więc równoważnef 1 (f 2 3)
(lubf(1,f(2,3))
w bardziej konwencjonalnej składni podobnej do C).Definiowanie
combine
funkcji lokalnej: otrzymuje dwa argumentyv1
iv2
. Kiedyv1
jest 10, po prostu wracav1
. W tym przypadku v2 nigdy nie jest analizowane , więc pętla się tutaj zatrzymuje.Alternatywnie, gdy v1 wynosi 150, dodaje do niej dodatkowe 100 i dodaje v2.
A jeśli żaden z tych warunków nie jest spełniony, po prostu dodaje v1 do v2.
To rozwiązanie jest nieco specyficzne dla Haskella, ponieważ fakt, że prawy fold kończy się, jeśli funkcja łącząca nie ocenia drugiego argumentu, jest spowodowany leniwą strategią oceny Haskella. Nie znam Clojure, ale wierzę, że używa ścisłej oceny, więc spodziewałbym się, że będzie miał
fold
funkcję w swojej standardowej bibliotece, która zawiera specjalne wsparcie dla wcześniejszego zakończenia. To jest często nazywanyfoldWhile
,foldUntil
lub podobny.Szybkie spojrzenie na dokumentację biblioteki Clojure sugeruje, że w nazwach różni się nieco od większości funkcjonalnych języków i
fold
nie jest to to, czego szukasz (jest to bardziej zaawansowany mechanizm umożliwiający obliczenia równoległe), alereduce
jest bardziej bezpośredni odpowiednik. Wcześniejsze zakończenie ma miejsce, jeślireduced
funkcja zostanie wywołana w ramach funkcji łączenia. Nie jestem w 100% pewien, że rozumiem składnię, ale podejrzewam, że szukasz czegoś takiego:Uwaga: oba tłumaczenia, Haskell i Clojure, nie są odpowiednie dla tego konkretnego kodu; ale przekazują ogólną treść - patrz dyskusja w komentarzach poniżej, aby znaleźć konkretne problemy z tymi przykładami.
źródło
v1 v2
są mylące:v1
to „wartość z tablicy”, alev2
jest to skumulowany wynik. i twoje tłumaczenie jest błędne, sądzę, że pętla OP kończy się, gdy skumulowana (od lewej) wartość osiągnie 10, a nie jakiś element w tablicy. To samo z zwiększany przez 100. Jeśli na stosowanie fałdy tu użyć krotnie lewo z początku zjazdu, na jakąś odmianęfoldlWhile
tutaj .(= v1 150)
użycia wartości przedv2
(aka.e
) Jest do niego sumowany.Breaking this down line by line in case you're not familiar with Haskell's syntax
-- Jesteś moim bohaterem. Haskell jest dla mnie zagadką.Możesz łatwo przekonwertować go na rekurencję. I ma ładne rekurencyjne połączenie zoptymalizowane pod kątem ogona.
Pseudo kod :
źródło
GOTO
. (Nie tak źle, ale wciąż dość niezręcznie.) Odpowiednikiem pętli, jak mówi Jules, jest odpowiednie pasowanie.GOTO
. W każdym razie, kiedy kompilujesz rekursję ogona, sprowadza się ona głównie dowhile (true)
pętli z ciałem funkcji, w której wczesny powrót jest tylkobreak
instrukcją. Fold, chociaż masz rację, że jest to pętla, jest w rzeczywistości bardziej ograniczony niż ogólna konstrukcja pętli; jest bardziej jak pętla dla każdegoGOTO
to, że musisz robić kłopotliwe księgowanie, jakie argumenty w jakim stanie są przekazywane do wywołania rekurencyjnego, aby upewnić się, że faktycznie zachowuje się zgodnie z przeznaczeniem. Nie jest to konieczne w takim samym stopniu w porządnie napisanych pętlach imperatywnych (gdzie całkiem jasne są, jakie są zmienne stanowe i jak zmieniają się w każdej iteracji), ani w naiwnej rekurencji (gdzie zwykle niewiele się robi z argumentami, a zamiast tego wynik jest montowany w dość intuicyjny sposób). ...Bardzo podoba mi się odpowiedź Julesa , ale chciałem dodatkowo wskazać na coś, co ludzie często tęsknią za leniwym programowaniem funkcjonalnym, a mianowicie, że wszystko nie musi być „w pętli”. Na przykład:
Widać, że każdą część logiki można obliczyć w osobnej funkcji, a następnie złożyć razem. Pozwala to na zastosowanie mniejszych funkcji, które zwykle są znacznie łatwiejsze do rozwiązania. W twoim przykładzie zabawkowym może to bardziej komplikuje, niż usuwa, ale w prawdziwym kodzie funkcje rozdzielania są często znacznie prostsze niż całość.
źródło
stopAt10
jest nie dobra konsumentów. Twoja odpowiedź jest lepsza od tej, którą przytaczasz, ponieważ poprawnie izoluje podstawowego producentascanl (+) 0
wartości. ich użycie powinno jednak bezpośrednio uwzględniać logikę sterowania, lepiej jest je zaimplementować za pomocą tylko dwóchspan
s oraz alast
, wyraźnie. który byłby ściśle zgodny z oryginalną strukturą i logiką kodu i był łatwy w utrzymaniu.Większość przykładów przetwarzania lista pojawi się korzystać z funkcji takich jak
map
,filter
,sum
itd., Które działają na liście jako całości. Ale w twoim przypadku masz warunkowe wcześniejsze wyjście - raczej rzadki wzorzec, który nie jest obsługiwany przez zwykłe operacje na liście. Musisz więc opuścić poziom abstrakcji i użyć rekurencji - co jest również bliższe wyglądowi przykładu rozkazującego.To jest raczej bezpośrednie (prawdopodobnie nie idiomatyczne) tłumaczenie na Clojure:
Edit: Jules podkreślić, że
reduce
w Clojure zrobić wspierać wczesne wyjście. Korzystanie z tego jest bardziej eleganckie:W każdym razie możesz robić wszystko w językach funkcjonalnych, jak w językach imperatywnych, ale często musisz nieco zmienić sposób myślenia, aby znaleźć eleganckie rozwiązanie. W kodowaniu imperatywnym myślisz o przetwarzaniu listy krok po kroku, podczas gdy w językach funkcjonalnych szukasz operacji, która zostanie zastosowana do wszystkich elementów na liście.
źródło
reduce
operacja Clojure obsługuje wczesne wyjście.takeWhile
nie jest to „powszechna operacja”?takeWhile
jest to częsta operacja, nie jest szczególnie przydatna w tym przypadku, ponieważ potrzebujesz wyników transformacji, zanim zdecydujesz, czy przerwać. W leniwym języku nie ma to znaczenia: możesz użyćscan
itakeWhile
na wynikach skanowania (patrz odpowiedź Karla Bielefeldta, który choć nie jest używany,takeWhile
można go łatwo przepisać), ale dla ścisłego języka, takiego jak clojure, byłoby to oznacza przetworzenie całej listy, a następnie odrzucenie wyników. Funkcje generatora mogą jednak rozwiązać ten problem i wierzę, że clojure je obsługuje.take-while
in Clojure tworzy leniwą sekwencję (zgodnie z dokumentacją). Innym sposobem rozwiązania tego problemu są przetworniki (być może najlepsze).Jak wskazano w innych odpowiedziach, Clojure ma
reduced
za zadanie wczesne powstrzymanie redukcji:To najlepsze rozwiązanie dla Twojej konkretnej sytuacji. Można również uzyskać dużo przebieg z łączenia
reduced
ztransduce
, co pozwala na korzystanie z przetwornikówmap
,filter
itd. Jednak jest to dalekie od pełnej odpowiedzi na swoje ogólne pytanie.Kontynuacje specjalne to uogólniona wersja instrukcji break i return. Są one bezpośrednio implementowane w niektórych schematach (
call-with-escape-continuation
), Common Lisp (block
+return
,catch
+throw
), a nawet w C (setjmp
+longjmp
). Bardziej ogólne, ograniczone lub nielimitowane kontynuacje, jak można znaleźć w standardowym schemacie lub jako monady kontynuacyjne w Haskell i Scali, mogą być również użyte jako kontynuacje ucieczki.Na przykład w Racket możesz użyć
let/ec
takiego:Wiele innych języków ma również konstrukcje przypominające kontynuację ucieczki w postaci obsługi wyjątków. W Haskell możesz również użyć jednej z różnych monad błędów
foldM
. Ponieważ są to przede wszystkim konstrukcje obsługujące błędy wykorzystujące wyjątki lub monady błędów dla wczesnych zwrotów, jest to zwykle niedopuszczalne kulturowo i być może dość powolne.Możesz także przejść z funkcji wyższego rzędu do wywołań typu tail tail.
Podczas korzystania z pętli kolejna iteracja jest wprowadzana automatycznie po osiągnięciu końca korpusu pętli. Możesz przejść do następnej iteracji wcześniej
continue
lub wyjść z pętli za pomocąbreak
(lubreturn
). Podczas korzystania z wywołań ogona (lubloop
konstrukcji Clojure, która naśladuje rekurencję ogona), zawsze musisz wykonać wyraźne wywołanie, aby przejść do następnej iteracji. Aby zatrzymać zapętlenie, po prostu nie wykonuj wywołania rekurencyjnego, ale bezpośrednio podaj wartość:źródło
MonadError
, w zasadzie odpowiednikEither
nie ma takiego nastawienia tylko do obsługi błędów, więc można go łatwo użyć jako zamiennika.Skomplikowaną częścią jest pętla. Zacznijmy od tego. Pętla jest zwykle konwertowana na styl funkcjonalny poprzez wyrażenie iteracji za pomocą jednej funkcji. Iteracja to transformacja zmiennej pętli.
Oto funkcjonalna implementacja ogólnej pętli:
Trwa (wartość początkowa zmiennej pętli, funkcja wyrażająca pojedynczą iterację [w zmiennej pętli]) (warunek kontynuacji pętli).
W twoim przykładzie użyto pętli na tablicy, która również się psuje. Ta umiejętność w języku imperatywnym jest upieczona w samym języku. W programowaniu funkcjonalnym taka zdolność jest zwykle implementowana na poziomie biblioteki. Oto możliwe wdrożenie
W tym :
Używam pary ((val, next_pos)), która zawiera zmienną pętli widoczną na zewnątrz i pozycję w tablicy, którą ta funkcja ukrywa.
Funkcja iteracji jest nieco bardziej złożona niż w ogólnej pętli, ta wersja umożliwia użycie bieżącego elementu tablicy. [Jest w formie curry ]
Takie funkcje są zwykle nazywane „fold”.
W nazwie wstawiam „l”, aby wskazać, że akumulacja elementów tablicy odbywa się w lewostronny sposób; naśladować nawyk imperatywnych języków programowania do iteracji tablicy od niskiego do wysokiego indeksu.
Umieszczam „c” w nazwie, aby wskazać, że ta wersja fold przyjmuje warunek kontrolujący, czy i kiedy pętla ma zostać zatrzymana wcześniej.
Oczywiście takie funkcje narzędziowe będą prawdopodobnie łatwo dostępne w bibliotece podstawowej dostarczanej z użytym funkcjonalnym językiem programowania. Napisałem je tutaj dla celów demonstracyjnych.
Teraz, gdy mamy wszystkie narzędzia, które są w języku w bezwzględnie koniecznym przypadku, możemy zwrócić się o wdrożenie konkretnej funkcjonalności twojego przykładu.
Zmienna w Twojej pętli to para („odpowiedź”, boolean, który koduje, czy kontynuować).
Zauważ, że użyłem nowej „zmiennej” „new_answer”. Wynika to z faktu, że w programowaniu funkcjonalnym nie mogę zmienić wartości już zainicjowanej „zmiennej”. Nie martwię się o wydajność, kompilator może ponownie wykorzystać pamięć „odpowiedz” dla „new_answer” poprzez analizę czasu życia, jeśli uzna, że jest to bardziej wydajne.
Włączenie tego do naszej wcześniej opracowanej funkcji pętli:
„Array” tutaj jest nazwą modułu, którym jest funkcja eksportu foldlc.
„pięść”, „drugi” oznaczają funkcje, które zwracają pierwszy, drugi składnik parametru pary
W tym przypadku styl „bez punktów” zwiększa czytelność implementacji doSomeCalc:
(>>>) to skład funkcji:
(>>>) : (a -> b) -> (b -> c) -> (a -> c)
Jest tak samo jak powyżej, tylko parametr „arr” jest pomijany po obu stronach równania definiującego.
I ostatnia rzecz: sprawdzanie wielkości liter (tablica == null). W lepiej zaprojektowanych językach programowania, ale nawet w źle zaprojektowanych językach z pewną podstawową dyscypliną raczej używa się opcjonalnego typu do wyrażenia nieistnienia. Nie ma to wiele wspólnego z programowaniem funkcjonalnym, o które ostatecznie chodzi, więc nie radzę sobie z tym.
źródło
Najpierw przepisz nieco pętlę, tak aby każda iteracja pętli albo wcześniej kończyła działanie, albo mutowała
answer
dokładnie raz:Powinno być jasne, że zachowanie tej wersji jest dokładnie takie samo jak poprzednio, ale teraz znacznie łatwiej jest przekonwertować na styl rekurencyjny. Oto bezpośrednie tłumaczenie Haskell:
Teraz jest on czysto funkcjonalny, ale możemy go ulepszyć zarówno z punktu widzenia wydajności, jak i czytelności, używając fold zamiast wyraźnej rekurencji:
W tym kontekście
Left
wcześnie wychodzi ze swojej wartości iRight
kontynuuje rekurencję ze swoją wartością.Można to teraz nieco uprościć:
Jest to lepsze niż końcowy kod Haskell, ale teraz jest nieco mniej jasne, jak odwzorowuje z powrotem na oryginalną Javę.
źródło