Jakie są funkcjonalne odpowiedniki imperatywnych instrukcji break i innych kontroli pętli?

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.

Najbliższym odpowiednikiem zapętlania tablicy w większości języków funkcjonalnych jest foldfunkcja, 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 funkcjonalnych foldjest 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:

doSomeCalc :: [Int] -> Int
doSomeCalc values = foldr1 combine values
  where combine v1 v2 | v1 == 10  = v1
                      | v1 == 150 = v1 + 100 + v2
                      | otherwise = v1 + v2

Podział tej linii po linii w przypadku, gdy nie znasz składni Haskella, działa to tak:

doSomeCalc :: [Int] -> Int

Definiuje typ funkcji, akceptując listę liczb całkowitych i zwracając pojedynczą liczbę całkowitą.

doSomeCalc values = foldr1 combine values

Główny korpus funkcji: podany argument values, return foldr1wywołany z argumentami combine(które zdefiniujemy poniżej) i values. foldr1jest wariantem prymitywu składania, który zaczyna się od zestawu akumulatorów ustawionego na pierwszą wartość listy (stąd 1nazwa 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ąd rnazwa funkcji). foldr1 f [1,2,3]Jest więc równoważne f 1 (f 2 3)(lub f(1,f(2,3))w bardziej konwencjonalnej składni podobnej do C).

  where combine v1 v2 | v1 == 10  = v1

Definiowanie combinefunkcji lokalnej: otrzymuje dwa argumenty v1i v2. Kiedy v1jest 10, po prostu wraca v1. W tym przypadku v2 nigdy nie jest analizowane , więc pętla się tutaj zatrzymuje.

                      | v1 == 150 = v1 + 100 + v2

Alternatywnie, gdy v1 wynosi 150, dodaje do niej dodatkowe 100 i dodaje v2.

                      | otherwise = v1 + 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ł foldfunkcję w swojej standardowej bibliotece, która zawiera specjalne wsparcie dla wcześniejszego zakończenia. To jest często nazywany foldWhile, foldUntillub podobny.

Szybkie spojrzenie na dokumentację biblioteki Clojure sugeruje, że w nazwach różni się nieco od większości funkcjonalnych języków i foldnie jest to to, czego szukasz (jest to bardziej zaawansowany mechanizm umożliwiający obliczenia równoległe), ale reducejest bardziej bezpośredni odpowiednik. Wcześniejsze zakończenie ma miejsce, jeśli reducedfunkcja zostanie wywołana w ramach funkcji łączenia. Nie jestem w 100% pewien, że rozumiem składnię, ale podejrzewam, że szukasz czegoś takiego:

(reduce 
    (fn [v1 v2]
        (if (= v1 10) 
             (reduced v1)
             (+ v1 v2 (if (= v1 150) 100 0))))
    array)

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.

Możesz łatwo przekonwertować go na rekurencję. I ma ładne rekurencyjne połączenie zoptymalizowane pod kątem ogona.

Pseudo kod :

public int doSomeCalc(int[] array)
{
    return doSomeCalcInner(array, 0);
}

public int doSomeCalcInner(int[] array, int answer)
{
    if (array is empty) return answer;

    // not sure how to efficiently implement head/tails array split in clojure
    var head = array[0] // first element of array
    var tail = array[1..] // remainder of array

    answer += head;
    if (answer == 10) return answer;
    if (answer == 150) answer += 100;

    return doSomeCalcInner(tail, answer);
}

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:

baseSums = scanl (+) 0

offsets = scanl (\offset sum -> if sum == 150 then offset + 100 else offset) 0

zipWithOffsets xs = zipWith (+) xs (offsets xs)

stopAt10 xs = if 10 `elem` xs then 10 else last xs

result = stopAt10 . zipWithOffsets . baseSums

result [1..]         -- 10
result [11..1000000] -- 500000499945

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

Większość przykładów przetwarzania lista pojawi się korzystać z funkcji takich jak map, filter, sumitd., 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:

(defn doSomeCalc 
  ([lst] (doSomeCalc lst 0))
  ([lst sum]
    (if (empty? lst) sum
        (if (= sum 10) sum
            (let [sum (+ sum (first lst))]
                 [sum (if (= sum 150) (+ sum 100) sum)]
               (recur (rest lst) sum))))))) 

Edit: Jules podkreślić, że reducew Clojure zrobić wspierać wczesne wyjście. Korzystanie z tego jest bardziej eleganckie:

