Quais são os equivalentes funcionais de instruções de interrupção imperativas e outras verificações de loop?

36

Digamos, eu tenho a lógica abaixo. Como escrever isso em Programação Funcional?

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

Os exemplos na maioria dos blogs, artigos ... Vejo apenas explica o caso simples de uma função matemática direta, como 'Sum'. Mas, eu tenho uma lógica semelhante à descrita acima em Java e gostaria de migrar para código funcional no Clojure. Se não podemos fazer o acima no FP, então o tipo de promoções para o FP não declara isso explicitamente.

Eu sei que o código acima é totalmente imperativo. Não foi escrito com a premissa de migrá-lo para o FP no futuro.

Vicky
fonte
1
Observe que a combinação de breake return answerpode ser substituída por uma parte returninterna do loop. No FP, você pode implementar esse retorno antecipado usando continuações, por exemplo, en.wikipedia.org/wiki/Continuation
Giorgio
1
@Giorgio continuações seria um enorme exagero aqui. De qualquer forma, é um loop. Para chamar sua próxima iteração, você faz uma chamada final, para interromper você simplesmente não liga mais e apenas retorna a resposta. Para loops aninhados ou outro fluxo de controle complicado, é aí que você pode usar continuações em vez de pesar para reestruturar seu código para usar a técnica simples acima (que sempre deve ser possível, mas pode levar a uma estrutura de código excessivamente complexa que explicaria mais ou menos a continuação e, para mais de um ponto de saída, você certamente precisará deles).
Will Ness
8
Neste caso: takeWhile.
Jonathan fundido
1
@ WillNess: Eu só queria mencionar isso, porque ele pode ser usado para deixar uma computação complexa a qualquer momento. Provavelmente não é a melhor solução para o exemplo concreto do OP.
Giorgio
@Giorgio você está certo, é o mais abrangente, em geral. na verdade, essa pergunta é muito ampla, IYKWIM (ou seja, seria fechada no SO em um piscar de olhos).
Will Ness

Respostas:

45

O equivalente mais próximo de loop sobre uma matriz na maioria das linguagens funcionais é uma foldfunção, ou seja, uma função que chama uma função especificada pelo usuário para cada valor da matriz, passando um valor acumulado ao longo da cadeia. Em muitas linguagens funcionais, foldé aumentada por uma variedade de funções adicionais que fornecem recursos extras, incluindo a opção de parar cedo quando surgir alguma condição. Em idiomas preguiçosos (por exemplo, Haskell), a parada antecipada pode ser alcançada simplesmente não avaliando mais a lista, o que fará com que valores adicionais nunca sejam gerados. Portanto, traduzindo seu exemplo para Haskell, eu o escreveria como:

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

Quebrando essa linha por linha, caso você não esteja familiarizado com a sintaxe de Haskell, isso funciona assim:

doSomeCalc :: [Int] -> Int

Define o tipo da função, aceitando uma lista de entradas e retornando um único int.

doSomeCalc values = foldr1 combine values

O corpo principal da função: dado argumento values, retorne foldr1chamado com argumentos combine(que definiremos abaixo) e values. foldr1é uma variante da primitiva da dobra que começa com o acumulador definido como o primeiro valor da lista (daí o 1nome da função) e a combina usando a função especificada pelo usuário da esquerda para a direita (que geralmente é chamada de dobra à direita , daí o rnome da função). Portanto, foldr1 f [1,2,3]é equivalente a f 1 (f 2 3)(ou f(1,f(2,3))na sintaxe mais convencional do tipo C).

  where combine v1 v2 | v1 == 10  = v1

Definindo a combinefunção local: recebe dois argumentos, v1e v2. Quando v1é 10, apenas retorna v1. Nesse caso, a v2 nunca é avaliada , portanto, o loop para aqui.

                      | v1 == 150 = v1 + 100 + v2

Como alternativa, quando v1 é 150, adiciona 100 extras a ele e v2.

                      | otherwise = v1 + v2

E, se nenhuma dessas condições for verdadeira, basta adicionar v1 a v2.

Agora, essa solução é um pouco específica para Haskell, porque o fato de uma dobra à direita terminar se a função de combinação não avaliar seu segundo argumento é causada pela estratégia de avaliação lenta de Haskell. Não conheço o Clojure, mas acredito que ele usa avaliação rigorosa, portanto, espero que ele tenha uma foldfunção em sua biblioteca padrão que inclua suporte específico para o término antecipado. Isso é muitas vezes chamado foldWhile, foldUntilou similar.

