Я думаю, что естественный способ написать что-то подобное на Python выглядит примерно так:
tolerance = 0.00001
def fixed_point(f, first_guess):
guess = first_guess
next_guess = f(guess)
def close_enough(a, b):
return (abs(a - b) < tolerance)
while not close_enough(guess, next_guess):
guess = next_guess
next_guess = f(guess)
return next_guess
Этот:
- использует цикл
while, а не рекурсию, как в Python;
- не использует какое-то ужасное
while True ... с побегом, что просто сбивает с толку.
(На самом деле, поскольку вызов функции в Python, как правило, очень медленный, вероятно, более естественно открыть код вызова close_enough и полностью удалить локальную функцию.)
Но это императивный код: он полон присваиваний (первые два «присваивания» на самом деле являются привязками переменных, поскольку Python не различает их синтаксически, но более поздние присваивания действительно являются присваиваниями). Мы хотим выразить это так, чтобы не было присваивания. Мы также хотим заменить его чем-то, что не использует никаких циклических конструкций или выражает эти циклические конструкции в терминах вызовов функций.
Мы можем сделать это двумя способами:
- мы можем рассматривать функцию верхнего уровня как то, что мы вызываем рекурсивно;
- мы можем определить некоторую локальную функцию, через которую мы рекурсивно.
Что из этого мы делаем, это действительно выбор, и в данном случае это, вероятно, не имеет большого значения. Однако у второго подхода часто есть значительные преимущества: в общем случае функция верхнего уровня (функция, которая находится в каком-то интерфейсе, который мы можем предоставить людям) может иметь всевозможные дополнительные аргументы, некоторые из которых могут иметь значения по умолчанию, и поэтому on, который мы действительно не хотим передавать через более поздние вызовы; функция верхнего уровня также может просто не иметь соответствующей сигнатуры аргумента, потому что итерационные шаги могут выполнять итерацию по некоторому набору значений, полученных из аргументов функции верхнего уровня.
Таким образом, обычно лучше выражать итерацию в терминах локальной функции, хотя это может быть не всегда так.
Вот рекурсивная версия на Python, которая также делает сигнатуру функции верхнего уровня заметно богаче. Обратите внимание, что этот подход был бы ужасным стилем в Python, поскольку Python не делает ничего особенного с хвостовыми вызовами. Код также замусорен returns, потому что Python не является языком выражений (не верьте людям, которые говорят, что «Python подобен Lisp»: это не так):
default_tolerance = 0.00001
def fixed_point(f, first_guess, tolerance=default_tolerance):
guess = first_guess
next_guess = f(guess)
def close_enough(a, b):
return (abs(a - b) < tolerance)
def step(guess, next_guess):
if close_enough(guess, next_guess):
return next_guess
else:
return step(next_guess, f(next_guess))
return step(first_guess, f(first_guess))
Что ж, в Scheme это гораздо естественнее: вот та же самая функция, написанная на Scheme (на самом деле, в Racket):
(define default-tolerance 0.00001)
(define (fixed-point f initial-guess #:tolerance (tolerance default-tolerance))
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess next)
(if (close-enough? guess next)
next
(try next (f next))))
(try initial-guess (f initial-guess)))
Единственное, что в этом раздражает, так это то, что мы должны запускать итерацию после определения try. Ну, мы могли бы избежать даже этого с помощью макроса:
(define-syntax-rule (iterate name ((var val) ...) form ...)
(begin
(define (name var ...)
form ...)
(name val ...)))
И теперь мы можем написать функцию как:
(define (fixed-point f initial-guess #:tolerance (tolerance default-tolerance))
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(iterate try ((guess initial-guess) (next (f initial-guess)))
(if (close-enough? guess next)
next
(try next (f next)))))
Ну, на самом деле нам не нужно писать этот макрос iterate: он настолько полезен в Scheme, что уже существует в виде специальной версии let под названием 'named let':
(define (fixed-point f initial-guess #:tolerance (tolerance default-tolerance))
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(let try ((guess initial-guess) (next (f initial-guess)))
(if (close-enough? guess next)
next
(try next (f next)))))
И с любой из этих версий:
> (fixed-point cos 0)
0.7390822985224023
> (fixed-point cos 0 #:tolerance 0.1)
0.7013687736227565
Наконец, мета-комментарий: я не понимаю, почему вы пытаетесь изучить Scheme с помощью Emacs Lisp. Эти два языка совсем не похожи: если вы хотите изучить Scheme, используйте Scheme: вероятно, существуют сотни систем Scheme, почти все из которых бесплатны.
person
Community
schedule
26.12.2019
