Quais são os equivalentes funcionais das instruções de quebra imperativa e outras verificações de loop?

35

Digamos que eu tenha a lógica abaixo. Como escrever isso na 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 ... eu vejo apenas explica o simples caso de uma função matemática direta dizer "Soma". Mas, eu tenho uma lógica semelhante ao acima escrito em Java e gostaria de migrar isso para código funcional no Clojure. Se não podemos fazer o que foi dito acima em FP, então o tipo de promoções para FP não indica isso explicitamente.

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

    
por Vicky 03.01.2018 / 08:24
fonte

6 respostas

45

O equivalente mais próximo a um loop em uma matriz na maioria das linguagens funcionais é uma função fold , 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 é aumentado por uma variedade de funções adicionais que fornecem recursos extras, incluindo a opção de parar cedo quando alguma condição surgir. Em idiomas preguiçosos (por exemplo, Haskell), a interrupção antecipada pode ser obtida simplesmente por não avaliar mais nada ao longo da lista, o que fará com que valores adicionais nunca sejam gerados. Portanto, traduzindo seu exemplo para Haskell, eu 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 isso 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 ints e retornando um único int.

doSomeCalc values = foldr1 combine values

O corpo principal da função: dado argumento values , return foldr1 chamado com argumentos combine (que definiremos abaixo) e values . foldr1 é uma variante da primitiva de dobras que começa com o conjunto de acumuladores para o primeiro valor da lista (daí o 1 no nome da função), então combina-a usando a função especificada pelo usuário da esquerda para a direita geralmente chamado de dobra direita , portanto, o r no nome 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 função combine local: ela recebe dois argumentos, v1 e v2 . Quando v1 é 10, apenas retorna v1 . Nesse caso, v2 nunca é avaliado , então o loop pára aqui.

                      | v1 == 150 = v1 + 100 + v2

Alternativamente, quando v1 é 150, adiciona um extra a 100 e adiciona v2.

                      | otherwise = v1 + v2

E, se nenhuma dessas condições for verdadeira, apenas adiciona v1 a v2.

Agora, esta solução é um tanto 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. Eu não conheço o Clojure, mas acredito que ele usa uma avaliação rigorosa, então eu esperaria que ele tivesse uma função fold em sua biblioteca padrão que inclui suporte específico para terminação antecipada. Isso geralmente é chamado de foldWhile , foldUntil ou similar.

Uma rápida olhada na documentação da biblioteca Clojure sugere que ela é um pouco diferente da maioria das linguagens funcionais na nomenclatura, e que fold não é o que você está procurando (é um mecanismo mais avançado destinado a permitir computação paralela ) mas reduce é o equivalente mais direto. A finalização antecipada ocorre se a função reduced for chamada dentro de sua função de combinação. Não tenho 100% de certeza de que entendi a sintaxe, mas suspeito que o que você está procurando é algo assim:

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

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

    
por 03.01.2018 / 09:23
fonte
31

Você pode facilmente convertê-lo em recursão. E tem ótima chamada recursiva otimizada para a cauda.

Pseudocó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);
}
    
por 03.01.2018 / 08:41
fonte
12

Eu gosto muito da resposta de Jules , mas eu também queria destacar algo que as pessoas muitas vezes sentem falta de funcionalidade preguiçosa programação, 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, em seguida, composta em conjunto. Isso permite funções menores, que geralmente são muito mais fáceis de solucionar. Para o seu exemplo de brinquedo, talvez isso acrescente mais complexidade do que remove, mas no código do mundo real, as funções de divisão são geralmente muito mais simples que o todo.

    
por 03.01.2018 / 14:52
fonte
6

A maioria dos exemplos de processamento de lista você verá funções como map , filter , sum etc. 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. Então você precisa descer um nível de abstração e usar recursão - que também está mais perto de como o exemplo imperativo parece.

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

Editar: Jules salienta que reduce no Clojure do suportam a saída antecipada. 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)))

Em qualquer caso, 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 em linguagens funcionais você procura uma operação para aplicar a todos os elementos da lista.

    
por 03.01.2018 / 09:39
fonte
3

Como apontado por outras respostas, o Clojure tem reduced para interromper as reduções antecipadamente:

(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 particular. Você também pode obter muita milhagem combinando reduced com transduce , o que permite usar transdutores de map , filter etc. No entanto, está longe de ser uma resposta completa à sua pergunta geral.

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

Por exemplo, em Racket você pode usar let/ec assim:

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

Muitas outras linguagens também têm construções de 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 com foldM . Porque eles são principalmente construções de tratamento de erros usando exceções ou mônadas de erro para retornos iniciais é geralmente culturalmente inaceitável e possivelmente muito lento.

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

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 com continue ou sair do loop com break (ou return ). Ao usar chamadas finais (ou a construção loop do Clojure que imita a recursão da cauda), você deve sempre fazer uma chamada explícita para entrar na próxima iteração. Para interromper o loop, você não faz a chamada recursiva, mas informa 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))))))
    
por 04.01.2018 / 11:13
fonte
2

A parte intrincada é o loop. Vamos começar com isso. Geralmente, um loop é 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

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

Seu exemplo usa um loop em uma matriz, que também é interrompida. Essa capacidade em sua linguagem imperativa é incorporada à própria linguagem. Na programação funcional, essa capacidade geralmente é implementada 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))

Nele:

Eu uso um par ((val, next_pos)) que contém a variável de loop visível 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 torna possível usar o elemento atual da matriz. [Ele está no curry do formulário.]

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

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

Eu coloquei um "c" no nome para indicar que esta versão do fold tem uma condição que controla se e quando o loop deve ser parado antes.

É claro que essas funções de utilidade 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 no idioma no caso imperativo, podemos recorrer para implementar a funcionalidade específica do seu exemplo.

A variável em seu loop é um par ('answer', 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)

Note 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 de 'answer' para 'new_answer' por meio de análise de tempo de vida, se achar que é mais eficiente.

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

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

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

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

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

Neste caso, o estilo "sem pontos" 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 definidora.

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, usa-se um tipo opcional para expressar não-linguagem. existência. Isso não tem muito a ver com programação funcional, sobre o qual a questão é, afinal, eu não lide com isso.

    
por 04.01.2018 / 13:17
fonte