Uma rápida olhada na documentação da biblioteca Clojure sugere que ela é um pouco diferente da maioria das linguagens funcionais na nomeação, e foldnão é isso que você está procurando (é um mecanismo mais avançado destinado a permitir a computação paralela), mas reduceé o mais direto equivalente. A rescisão antecipada ocorre se a reducedfunção for chamada dentro da sua função combinada. Não tenho 100% de certeza de entender a sintaxe, mas suspeito que o que você está procurando é algo como isto:

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

Nota: ambas as traduções, Haskell e Clojure, não estão certas para esse código específico; mas eles transmitem a essência geral - veja a discussão nos comentários abaixo para problemas específicos com esses exemplos.

Jules
fonte
11
os nomes v1 v2são confusos: v1é um "valor da matriz", mas v2é o resultado acumulado. e sua tradução é errônea, creio eu, sai do loop do OP quando o acumulado (da esquerda) valor atinge 10, não algum elemento na matriz. O mesmo ocorre com o incremento de 100. Se usar dobras aqui, use a dobra esquerda com saída antecipada, alguma variação foldlWhile aqui .
Will Ness
2
ele é engraçado como a resposta mais errado obtiver a maioria dos upvotes em SE .... não há problema em cometer erros, você está em boa companhia :) também. Mas o mecanismo de descoberta de conhecimento no SO / SE está definitivamente quebrado.
Will Ness
1
O código Clojure está quase correto, mas a condição de (= v1 150)usa o valor anterior v2(aka. e) É somada a ele.
NikoNyrh
1
Breaking this down line by line in case you're not familiar with Haskell's syntax-- Você é meu herói. Haskell é um mistério para mim.
Capitão Man
15
@WillNess Foi votada porque é a tradução e explicação mais imediatamente compreensíveis. O fato de estar errado é uma vergonha, mas relativamente sem importância aqui, porque os pequenos erros não negam o fato de que a resposta é útil. Mas é claro que deve ser corrigido.
Konrad Rudolph
33

Você pode facilmente convertê-lo em recursão. E possui uma agradável chamada recursiva otimizada pela cauda.

Pseudo-código :

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);
}
Eufórico
fonte
14
Sim. O equivalente funcional a um loop é recursão de cauda e o equivalente funcional a um condicional ainda é um condicional.
Jörg W Mittag
4
@ JörgWMittag Eu prefiro dizer que a recursão da cauda é o equivalente funcional a GOTO. (Não é tão ruim, mas ainda assim bastante estranho.) O equivalente a um loop, como Jules diz, é uma dobra adequada.
precisa saber é o seguinte
6
@leftaroundabout Eu discordo na verdade. Eu diria que a recursão da cauda é mais restrita do que ir, dada a necessidade de pular para si mesma e apenas na posição da cauda. É fundamentalmente equivalente a uma construção em loop. Eu diria que a recursão em geral é equivalente a GOTO. De qualquer forma, quando você compila a recursão da cauda, ​​a maioria se resume a um while (true)loop com o corpo da função em que o retorno antecipado é apenas uma breakdeclaração. Uma dobra, enquanto você estiver correto sobre se tratar de um loop, é na verdade mais restrita do que uma construção de loop geral; é mais como um para-cada loop
J_mie6
1
@ J_mie6 a razão pela qual considero a recursão da cauda mais como uma GOTOé que você precisa fazer uma contabilidade minuciosa de quais argumentos em que estado são passados ​​para a chamada recursiva, para garantir que ela realmente se comporte como pretendido. Isso não é necessário no mesmo grau em loops imperativos decentemente escritos (onde é bastante claro quais são as variáveis ​​com estado e como elas mudam em cada iteração), nem na recursão ingênua (onde geralmente não se faz muito com os argumentos e, em vez disso, com o argumento resultado é montado de maneira bastante intuitiva). ...
leftaroundabout
1
... Quanto às dobras: você está certo, uma dobra tradicional (catamorfismo) é um tipo muito específico de loop, mas esses esquemas de recursão podem ser generalizados (ana- / apo- / hilomorfismos); coletivamente, estes são IMO, o substituto adequado para loops imperativos.
precisa saber é o seguinte
13

Gosto muito da resposta de Jules , mas queria destacar ainda algo que as pessoas muitas vezes sentem falta da programação funcional preguiçosa, que é que tudo não precisa estar "dentro do loop". Por exemplo:

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

