Uma solução de funcionalidade pura para esse problema pode ser tão limpa quanto o imperativo?

10

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.

user1358
fonte
7
Na minha experiência, código puramente funcional no sentido de não usar variáveis ​​mutáveis ​​(o que também implica em não usar forloops, 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".
2
BTW O método de multiplicação é o método de Horner e é mais eficiente que a exponenciação em cada etapa, pois a exponenciação exige as mesmas multiplicações e, em seguida, mais algumas.
1
O Python é notoriamente feio quando você começa a usar lambda, comparado a idiomas com uma função de sintaxe anônima mais leve. Parte disso provavelmente contribui para a aparência "impura".
KChaloux
@KChaloux é exatamente o que eu ia dizer. O suporte à programação funcional é uma reflexão tardia no Python em muitos aspectos, e meio que mostra. Mesmo assim, acho que nem a primeira versão é tão terrivelmente ilegível que você não consegue entender o que está acontecendo.
Evicatos
Estou realmente confuso com o seu código, enquanto o escopo do problema tem uma equação matemática extremamente clara, por que você não usa apenas essa equação matemática literalmente? É facilmente transformado em uma função, dada qualquer idioma ... não sei ao certo o que você deseja mapear, reduzir ou iterar quando a pergunta está pedindo uma função que avalie uma única equação e a dê - ela não pede iteração em tudo ...
Jimmy Hoffa

Respostas:

13

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:

def eval_poly(poly, x):
    return sum( [a * x**i for i,a in enumerate(poly)] )
aelfric5578
fonte
17
Largue os colchetes e dê um nome mais descritivo às variáveis, e é ainda melhor: sum(coeff * X**power for power, coeff in enumerate(poly))
Izkata
1
Me entristece que as outras respostas postadas sejam tão complexas. Use o idioma para sua vantagem!
precisa saber é o seguinte
compreensão é como um loop for "contrabandeado" em programação funcional
user1358
7
@ user1358 Não, é açúcar sintático para a composição de mape filter. 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.
7

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 #:

let compute coefficients x = 
    coefficients 
        |> Seq.mapi (fun i c -> c * Math.Pow(x, (float)i))
        |> Seq.sum
Steven Evers
fonte
2
E mesmo que não, desde que você entenda como mapfunciona, deve ser bem simples escrever um.
KChaloux
4

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

eval acc exp val [] = acc
eval acc exp val (x:xs) = eval (acc + execPoly) (exp+1) xs
  where execPoly = x * (val^exp)

À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 é:

steval val poly = runST $ do
  accAndExp <- newSTRef (0,1)
  forM_ poly $ \x -> do
    modifySTRef accAndExp (updateAccAndExp x)
  readSTRef accAndExp
  where updateAccAndExp x (acc, exp) = (acc + x*(val^exp), exp + 1)

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.

Jimmy Hoffa
fonte
4

Se você apenas possui uma tupla (fixa), por que não fazer isso (em Haskell):

evalPolyTuple (c, b, a) x = c + b*x + a*x^2

Se, em vez disso, você tiver uma lista de coeficientes, poderá usar:

evalPolyList coefs x = sum $ zipWith (\c p -> c*x^p) coefs [0..]

ou com uma redução como você teve:

evalPolyList' coefs x = foldl' (\sum (c, p) -> sum + c*x^p) 0 $ zip coefs [0..]
Paulo
fonte
1
NÃO é lição de casa! Sem mencionar que eu já fiz 3 soluções.
user1358
Metade do tempo em Python (incluindo neste caso), "tupla" significa "lista imutável" e, portanto, é arbitrária.
obviamente comprimento arbitrário
user1358
1
não por causa de python, mas porque polinomial implica comprimento arbitrário e tamanho fixo não seria um grande de um exercício
user1358
1
@ delnan Isso é interessante. Sempre entendi tuplecomo 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.
KChaloux
3

Há um conjunto geral de etapas que você pode usar para melhorar a legibilidade dos algoritmos funcionais:

  • Coloque nomes em seus resultados intermediários, em vez de tentar empinar tudo em uma linha.
  • Use funções nomeadas em vez de lambdas, especialmente em idiomas com sintaxe lambda detalhada. É muito mais fácil ler algo como evaluateTermuma expressão lambda longa. Só porque você pode usar um lambda não significa necessariamente que deveria .
  • Se uma de suas funções agora nomeadas parecer algo que surgiria com bastante frequência, é provável que já esteja na biblioteca padrão. Olhar em volta. Meu python está um pouco enferrujado, mas parece que você basicamente reinventou enumerateou zipWith.
  • Freqüentemente, ver as funções e os resultados intermediários nomeados facilita o raciocínio sobre o que está acontecendo e a simplifica; nesse ponto, pode fazer sentido colocar um lambda de volta ou combinar algumas linhas novamente.
  • Se um loop for imperativo parecer mais legível, é provável que uma compreensão funcione bem.
Karl Bielefeldt
fonte