Цикл против рекурсии с F # - PullRequest
Новая
       15

Цикл против рекурсии с F #

4 голосов
/ 05 марта 2012

Пример кода здесь решает проблему Эйлера проекта:

Начиная с цифры 1 и двигаясь вправо по часовой стрелке Направление спирали 5 на 5 формируется следующим образом: 

 21 22 23 24 25 
 20  7  8  9 10  
 19  6  1  2 11    
 18  5  4  3 12 
 17 16 15 14 13

Можно проверить, что сумма чисел на диагонали 101.

Какова сумма чисел на диагонали в 1001 на 1001 спираль образовалась таким же образом?

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

let answer = 
    let dimensions = 1001
    let max_number = dimensions * dimensions

    let rec loop total increment increment_count current =
        if current > max_number then total
        else
            let new_inc, new_inc_count =
                if increment_count = 4 then increment + 2, 0
                else increment, increment_count + 1
            loop (total + current) new_inc new_inc_count (current + increment)            
    loop 0 2 1 1

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

let answer = 
    let dimensions = 1001
    let mutable total = 1
    let mutable increment = 2
    let mutable current = 1

    for spiral_layer_index in {1..(dimensions- 1) / 2} do
        for increment_index in {1..4} do
            current <- current + increment
            total <- total + current 
        increment <- increment + 2
    total

Несмотря на то, что люди с большими математическими способностями решили проблему аналитически, есть ли лучший способ сделать это в функциональном стиле? Я также попытался использовать Seq.unfold, чтобы создать последовательность значений, а затем передать полученную последовательность в Seq.sum, но это оказалось еще сложнее, чем моя рекурсивная версия.

Ответы [ 2 ]

6 голосов
/ 05 марта 2012

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

for increment_index in {1..4} do 
  current <- current + increment 
  total <- total + current

Вы не используете increment_index для чего-либо, поэтому вы можете просто умножить increment и currentна четыре и получите тот же результат: 

total <- total + 4*current + 10*increment
current <- current + 4*increment

Тогда вашим императивным решением станет: 

let mutable total = 0 
let mutable increment = 2 
let mutable current = 1 

for spiral_layer_index in {1..(dimensions- 1) / 2} do 
  total <- total + 4*current + 10*increment
  current <- current + 4*increment
  increment <- increment + 2 
total

Если переписать это в рекурсивную функцию, оно станет просто: 

let rec loop index (total, current, increment) = 
  if index > (dimensions - 1) / 2 then total 
  else loop (index + 1) ( total + 4*current + 10*increment,
                          current + 4*increment, increment + 2 )
let total = loop 1 (0, 2, 1)

То же самое можно было бы написать, используя Seq.fold, как это (это еще более «функционально», потому что в функциональном программировании вы используете рекурсию только для реализации базовых функций, таких как fold, которые затем могут быть повторноб): 

let total, _, _=
  {1 .. (dimensions - 1) / 2} |> Seq.fold (fun (total, current, increment) _ ->
    (total + 4*current + 10*increment, current + 4 * increment, increment + 2)) (0, 1, 2)

ПРИМЕЧАНИЕ: я не уверен, что это действительно реализует то, что вы хотите.Это просто упрощение вашего императивного решения, а затем переписать его с помощью рекурсивной функции ...

3 голосов
/ 05 марта 2012

На самом деле это Project Euler Problem 28 и my F # решение около 21 ноября 2011 г. очень похоже на то, что было предложено в ответе Томаса: 

let problem028 () =
    [1..500]
    |> List.fold (fun (accum, last) n ->
            (accum + 4*last + 20*n, last + 8*n)) (1,1)
    |> fst

Действительно, решение исходной задачи занимает всего одну строчку fold по списку всех задействованных квадратов с углами в диагональных узлах, пронизывая накопленную сумму и значение текущего диагонального элемента. Складывание - одна из основных фраз функционального программирования; есть классическая классическая статья Учебное пособие по универсальности и выразительности сгиба , которая охватывает многие важные аспекты этой базовой модели.

...