Você pode ver que cada parte da sua lógica pode ser calculada em uma função separada e depois composta em conjunto. Isso permite funções menores, geralmente muito mais fáceis de solucionar. Para o seu exemplo de brinquedo, talvez isso adicione mais complexidade do que remove, mas no código do mundo real as funções separadas são geralmente muito mais simples que o todo.

Karl Bielefeldt
fonte
a lógica está espalhada por todo o lado. esse código não será fácil de manter. nãostopAt10 é um bom consumidor. sua resposta é melhor do que a que você cita, pois isola corretamente o produtor básico de valores. seu consumo deve incorporar a lógica de controle diretamente, porém, é melhor implementado com apenas dois se um , explicitamente. isso seguiria de perto a estrutura e a lógica originais do código e seria fácil de manter. scanl (+) 0spanlast
Will Ness
6

A maioria dos exemplos de processamento de lista que você vai ver o uso de funções como map, filter, sumetc., que operam na lista como um todo. Mas no seu caso, você tem uma saída antecipada condicional - um padrão bastante incomum que não é suportado pelas operações de lista usuais. Portanto, você precisa descer um nível de abstração e usar a recursão - que também está mais próxima da aparência do exemplo imperativo.

Esta é uma tradução bastante direta (provavelmente não idiomática) no 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: ponto Jules que reduceem Clojure fazer suportar saída precoce. Usar isso é mais elegante:

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

De qualquer forma, você pode fazer qualquer coisa em linguagens funcionais, como em linguagens imperativas, mas geralmente precisa mudar um pouco sua mentalidade para encontrar uma solução elegante. Na codificação imperativa, você pensa em processar uma lista passo a passo, enquanto nas linguagens funcionais procura uma operação para aplicar a todos os elementos da lista.

JacquesB
fonte
veja a edição que acabei de adicionar à minha resposta: a reduceoperação do Clojure suporta saída antecipada.
Jules
@ Jules: Cool - essa é provavelmente uma solução mais idiomática.
JacquesB
Incorreta - ou takeWhilenão é uma 'operação comum'?
Jonathan fundido
@jcast - embora takeWhileseja uma operação comum, não é especialmente útil neste caso, porque você precisa dos resultados de sua transformação antes de decidir se deve parar. Em uma linguagem preguiçosa, isso não importa: você pode usar scane takeWhilenos resultados da verificação (consulte a resposta de Karl Bielefeldt, que, embora não use, takeWhilepode ser reescrita com facilidade), mas para uma linguagem estrita como o clojure, isso significa processar a lista inteira e descartar os resultados posteriormente. As funções do gerador poderiam resolver isso, no entanto, e acredito que o clojure as suporta.
Jules
@Jules take-whileem Clojure produz uma sequência lenta (de acordo com os documentos). Outra maneira de resolver isso seria com transdutores (talvez o melhor).
Ness Will
4

Conforme apontado por outras respostas, Clojure tem reducedque interromper as reduções mais cedo:

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

Esta é a melhor solução para sua situação específica. Você também pode obter um lote de milhagem de combinar reducedcom transduce, que permite utilizar transdutores de map, filteretc, no entanto, está longe de uma resposta completa à sua pergunta geral.

As continuações de escape são uma versão generalizada das instruções de interrupção e retorno. Eles são implementados diretamente em alguns Schemes ( call-with-escape-continuation), Common Lisp ( block+ return, catch+ throw) e até C ( setjmp+ longjmp). Continuações mais gerais delimitadas ou não limitadas, como encontradas no esquema padrão ou como mônadas de continuação em Haskell e Scala, também podem ser usadas como continuações de escape.

Por exemplo, no Racket você pode usar let/ecassim:

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

Muitos outros idiomas também têm construções semelhantes à continuação de escape na forma de tratamento de exceções. Em Haskell, você também pode usar uma das várias mônadas de erro foldM. Como eles são basicamente construções de manipulação de erro, usando exceções ou mônadas de erro para retornos iniciais, geralmente é culturalmente inaceitável e possivelmente muito lento.

Você também pode descer de funções de ordem superior para atender chamadas.

Ao usar loops, você insere a próxima iteração automaticamente quando atinge o final do corpo do loop. Você pode inserir a próxima iteração antecipadamente com continueou sair do loop com break(ou return). Ao usar chamadas de cauda (ou a loopconstrução de Clojure que imita a recursão de cauda), você sempre deve fazer uma chamada explícita para inserir a próxima iteração. Para parar o loop, você simplesmente não faz a chamada recursiva, mas fornece o valor diretamente:

