Преобразование цикла в чистые функции

Question

У меня есть этот код, написанный для Project Euler проблемы в c ++:

int sum = 0;

for(int i =0; i < 1000; i++)
{
    //Check if multiple of 3 but not multiple of 5 to prevent duplicate
    sum += i % 3 == 0 && i % 5 != 0 ? i: 0;
    //check for all multiple of 5, including those of 3
    sum += i % 5 == 0 ? i: 0;
}
    cout << sum;

Я пытаюсь выучить f# и переписываю это в f#. Это то, что я до сих пор:

open System

//function to calculate the multiples
let multiple3v5 num =
    num

//function to calculate sum of list items
let rec SumList xs =
    match xs with
    | []    -> 0
    | y::ys -> y + SumList ys

let sum = Array.map multiple3v5 [|1 .. 1000|]

Что у меня может быть полная чушь ... так что помогите пожалуйста?

Answer 1

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

Вот решение упрощенной задачи - добавьте все числа, которые делятся на 3:

open System

let rec sumList xs =
  match xs with
  | []    -> 0 // If the list is empty, the sum is zero
  | y::ys when y % 3 = 0 -> 
     // If the list starts with y that is divisible by 3, then we add 'y' to the
     // sum that we get by recursively processing the rest of the list
     y + sumList ys
  | y::ys -> 
     // This will only execute when y is not divisible by 3, so we just
     // recursively process the rest of the list and return 
     /// that (without adding current value)
     sumList ys

// For testing, let's sum all numbers divisble by 3 between 1 and 10.
let sum = sumList [ 1 .. 10 ]

Это основной способ написания функции с использованием явной рекурсии. На практике, решение jpalmer - это то же самое, что и я, но полезно написать несколько рекурсивных функций самостоятельно, если вы изучаете F #.

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

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

let rec sumList xs sumSoFar = ...

При первоначальном вызове вы пишете sumList [ ... ] 0. Рекурсивные вызовы не будут вызывать y + sumList xs, но вместо этого добавят y к аккумулятору и затем сделают рекурсивный вызов sumList xs (y + sumSoFar). Таким образом, компилятор F # может выполнять оптимизацию хвостового вызова и переводит код в цикл (аналогично версии C ++).

Answer 2

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

Общие задачи из Project Euler отлично подходят для освоения многих средств F #.Например, вы можете использовать списочные выражения, как в приведенном ниже фрагменте

// multipleOf3Or5 function definition is left for your exercise
let sumOfMultiples n =
    [ for x in 1 .. n do if multipleOf3Or5 x then yield x] |> List.sum
sumOfMultiples 999

, или вы можете немного обобщить решение, предложенное @jpalmer, используя лень:

Seq.initInfinite id
|> Seq.filter multipleOf3Or5
|> Seq.takeWhile ((>) 1000)
|> Seq.sum

или можетедаже используйте эту возможность для освоения активных шаблонов:

let (|DivisibleBy|_) divisior num = if num % divisor = 0 the Some(num) else None
{1..999}
|> Seq.map (fun i ->
    match i with | DivisibleBy 3 i -> i | DivisibleBy 5 i -> i | _ -> 0)
|> Seq.sum

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

Answer 3

F # имеет гораздо больше функций, чем просто карта - эта проблема предполагает использование фильтра и суммы, мой подход будет выглядеть примерно так:

let valid n = Left as an exercise

let r =
    [1..1000]
    |> List.filter valid
    |> List.sum
printfn "%i" r

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

Answer 4

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

Например:

let rec loop acc =
    if acc = 10 then
      printfn "endloop"
    else
      printfn "%d" acc
      loop (acc + 1)

loop 0

Это остановится, когда acc будет 10.