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.
break
ereturn answer
pode ser substituída por uma partereturn
interna do loop. No FP, você pode implementar esse retorno antecipado usando continuações, por exemplo, en.wikipedia.org/wiki/ContinuationtakeWhile
.Respostas:
O equivalente mais próximo de loop sobre uma matriz na maioria das linguagens funcionais é uma
fold
funçã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:Quebrando essa linha por linha, caso você não esteja familiarizado com a sintaxe de Haskell, isso funciona assim:
Define o tipo da função, aceitando uma lista de entradas e retornando um único int.
O corpo principal da função: dado argumento
values
, retornefoldr1
chamado com argumentoscombine
(que definiremos abaixo) evalues
.foldr1
é uma variante da primitiva da dobra que começa com o acumulador definido como o primeiro valor da lista (daí o1
nome 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í or
nome da função). Portanto,foldr1 f [1,2,3]
é equivalente af 1 (f 2 3)
(ouf(1,f(2,3))
na sintaxe mais convencional do tipo C).Definindo a
combine
função local: recebe dois argumentos,v1
ev2
. Quandov1
é 10, apenas retornav1
. Nesse caso, a v2 nunca é avaliada , portanto, o loop para aqui.Como alternativa, quando v1 é 150, adiciona 100 extras a ele e 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
fold
função em sua biblioteca padrão que inclua suporte específico para o término antecipado. Isso é muitas vezes chamadofoldWhile
,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 nomeação, e
fold
não é isso que você está procurando (é um mecanismo mais avançado destinado a permitir a computação paralela), masreduce
é o mais direto equivalente. A rescisão antecipada ocorre se areduced
funçã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: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.
fonte
v1 v2
são confusos:v1
é um "valor da matriz", masv2
é 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çãofoldlWhile
aqui .(= v1 150)
usa o valor anteriorv2
(aka.e
) É somada a ele.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.Você pode facilmente convertê-lo em recursão. E possui uma agradável chamada recursiva otimizada pela cauda.
Pseudo-código :
fonte
GOTO
. (Não é tão ruim, mas ainda assim bastante estranho.) O equivalente a um loop, como Jules diz, é uma dobra adequada.GOTO
. De qualquer forma, quando você compila a recursão da cauda, a maioria se resume a umwhile (true)
loop com o corpo da função em que o retorno antecipado é apenas umabreak
declaraçã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 loopGOTO
é 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). ...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:
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.
fonte
stopAt10
é 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 (+) 0
span
last
A maioria dos exemplos de processamento de lista que você vai ver o uso de 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. 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:
Edit: ponto Jules que
reduce
em Clojure fazer suportar saída precoce. Usar isso é mais elegante: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.
fonte
reduce
operação do Clojure suporta saída antecipada.takeWhile
não é uma 'operação comum'?takeWhile
seja 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 usarscan
etakeWhile
nos resultados da verificação (consulte a resposta de Karl Bielefeldt, que, embora não use,takeWhile
pode 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.take-while
em Clojure produz uma sequência lenta (de acordo com os documentos). Outra maneira de resolver isso seria com transdutores (talvez o melhor).Conforme apontado por outras respostas, Clojure tem
reduced
que interromper as reduções mais cedo:Esta é a melhor solução para sua situação específica. Você também pode obter um lote de milhagem de combinar
reduced
comtransduce
, que permite utilizar transdutores demap
,filter
etc, 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/ec
assim: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
continue
ou sair do loop combreak
(oureturn
). Ao usar chamadas de cauda (ou aloop
construçã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:fonte
MonadError
, o basicamente equivalenteEither
não tem esse viés apenas para o tratamento de erros; portanto, pode ser facilmente usado como um substituto.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:
É 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
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).
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:
"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
Nesse caso, o estilo "sem ponto" aumenta a legibilidade da implementação do doSomeCalc:
(>>>) é 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.
fonte
Primeiro, reescreva o loop levemente, de modo que cada iteração do loop seja encerrada antecipadamente ou mude
answer
exatamente uma vez: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:
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:
Nesse contexto,
Left
sai antecipadamente com seu valor eRight
continua a recursão com seu valor.Agora isso poderia ser simplificado um pouco mais, assim:
Isso é melhor como código Haskell final, mas agora é um pouco menos claro como ele é mapeado de volta para o Java original.
fonte