Каковы функциональные эквиваленты операторов обязательного разрыва и других проверок цикла?

Допустим, у меня есть логика ниже. Как написать это в функциональном программировании?

    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;
    }

Примеры в большинстве блогов, статей ... Я вижу, просто объясняет простой случай одной прямой математической функции, скажем, "Сумма". Но у меня есть логика, аналогичная вышеописанной на Java, и я хотел бы перенести ее в функциональный код в Clojure. Если мы не можем сделать это в FP, то в промо-акциях для FP это прямо не указано.

Я знаю, что приведенный выше кодекс абсолютно необходим. Он не был написан с мыслью о переносе его в FP в будущем.

Ближайшим эквивалентом зацикливания массива в большинстве функциональных языков является foldфункция, то есть функция, которая вызывает пользовательскую функцию для каждого значения массива, передавая накопленное значение по цепочке. Во многих функциональных языках foldдополнен множеством дополнительных функций, которые предоставляют дополнительные функции, в том числе возможность досрочной остановки при возникновении некоторых условий. В ленивых языках (например, Haskell) досрочная остановка может быть достигнута просто без дальнейшей оценки по списку, что приведет к тому, что дополнительные значения никогда не будут генерироваться. Поэтому, переводя ваш пример на Haskell, я бы написал так:

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

Разбивая это построчно, если вы не знакомы с синтаксисом Haskell, это работает так:

doSomeCalc :: [Int] -> Int

Определяет тип функции, принимает список целых и возвращает одно целое.

doSomeCalc values = foldr1 combine values

Основная часть функции: заданный аргумент values, return foldr1с аргументами combine(которые мы определим ниже) и values. foldr1является вариантом примитива сгиба, который начинается с того, что аккумулятор установлен на первое значение списка (отсюда и 1в имени функции), а затем объединяет его, используя функцию, заданную пользователем слева направо (которая обычно называется правым сгибом , следовательно rв названии функции). Так foldr1 f [1,2,3]эквивалентно f 1 (f 2 3)(или f(1,f(2,3))в более обычном C-подобном синтаксисе).

  where combine v1 v2 | v1 == 10  = v1

Определение combineлокальной функции: она получает два аргумента v1и v2. Когда v110, он просто возвращается v1. В этом случае v2 никогда не оценивается , поэтому цикл останавливается здесь.

                      | v1 == 150 = v1 + 100 + v2

Кроме того, когда v1 равен 150, добавляет к нему дополнительные 100 и добавляет v2.

                      | otherwise = v1 + v2

И, если ни одно из этих условий не выполняется, просто добавляет v1 к v2.

Теперь, это решение несколько специфично для Haskell, потому что тот факт, что правильное сгибание заканчивается, если функция объединения не оценивает свой второй аргумент, вызвано ленивой стратегией оценки Haskell. Я не знаю Clojure, но я полагаю, что он использует строгую оценку, поэтому я ожидаю, что foldв его стандартной библиотеке будет функция, включающая специальную поддержку для досрочного завершения. Это часто называют foldWhile, foldUntilили аналогичный.

Беглый взгляд на документацию библиотеки Clojure показывает, что она немного отличается от большинства функциональных языков в именовании, и это foldне то, что вам нужно (это более продвинутый механизм, предназначенный для обеспечения параллельных вычислений), но reduceоно более прямое. эквивалент. Досрочное прекращение происходит, если reducedфункция вызывается в вашей функции объединения. Я не уверен на 100%, что понимаю синтаксис, но подозреваю, что вы ищете что-то вроде этого:

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

NB: оба перевода, Haskell и Clojure, не совсем подходят для этого конкретного кода; но они передают общую суть этого - см. обсуждение в комментариях ниже для конкретных проблем с этими примерами.

Вы можете легко преобразовать это в рекурсию. И у него есть хороший рекурсивный вызов с оптимизированным хвостом.

Псевдокод:

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);
}

Мне очень нравится ответ Жюля , но я хотел бы дополнительно отметить кое-что, что люди часто упускают из-за ленивого функционального программирования, а именно, что все не должно быть «внутри цикла». Например:

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

Вы можете видеть, что каждая часть вашей логики может быть вычислена в отдельной функции, а затем составлена ​​вместе. Это учитывает меньшие функции, которые обычно намного легче устранить неисправности. Для вашего игрушечного примера, возможно, это добавляет больше сложности, чем удаляет, но в коде реального мира разделенные функции часто намного проще, чем целое.

Большинство примеров обработки списка вы будете видеть функции использования , как map, filter,sum т. Д., Которые работают со списком в целом. Но в вашем случае у вас есть условный досрочный выход - довольно необычный шаблон, который не поддерживается обычными операциями со списком. Таким образом, вам нужно сбросить уровень абстракции и использовать рекурсию, что также ближе к тому, как выглядит императивный пример.

Это довольно прямой (вероятно, не идиоматический) перевод на 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: Жюль отмечают, что reduceв Clojure сделать поддержку раннего выхода. Используя это более элегантно:

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

В любом случае вы можете делать что-либо на функциональных языках, как на императивных языках, но вам часто приходится несколько менять свое мышление, чтобы найти элегантное решение. В императивном кодировании вы думаете об обработке списка шаг за шагом, в то время как в функциональных языках вы ищете операцию, которую можно применить ко всем элементам в списке.

