Может ли чисто функциональное решение этой проблемы быть таким же чистым, как императив?

10

У меня есть упражнение на Python следующим образом:

  • многочлен задается в виде набора коэффициентов, так что степени определяются индексами, например: (9,7,5) означает 9 + 7 * x + 5 * x ^ 2

  • написать функцию для вычисления ее значения для данного х

Так как в последнее время я занимаюсь функциональным программированием, я написал

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)

который я считаю нечитаемым, поэтому я написал

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]

по крайней мере так же нечитабельно, поэтому я написал

def evaluate3(poly, x):
  return poly[0]+x*evaluate(poly[1:],x) if len(poly)>0 else 0

который может быть менее эффективным (правка: я был неправ!), поскольку он использует множество умножений вместо возведения в степень, в принципе, мне здесь наплевать на измерения (правка: как глупо с моей стороны! Измерения указали бы на мое заблуждение!) и все еще не так читабельно (возможно), как итеративное решение:

def evaluate4(poly, x):
  result = 0
  for i in range(0,len(poly)):
      result += poly[i] * x**i
  return result

Есть ли чисто функциональное решение, столь же удобочитаемое, как императив, и близкое к нему по эффективности?

По общему признанию, изменение представления помогло бы, но это было дано упражнением.

Может быть Haskell или Lisp, а не только Python.

user1358
источник
7
По моему опыту, чисто функциональный код в том смысле, что он не использует изменяемые переменные (что также подразумевает for, например, не использование циклов), является плохой целью, к которой нужно стремиться в Python. Разумное повторное связывание переменных и отсутствие изменения объектов дает вам практически все преимущества и делает код бесконечно более читабельным. Поскольку числовые объекты являются неизменяемыми и связывают только два локальных имени, ваше «императивное» решение лучше реализует преимущества функционального программирования, чем любой «строго чистый» код Python.
2
Кстати, метод умножения - это метод Хорнера, и он более эффективен, чем возведение в степень на каждом шаге, поскольку возведение в степень требует тех же умножений, а затем и еще нескольких.
1
Python заведомо уродлив, когда вы lambdaначинаете использовать его , по сравнению с языками с более легкой анонимной синтаксической функцией. Частично это, вероятно, способствует «нечистой» внешности.
KChaloux
@KChaloux это именно то, что я собирался сказать. Поддержка функционального программирования во многом является запоздалой мыслью в Python, и это как бы показывает. Несмотря на это, я не думаю, что даже первая версия настолько ужасно нечитабельна, что вы не можете понять, что происходит.
Evicatos
Я действительно запутался в вашем коде, в то время как объем задачи имеет математическое уравнение, которое предельно ясно, почему бы вам просто не использовать это математическое уравнение дословно? Это довольно легко превратить в функцию для любого языка ... не уверен, что вы хотите отобразить, уменьшить или повторить что-либо для чего-то, когда вопрос требует функцию, которая оценивает одно уравнение и дает это уравнение - она ​​не запрашивает итерация вообще ...
Джимми Хоффа

Ответы:

13

Метод Хорнера, вероятно, более вычислительно эффективен, как указывает @delnan, но я бы назвал это довольно читабельным в Python для решения возведения в степень:

def eval_poly(poly, x):
    return sum( [a * x**i for i,a in enumerate(poly)] )
aelfric5578
источник
17
Снимите квадратные скобки и дайте переменным более описательные имена, и это даже лучше: sum(coeff * X**power for power, coeff in enumerate(poly))
Изката
1
Это как-то огорчает меня, что другие опубликованные ответы настолько сложны. Используйте язык в ваших интересах!
Изката
Понимание
7
@ user1358 Нет, это синтаксический сахар для состава mapи filter. Можно также думать о нем как о петле for определенной формы, но петли этой формы эквивалентны вышеупомянутому функциональному комбинатору.
7

Многие функциональные языки имеют реализации mapi, которые позволяют вам иметь индекс, сплетенный через карту. Объедините это с суммой, и вы получите следующее в F #:

let compute coefficients x = 
    coefficients 
        |> Seq.mapi (fun i c -> c * Math.Pow(x, (float)i))
        |> Seq.sum
Стивен Эверс
источник
2
И даже если они этого не делают, пока вы понимаете, как это mapработает, написать свой собственный будет довольно просто.
KChaloux
4

Я не понимаю, как ваш код соотносится с областью задачи, которую вы определили, поэтому я приведу свою версию того, что ваш код игнорирует область проблемы (на основе написанного вами императивного кода).

Довольно читаемый haskell (этот подход может быть легко переведен на любой язык FP, который имеет деструктуризацию списка и получается чистым и читаемым):

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

Иногда такой простой наивный подход в Haskell чище, чем более лаконичный подход к людям, менее привыкшим к FP.

Более четкий императивный подход, который все еще полностью чист:

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)

Бонус ко второму подходу заключается в том, что в монаде ST он будет работать очень хорошо.

Хотя, чтобы быть уверенным, наиболее вероятной реальной реализацией от Haskeller будет zipwith, упомянутый в другом ответе выше. zipWithЭто очень типичный подход, и я верю, что Python может имитировать подход комбинирования функций и индексатора, который можно отобразить.

Джимми Хоффа
источник
4

Если у вас просто есть (фиксированный) кортеж, почему бы не сделать это (в Haskell):

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

Если вместо этого у вас есть список коэффициентов, вы можете использовать:

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

или с уменьшением, как у вас было:

evalPolyList' coefs x = foldl' (\sum (c, p) -> sum + c*x^p) 0 $ zip coefs [0..]
Павел
источник
1
Это НЕ домашнее задание! Не говоря уже о том, что я уже сделал 3 решения.
user1358
Половина времени в Python (включая в этом случае), «кортеж» означает «неизменный список» и, следовательно, имеет произвольную длину.
очевидно произвольной длины
user1358
1
не из-за python, а потому, что многочлен подразумевает произвольную длину, и фиксированный размер не будет большим упражнением
user1358
1
@delnan Это интересно. Я всегда tupleимел в виду набор значений фиксированного размера, каждый из которых может иметь разные типы, которые нельзя добавлять или удалять. Я никогда не понимал, почему они нужны динамическому языку со списками, который принимает гетерогенные входные данные.
KChaloux
3

Существует общий набор шагов, которые вы можете использовать для улучшения читаемости функциональных алгоритмов:

  • Поместите имена в свои промежуточные результаты, вместо того, чтобы пытаться втиснуть все в одну строку.
  • Используйте именованные функции вместо лямбда-выражений, особенно в языках с подробным лямбда-синтаксисом. Гораздо проще читать что-то вроде evaluateTermдлинного лямбда-выражения. То, что вы можете использовать лямбду, не обязательно означает, что вы должны это делать .
  • Если одна из ваших теперь названных функций выглядит так, как будто она появляется довольно часто, скорее всего, она уже есть в стандартной библиотеке. Смотреть по сторонам. Мой питон немного ржавый, но похоже, что вы в основном заново enumerateили zipWith.
  • Часто видение названных функций и промежуточных результатов облегчает рассуждение о том, что происходит, и упрощает его, и в этот момент может иметь смысл вернуть обратно лямбду или объединить некоторые строки вместе.
  • Если императивный цикл выглядит более читабельным, скорее всего, для понимания будет хорошо работать.
Карл Билефельдт
источник