Eu tenho um exercício em Python da seguinte maneira:
um polinômio é dado como uma tupla de coeficientes, de modo que as potências sejam determinadas pelos índices, por exemplo: (9,7,5) significa 9 + 7 * x + 5 * x ^ 2
escreva uma função para calcular seu valor para x
Desde que eu estou na programação funcional ultimamente, escrevi
def evaluate1(poly, x):
coeff = 0
power = 1
return reduce(lambda accu,pair : accu + pair[coeff] * x**pair[power],
map(lambda x,y:(x,y), poly, range(len(poly))),
0)
que considero ilegível, então escrevi
def evaluate2(poly, x):
power = 0
result = 1
return reduce(lambda accu,coeff : (accu[power]+1, accu[result] + coeff * x**accu[power]),
poly,
(0,0)
)[result]
que é pelo menos tão ilegível, então eu escrevi
def evaluate3(poly, x):
return poly[0]+x*evaluate(poly[1:],x) if len(poly)>0 else 0
que pode ser menos eficiente (editar: eu estava errado!), pois usa muitas multiplicações em vez de exponenciação; em princípio, não me importo com medições aqui (editar: que bobagem minha! A medição teria apontado meu equívoco!) e ainda não é tão legível (sem dúvida) quanto a solução iterativa:
def evaluate4(poly, x):
result = 0
for i in range(0,len(poly)):
result += poly[i] * x**i
return result
Existe uma solução funcional pura tão legível quanto o imperativo e próxima a ela em eficiência?
É certo que uma mudança de representação ajudaria, mas isso foi dado pelo exercício.
Também pode ser Haskell ou Lisp, não apenas Python.
for
loops, por exemplo) é um objetivo ruim para o Python. Reconectar variáveis criteriosamente e não alterar objetos fornece quase todos os benefícios e torna o código infinitamente mais legível. Como os objetos numéricos são imutáveis e apenas religam dois nomes locais, sua solução "imperativa" realiza melhor as virtudes da programação funcional do que qualquer código Python "estritamente puro".lambda
, comparado a idiomas com uma função de sintaxe anônima mais leve. Parte disso provavelmente contribui para a aparência "impura".Respostas:
O método de Horner é provavelmente mais eficiente computacionalmente como o @delnan aponta, mas eu chamaria isso de legível em Python para a solução de exponenciação:
fonte
sum(coeff * X**power for power, coeff in enumerate(poly))
map
efilter
. Também se pode pensar nele como um loop for de uma forma particular, mas os loops dessa forma são equivalentes ao combinador funcional acima mencionado.Muitas linguagens funcionais têm implementações de mapi que permitem que você tenha um índice tecido através de um mapa. Combine isso com uma soma e você terá o seguinte em F #:
fonte
map
funciona, deve ser bem simples escrever um.Não entendo como o seu código se relaciona com o escopo do problema que você definiu, por isso darei minha versão do que seu código ignora o escopo do problema (com base no código imperativo que você escreveu).
Haskell bastante legível (essa abordagem pode ser facilmente traduzida para qualquer linguagem FP que tenha a desestruturação da lista e saia pura e legível):
Às vezes, a abordagem simples e ingênua em haskell é mais limpa do que a abordagem mais concisa para pessoas menos acostumadas ao FP.
Uma abordagem mais claramente imperativa que ainda é completamente pura é:
Se o bônus da segunda abordagem estiver na mônada do ST, ele funcionará muito bem.
Embora seja certo, a implementação real mais provável de um Haskeller seria o zip mencionado em outra resposta acima.
zipWith
é uma abordagem muito típica e acredito que o Python possa imitar a abordagem de combinação de funções e um indexador que pode ser mapeado.fonte
Se você apenas possui uma tupla (fixa), por que não fazer isso (em Haskell):
Se, em vez disso, você tiver uma lista de coeficientes, poderá usar:
ou com uma redução como você teve:
fonte
tuple
como um conjunto de valores de tamanho fixo, cada um dos tipos potencialmente diferentes, que não podem ser adicionados ou removidos. Eu realmente nunca entendi por que uma linguagem dinâmica com listas, que aceita entradas heterogêneas, precisaria delas.Há um conjunto geral de etapas que você pode usar para melhorar a legibilidade dos algoritmos funcionais:
evaluateTerm
uma expressão lambda longa. Só porque você pode usar um lambda não significa necessariamente que deveria .enumerate
ouzipWith
.fonte