Как указано в других ответах, Clojure предлагает reducedпрекратить сокращение на ранних этапах:

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

Это лучшее решение для вашей конкретной ситуации. Вы также можете получить много пробег от объединения reducedс transduce, что позволяет использовать датчики с map, и filterт.д. Однако это далеко не полный ответ на ваш общий вопрос.

Продолжения Escape являются обобщенной версией операторов break и return. Они напрямую реализованы в некоторых Schemes ( call-with-escape-continuation), Common Lisp ( block+ return, catch+ throw) и даже C ( setjmp+ longjmp). Более общие или неограниченные продолжения, определенные в стандартной Схеме или в виде монад продолжения в Хаскеле и Скале, также могут использоваться в качестве продолжения эвакуации.

Например, в Racket вы можете использовать let/ecтак:

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

Многие другие языки также имеют экранирующие продолжения конструкции в форме обработки исключений. В Haskell вы также можете использовать одну из различных монад ошибок с foldM. Поскольку они в первую очередь являются конструкциями обработки ошибок, использующими исключения или монады ошибок для раннего возврата, обычно культурно неприемлемы и, возможно, довольно медленны.

Вы также можете перейти от функций высшего порядка к хвостовым вызовам.

При использовании циклов вы автоматически вводите следующую итерацию, когда достигаете конца тела цикла. Вы можете ввести следующую итерацию как можно раньше continueили выйти из цикла с помощью break(или return). При использовании хвостовых вызовов (или loopконструкции Clojure, которая имитирует хвостовую рекурсию), вы всегда должны делать явный вызов для входа в следующую итерацию. Чтобы прекратить зацикливание, вы просто не делаете рекурсивный вызов, а передаете значение напрямую:

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

Запутанная часть - петля. Давайте начнем с этого. Цикл обычно преобразуется в функциональный стиль, выражая итерацию одной функцией. Итерация - это преобразование переменной цикла.

Вот функциональная реализация общего цикла:

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

Он принимает (начальное значение переменной цикла, функция, которая выражает одну итерацию [в переменной цикла]) (условие для продолжения цикла).

Ваш пример использует цикл в массиве, который также разрывается. Эта возможность на вашем императивном языке встроена в сам язык. В функциональном программировании такая возможность обычно реализуется на уровне библиотеки. Вот возможная реализация

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

В этом :

Я использую пару ((val, next_pos)), которая содержит видимую снаружи переменную цикла и позицию в массиве, которую скрывает эта функция.

Функция итерации немного сложнее, чем в общем цикле, эта версия позволяет использовать текущий элемент массива. [Это в карри .]

Такие функции обычно называют «сложить».

Я вставил «l» в названии, чтобы указать, что накопление элементов массива осуществляется левоассоциативным образом; имитировать привычку императивных языков программирования перебирать массив от низкого до высокого индекса.

Я вставил «c» в названии, чтобы указать, что эта версия сгиба принимает условие, которое контролирует, когда и когда цикл должен быть остановлен досрочно.

Конечно, такие вспомогательные функции, вероятно, будут легко доступны в базовой библиотеке, поставляемой с используемым функциональным языком программирования. Я написал их здесь для демонстрации.

Теперь, когда у нас есть все инструменты, которые есть в языке в императивном случае, мы можем обратиться к реализации конкретной функциональности вашего примера.

Переменная в вашем цикле - это пара ('answer', логическое значение, которое кодирует, продолжать ли).

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)

Обратите внимание, что я использовал новую переменную new_answer. Это связано с тем, что в функциональном программировании я не могу изменить значение уже инициализированной «переменной». Я не беспокоюсь о производительности, компилятор может повторно использовать память 'answer' для 'new_answer' с помощью анализа времени жизни, если он считает, что это более эффективно.

Включение этого в нашу функцию цикла, разработанную ранее:

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

«Массив» - это имя модуля, в котором экспортируется функция foldlc.

«кулак», «второй» означают функции, которые возвращают первый, второй компонент своего параметра пары

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

В этом случае стиль «без точек» повышает удобочитаемость реализации doSomeCalc:

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

(>>>) - это композиция функций: (>>>) : (a -> b) -> (b -> c) -> (a -> c)

Это то же самое, что и выше, только параметр "arr" не учитывается с обеих сторон определяющего уравнения.

И последнее: проверка регистра (массив == ноль). В лучше разработанных языках программирования, но даже в плохо разработанных языках с некоторой базовой дисциплиной, один использует дополнительный тип для выражения несуществования. Это не имеет ничего общего с функциональным программированием, о котором в конечном итоге и идет речь, поэтому я не занимаюсь этим.

Во-первых, немного переписать цикл так, чтобы каждая итерация цикла либо рано выходила, либо изменялась answerровно один раз:

    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;
    }

Должно быть ясно, что поведение этой версии точно такое же, как и раньше, но теперь гораздо проще перейти к рекурсивному стилю. Вот прямой перевод на 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

Теперь он чисто функциональный, но мы можем улучшить его как с точки зрения эффективности, так и читабельности, используя сгиб вместо явной рекурсии:

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)

В этом контексте Leftранний выход с его значением и Rightпродолжение рекурсии с его значением.

Теперь это можно упростить немного больше, например так:

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

Это лучше, чем финальный код на Haskell, но теперь немного менее понятно, как он отображается на исходную Java.