(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))))))
nilern
fonte
1
Re usando mônadas de erro em Haskell, não acredito que exista uma penalidade real de desempenho aqui. Eles tendem a pensar nas linhas de tratamento de exceções, mas não funcionam da mesma maneira e não há necessidade de caminhar pela pilha; portanto, isso não deve ser um problema se usado dessa maneira. Além disso, mesmo que haja uma razão cultural para não usar algo como MonadError, o basicamente equivalente Eithernão tem esse viés apenas para o tratamento de erros; portanto, pode ser facilmente usado como um substituto.
Jules
@Jules Acho que retornar à esquerda não impede que a dobra visite a lista inteira (ou outra sequência). No entanto, não estou familiarizado com os componentes internos da biblioteca padrão de Haskell.
Nilern
2

A parte intricada é o loop. Vamos começar com isso. Um loop geralmente é convertido em estilo funcional, expressando a iteração com uma única função. Uma iteração é uma transformação da variável de loop.

Aqui está uma implementação funcional de um loop geral:

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

É preciso (um valor inicial da variável do loop, a função que expressa uma única iteração [na variável do loop]) (uma condição para continuar o loop).

Seu exemplo usa um loop em uma matriz, que também quebra. Esse recurso em sua linguagem imperativa é incorporado à própria linguagem. Na programação funcional, esse recurso geralmente é implementado no nível da biblioteca. Aqui está uma possível implementação

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

Nisso :

Eu uso um par ((val, next_pos)) que contém a variável de loop visível do lado de fora e a posição na matriz, que esta função oculta.

A função de iteração é um pouco mais complexa do que no loop geral; esta versão possibilita o uso do elemento atual da matriz. [Está na forma de caril .]

Tais funções são geralmente denominadas "fold".

Coloquei um "l" no nome para indicar que o acúmulo dos elementos da matriz é feito de maneira associativa à esquerda; imitar o hábito de linguagens de programação imperativas para iterar uma matriz de baixo para alto índice.

Coloquei um "c" no nome para indicar que esta versão do fold adota uma condição que controla se e quando o loop deve ser interrompido mais cedo.

É claro que essas funções utilitárias provavelmente estarão prontamente disponíveis na biblioteca base fornecida com a linguagem de programação funcional usada. Eu os escrevi aqui para demonstração.

Agora que temos todas as ferramentas que estão na linguagem no caso imperativo, podemos recorrer à implementação da funcionalidade específica do seu exemplo.

A variável no seu loop é um par ('resposta', um booleano que codifica se deve continuar).

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)

Observe que eu usei uma nova "variável" 'new_answer'. Isso ocorre porque na programação funcional não posso alterar o valor de uma "variável" já inicializada. Não me preocupo com o desempenho, o compilador pode reutilizar a memória da 'resposta' para 'new_answer' através da análise do tempo de vida, se achar que é mais eficiente.

Incorporando isso em nossa função de loop desenvolvida anteriormente:

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

"Matriz" aqui é o nome do módulo que exporta a função foldlc.

"punho", "segundo" representam funções que retornam o primeiro, segundo componente de seu parâmetro de par

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

Nesse caso, o estilo "sem ponto" aumenta a legibilidade da implementação do doSomeCalc:

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

(>>>) é a composição da função: (>>>) : (a -> b) -> (b -> c) -> (a -> c)

É o mesmo que acima, apenas o parâmetro "arr" é deixado de fora dos dois lados da equação que define.

Uma última coisa: verificar caso (array == null). Em linguagens de programação melhor projetadas, mas mesmo em linguagens mal projetadas, com alguma disciplina básica, utiliza-se um tipo opcional para expressar inexistência. Isso não tem muito a ver com programação funcional, que é a questão final, portanto, eu não lido com ela.

libeako
fonte
0

Primeiro, reescreva o loop levemente, de modo que cada iteração do loop seja encerrada antecipadamente ou mude answerexatamente uma vez:

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

Deve ficar claro que o comportamento desta versão é exatamente o mesmo de antes, mas agora é muito mais simples converter em estilo recursivo. Aqui está uma tradução direta de 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

Agora é puramente funcional, mas podemos melhorá-lo do ponto de vista de eficiência e legibilidade usando uma dobra em vez de recursão explícita:

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)

Nesse contexto, Leftsai antecipadamente com seu valor e Rightcontinua a recursão com seu valor.


Agora isso poderia ser simplificado um pouco mais, assim:

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

Isso é melhor como código Haskell final, mas agora é um pouco menos claro como ele é mapeado de volta para o Java original.

Joseph Sible-Restabelecer Monica
fonte