Зачем использовать рекурсивную функцию вместо `while true do` в F #? - PullRequest
Новая
       24

Зачем использовать рекурсивную функцию вместо `while true do` в F #?

0 голосов
/ 30 апреля 2018

Наблюдая за Томасом Петричеком курс Множественного взгляда (который, я полагаю, знает, о чем он говорит), я увидел код, подобный следующему ... 

let echo =
  MailboxProcessor<string>.Start(fun inbox ->
    async {
      while do true
        let! msg = inbox.Receive()
    printfn "Hello %s" msg
    })

Не обращая внимания на тот факт, что это было для демо-агентов, меня интересует внутренняя функция, которая использует while do true, чтобы она работала бесконечно.

Пока я искал другой пример агентов, я увидел, что многие другие люди используют такой код ... 

let counter =
  MailboxProcessor.Start(fun inbox ->
    let rec loop n =
      async { do printfn "n = %d, waiting..." n
        let! msg = inbox.Receive()
        return! loop(n+msg) }
    loop 0)

Код скопирован с Wikibooks .

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

Теперь я понимаю, что во втором случае рекурсия - это удобный способ передачи закрытого значения внутренней функции без необходимости использования изменяемого локального значения, но есть ли какая-либо другая причина использовать здесь рекурсию, а не while do true? Будет ли какая-то польза от написания первого фрагмента кода с использованием рекурсии?

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

Ответы [ 3 ]

0 голосов
/ 30 апреля 2018

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

Рекурсия облегчает использование неизменяемого состояния, и я считаю while цикл более приятным, если у вас нет состояния или если вы используете изменяемое состояние. Использование изменяемого состояния часто весьма полезно, поскольку MailboxProcessor защищает вас от одновременного доступа, и вы можете сохранять состояние локальным, поэтому такие вещи, как Dictionary (эффективная хэш-таблица), часто полезны.

В целом:

  • Если вам не нужно государство, я бы предпочел while
  • Если у вас изменчивое состояние (например, Dictionary или ResizeArray), я бы выбрал while
  • Если у вас есть какое-то неизменное состояние (например, функциональный список или целое число), то рекурсия лучше
  • Если ваша логика переключается между несколькими режимами работы, то вы можете написать ее как две взаимно рекурсивные функции, что недопустимо с циклами.
0 голосов
/ 30 апреля 2018

В выражениях цикла F # for и while отсутствуют возможности, общие для других языков:

  1. continue - пропустить остаток цикла и перезапустить его с начала выражения цикла.
  2. break - преждевременно остановить цикл.

Если вы хотите, чтобы continue и break не делали то, что я делал в начале, напишите очень сложное тестовое выражение для циклов while. Вместо этого хвостовая рекурсия - лучший ответ в F #: 

let vs : int [] = ...
let rec findPositiveNumberIndex i =
  if i < vs.Length then
    if vs.[i] > 0 then 
      Some i
    else 
      findPositiveNumberIndex (i + 1)
  else
    None
match findPositiveNumberIndex 0 with
| Some i -> printfn "First positive number index: %d" i
| None   -> printfn "No positive numbers found"

В коде, подобном этому, F # применяет нечто, называемое оптимизацией хвостового вызова (TCO), которое преобразует приведенный выше код в цикл while с break. Это означает, что мы не исчерпаем пространство стека, и цикл эффективен. TCO - это функция, которой нет в C #, поэтому мы не хотим писать код, подобный описанному выше, в C #.

Как и другие говорят с хвостовой рекурсией, иногда можно избежать изменчивого состояния, но это еще не все.

С помощью рекурсии хвоста ваши выражения цикла могут возвращать хороший результат.

Кроме того, если вы хотите быстро выполнять итерацию в F # для таких типов, как int64 или с приращением, отличным от 1 и -1, вы должны полагаться на хвостовую рекурсию. Причина в том, что F # делает только эффективные for выражения для целых и приращений 1 и -1. 

for i in 0..100 do
  printfn "This is a fast loop"

for i in 0..2..100 do
  printfn "This is a slow loop"  

for i in 0L..100L do
  printfn "This is a slow loop"

Иногда, когда вы охотитесь за производительностью, хитрость заключается в цикле к 0 (сохраняет регистр процессора). К сожалению, способ, которым F # генерирует код цикла for, работает не так хорошо, как хотелось бы надеяться: 

for i = 100 downto 0 do
  printfn "Unfortunately this is not as efficient as it can be"

Хвостовая рекурсия в направлении 0 сохраняет регистр ЦП.

(К сожалению, компилятор F # не объединяет тест и инструкцию цикла для хвостовой рекурсии, так что это не так хорошо, как могло бы быть)

0 голосов
/ 30 апреля 2018

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

Вас может заинтересовать этот вопрос, поскольку он объясняет мой ответ немного дальше: рекурсия против итерации

...