(defn doSomeCalc [lst]  
  (reduce (fn [sum val]
    (if (= sum 10) (reduced sum)
        (let [sum (+ sum val)]
             [sum (if (= sum 150) (+ sum 100) sum)]
           sum))
   lst)))

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.

Jak wskazano w innych odpowiedziach, Clojure ma reducedza zadanie wczesne powstrzymanie redukcji:

(defn some-calc [coll]
  (reduce (fn [answer e]
            (let [answer (+ answer e)]
               (case answer
                 10  (reduced answer)
                 150 (+ answer 100)
                 answer)))
          0 coll))

To najlepsze rozwiązanie dla Twojej konkretnej sytuacji. Można również uzyskać dużo przebieg z łączenia reducedz transduce, co pozwala na korzystanie z przetworników map, filteritd. 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/ectakiego:

(define (some-calc ls)
  (let/ec break ; let break be an escape continuation
    (foldl (lambda (answer e)
             (let ([answer (+ answer e)])
               (case answer
                 [(10)  (break answer)] ; return answer immediately
                 [(150) (+ answer 100)]
                 [else  answer])))
           0 ls)))

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 continuelub wyjść z pętli za pomocą break(lub return). Podczas korzystania z wywołań ogona (lub loopkonstrukcji 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ść:

(defn some-calc [coll]
  (loop [answer 0, [e es :as coll] coll]
    (if (empty? coll)
      answer
      (let [answer (+ answer e)]
        (case answer
          10 answer
          150 (recur (+ answer 100) es)
          (recur answer es))))))

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:

loop : v -> (v -> v) -> (v -> Bool) -> v
loop init iter cond_to_cont = 
    if cond_to_cont init 
        then loop (iter init) iter cond
        else init

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

module Array (foldlc) where

foldlc : v -> (v -> e -> v) -> (v -> Bool) -> Array e -> v
foldlc init iter cond_to_cont arr = 
    loop 
        (init, 0)
        (λ (val, next_pos) -> (iter val (at next_pos arr), next_pos + 1))
        (λ (val, next_pos) -> and (cond_to_cont val) (next_pos < size arr))

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

iter : (Int, Bool) -> Int -> (Int, Bool)
iter (answer, cont) collection_element = 
  let new_answer = answer + collection_element
  in case new_answer of
    10 -> (new_answer, false)
    150 -> (new_answer + 100, true)
    _ -> (new_answer, true)

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:

doSomeCalc :: Array Int -> Int
doSomeCalc arr = fst (Array.foldlc (0, true) iter snd arr)

„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

fst : (x, y) -> x
snd : (x, y) -> y

W tym przypadku styl „bez punktów” zwiększa czytelność implementacji doSomeCalc:

doSomeCalc = Array.foldlc (0, true) iter snd >>> fst

(>>>) 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.

Najpierw przepisz nieco pętlę, tak aby każda iteracja pętli albo wcześniej kończyła działanie, albo mutowała answerdokładnie raz:

    public int doSomeCalc(int[] array)
    {
        int answer = 0;
        if(array!=null)
        {
            for(int e: array)
            {
                if(answer + e == 10) return answer + e;
                else if(answer + e == 150) answer = answer + e + 100;
                else answer = answer + e;
            }
        }
        return answer;
    }

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:

doSomeCalc :: [Int] -> Int
doSomeCalc = recurse 0
  where recurse :: Int -> [Int] -> Int
        recurse answer [] = answer
        recurse answer (e:array)
          | answer + e == 10 = answer + e
          | answer + e == 150 = recurse (answer + e + 100) array
          | otherwise = recurse (answer + e) array

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:

import Control.Monad (foldM)

doSomeCalc :: [Int] -> Int
doSomeCalc = either id id . foldM go 0
  where go :: Int -> Int -> Either Int Int
        go answer e
          | answer + e == 10 = Left (answer + e)
          | answer + e == 150 = Right (answer + e + 100)
          | otherwise = Right (answer + e)

W tym kontekście Leftwcześnie wychodzi ze swojej wartości i Rightkontynuuje rekurencję ze swoją wartością.

Można to teraz nieco uprościć:

import Control.Monad (foldM)

doSomeCalc :: [Int] -> Int
doSomeCalc = either id id . foldM go 0
  where go :: Int -> Int -> Either Int Int
        go answer e
          | answer' == 10 = Left 10
          | answer' == 150 = Right 250
          | otherwise = Right answer'
          where answer' = answer + e

Jest to lepsze niż końcowy kod Haskell, ale teraz jest nieco mniej jasne, jak odwzorowuje z powrotem na oryginalną Javę.