Расширенный евклидов алгоритм F # с вопросом о продолжениях - PullRequest
Новая
       35

Расширенный евклидов алгоритм F # с вопросом о продолжениях

2 голосов
/ 28 января 2020

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

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

Я запускал eea 7 3 вручную, и (правильный) результат, который я вычислил, был ( 1, 1, -2)

Но когда я запускаю его в интерпретаторе, я получаю 

eea 7 3;;
val it : int * int * int = (1, 0, 1)

Вот моя реализация: 

let eea a b = 
    let rec contEEA a b f = 
        match b with
        | 0 -> f () (a,1,0)
        | _ -> 
            contEEA b (a%b) (fun () t ->
                let (d,x',y') = t
                (d, y', x'-(y'*(a/b)))
            )
    contEEA a b (fun () t -> t)

Для справки: наивный подход прямо из учебника это 

let rec eea_gcd a b =
    match b with
    | 0 -> (a, 1, 0)
    | _ -> 
        let d, x', y' = eea_gcd b (a % b)
        (d, y', x'-(y'*(a/b)))

1 Ответ

3 голосов
/ 28 января 2020

Ваша основанная на продолжении версия всегда выполняет ровно одну итерацию (последнюю). Когда вы делаете рекурсивный вызов, ваше продолжение просто возвращает результат, а не «возвращает» его предыдущему вызову, передавая предыдущее продолжение.

Таким образом, последовательность вызовов выглядит следующим образом:

  1. eea 7 3
  2. contEEA 7 3 (fun () t -> t)
  3. b <> 0 ==> второй случай совпадений
  4. contEEA 3 1 (fun () t -> ... (d, y', ...))
  5. b <> 0 ==> второй случай соответствует
  6. contEEA 1 0 (fun () t -> ... (d, y', ...))
  7. b = 0 ==> первый случай соответствует
  8. Продолжение называется f () (1, 1, 0)
  9. продолжение вычисляет результат (1, 0, 1 - (0*(3/1)) = (1, 0, 1) и немедленно возвращает его

То, что вы хотите сделать вместо этого, - это когда первое продолжение вычисляет результат (1, 0, 1), оно должно передать его предыдущее продолжение, так что оно может продолжать вычисления оттуда, в конечном итоге передавая результат самому первому продолжению fun () t -> t, которое возвращает его потребителю.

Для этого, замените эту строку: 

(d, y', x'-(y'*(a/b)))

этим: 

f (d, y', x'-(y'*(a/b)))

Кроме того, несколько замечаний по некоторым другим аспектам.

  1. Первый параметр продолжения (единица измерения ()) необязателен, так как никогда не используется (и как это может быть?). Вы можете потерять его.

  2. После удаления параметра модуля первым продолжением становится fun t -> t, которое имеет специальное имя id (он же «функция идентификации»)

  3. Вместо того, чтобы деструктурировать тройку с помощью let, вы можете сделать это прямо в объявлении параметра. Параметрами могут быть шаблоны!

Применяя все вышеперечисленное, а также реальное решение проблемы, вот лучшая версия: 

let eea a b = 
    let rec contEEA a b f = 
        match b with
        | 0 -> f (a,1,0)
        | _ -> 
            contEEA b (a%b) (fun (d,x',y') -> 
                f (d, y', x'-(y'*(a/b)))
            )
    contEEA a b id
...