Преобразование из императивного в функциональное программирование [Python в Standard ML] - PullRequest
Новая
       25

Преобразование из императивного в функциональное программирование [Python в Standard ML]

3 голосов
/ 22 февраля 2010

У меня есть спецификация функции, в которой говорится, что она должна оценивать полиномиальную функцию от одной переменной. Коэффициент функции приведен в виде списка. Он также принимает значение переменной как действительное.

Например: eval (2, [4, 3, 2, 1]) = 26 (1 * x ^ 3 + 2 * x ^ 2 + 3 * x ^ 1 + 4 * x ^ 0, где x = 2)

Вот функция в python, но я не уверен, как преобразовать ее в SML. У меня проблемы с поиском способа передать значение итерации без изменения параметров функции. Он должен оставаться реальным * реальным списком -> реальной функцией. 

def eval(r, L):
    sum = 0
    for i in range(0, len(L)):
        sum = sum + L[i] * (r ** i)
    return sum

Ответы [ 2 ]

4 голосов
/ 22 февраля 2010

Обычный способ выражения сумм на функциональных языках - это сгиб. Вы можете избавиться от необходимости в индексе (и функции для возведения целого числа в степень другого целого числа), умножив сумму на r в каждой итерации: 

fun eval radix lst = let
  fun f (element, sum) = sum * radix + element
in
  foldr f 0 lst
end

Теперь функцию можно использовать так: 

- eval 10 [1,2,3];
val it = 321 : int
1 голос
/ 22 февраля 2010

Вы можете использовать явную рекурсию, чтобы пройти по списку коэффициентов, возвести в степень основание и подвести итог. 

fun eval r =
    let fun step (power, sum) (coeff :: rest) =
                step (power * r, sum + coeff * power) rest
          | step (_, sum) nil = sum
    in step (1, 0)
    end

Конструктивно это похоже на складку, и становится понятнее, если мы заменим ее на одну. 

fun eval r lst =
    let fun step (coeff, (power, sum)) = (power * r, sum + coeff * power)
        val (_, sum) = foldl step (1, 0) lst
    in sum
    end

Вы можете изменить порядок операций, чтобы использовать схему Хорнера, как упомянуто в комментарии KennyTM: это приведет к ответу sepp2k, который требует вдвое меньше умножений, но использует больше места в стеке.

...