Произведите код F # для хвостовой рекурсии

Question

Я пишу код для изучения F #. Вот пример:

let nextPrime list=
    let rec loop n=
        match n with
        | _ when (list |> List.filter (fun x -> x <= ( n |> double |> sqrt |> int)) |> List.forall (fun x -> n % x <> 0)) -> n
        | _ -> loop (n+1)
    loop (List.max list + 1)

let rec findPrimes num=
    match num with
    | 1 -> [2]
    | n -> 
        let temp = findPrimes <| n-1
        (nextPrime temp ) :: temp

//find 10 primes
findPrimes 10 |> printfn "%A"

Я очень рад, что это просто работает!

Я полностью новичок в рекурсии

Рекурсия - замечательная вещь.

Я думаю findPrimes не эффективен.

Кто-то помог мне реорганизовать findPrimes для хвостовой рекурсии , если возможно?

Кстати, есть ли более эффективный способ найти первые n простых чисел ?

Answer 1

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

let findPrimesTailRecursive num =
    let rec aux acc num = 
        match num with
        | 1 -> acc
        | n -> aux ((nextPrime acc)::acc) (n-1)
    aux [2] num

Рекурсивная функция aux собирает свои результаты в дополнительный параметр, обычно называемый acc (как в acc-umulator). Когда вы достигнете конечного состояния, просто выплюните накопленный результат. Я включил хвостовую рекурсивную вспомогательную функцию в другую функцию, поэтому сигнатура функции остается прежней.

Как видите, вызов aux является единственным и, следовательно, последним вызовом, который должен произойти в случае n <> 1. Теперь он хвостовой рекурсивен и скомпилируется в цикл while.

Я рассчитал вашу версию и мою, генерируя 2000 простых чисел. Моя версия на 16% быстрее, но все еще довольно медленная. Для генерации простых чисел мне нравится использовать массив решет. Не очень функционально, но очень (очень) быстро.

Answer 2

Альтернативой является использование дополнительного аргумента продолжения, чтобы сделать хвост findPrimes рекурсивным. Эта техника всегда работает. Это позволит избежать переполнения стека, но, вероятно, не сделает ваш код быстрее.

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

let nextPrime list=
    let rec loop n = if list |> List.filter (fun x -> x*x <= n) 
                             |> List.forall (fun x -> n % x <> 0) 
                     then n
                     else loop (n+1)
    loop (1 + List.head list)

let rec findPrimesC num cont =
        match num with
        | 1 -> cont [2]
        | n -> findPrimesC (n-1) (fun temp -> nextPrime temp :: temp |> cont)

let findPrimes num = findPrimesC num (fun res -> res)        
findPrimes 10

Как уже говорили другие, есть более быстрые способы генерирования простых чисел.

Answer 3

Почему бы просто не написать:

let isPrime n =
    if n<=1 then false
    else
        let m = int(sqrt (float(n)))
        {2..m} |> Seq.forall (fun i->n%i<>0)

let findPrimes n = 
    {2..n} |> Seq.filter isPrime |> Seq.toList

или сито (очень быстрое):

let generatePrimes max=
    let p = Array.create (max+1) true
    let rec filter i step = 
        if i <= max then 
            p.[i] <- false
            filter (i+step) step
    {2..int (sqrt (float max))} |> Seq.iter (fun i->filter (i+i) i) 
    {2..max} |> Seq.filter (fun i->p.[i]) |> Seq.toArray

Answer 4

Я знаю, что уже немного поздно, и ответ уже принят. Тем не менее, я считаю, что хорошее пошаговое руководство по созданию чего-то рекурсивного может быть интересным для ОП или кого-либо еще в этом отношении. Вот несколько советов, которые, безусловно, помогли мне. Я собираюсь использовать прямой пример, отличный от простого поколения, потому что, как утверждали другие, есть более эффективные способы генерирования простых чисел.

Рассмотрим наивную реализацию функции count, которая создаст список целых чисел, отсчитывающих от некоторого n. Эта версия не является хвостовой рекурсией, поэтому для длинных списков вы встретите исключение переполнения стека:

let rec countDown = function
  | 0 -> []
  | n -> n :: countDown (n - 1)
(*         ^
           |... the cons operator is in the tail position
                as such it is evaluated last.  this drags
                stack frames through subsequent recursive
                calls *)

Один из способов исправить это - применить стиль передачи продолжения с параметризованной функцией:

let countDown' n =
  let rec countDown n k =
    match n with
    | 0 -> k [] (*            v--- this is continuation passing style *)
    | n -> countDown (n - 1) (fun ns -> n :: k ns)
(*          ^
            |... the recursive call is now in tail position *)
  countDown n (fun ns -> ns) 
(*              ^
                |... and we initialize k with the identity function *)

Затем преобразуйте эту параметризованную функцию в специализированное представление. Обратите внимание, что функция countDown' на самом деле не ведет обратный отсчет. Это артефакт способа построения продолжения при n > 0, а затем оценки при n = 0. Если у вас есть что-то похожее на первый пример, и вы не можете понять, как сделать его рекурсивным, я предлагаю вам написать второй, а затем попытаться оптимизировать его, чтобы исключить параметр функции k. Это, безусловно, улучшит читабельность. Это оптимизация второго примера:

let countDown'' n =
  let rec countDown n ns =
    match n with
    | 0 -> List.rev ns  (* reverse so we are actually counting down again *)
    | n -> countDown (n - 1) (n :: ns)
  countDown n []

Answer 5

Кстати, есть ли более эффективный способ найти первые n простых чисел?

Я описал быстрое сито эратосфена произвольного размера в F # здесь , которое накапливало свои результаты в постоянно растущем ResizeArray:

> let primes =
    let a = ResizeArray[2]
    let grow() =
      let p0 = a.[a.Count-1]+1
      let b = Array.create p0 true
      for di in a do
        let rec loop i =
          if i<b.Length then
            b.[i] <- false
            loop(i+di)
        let i0 = p0/di*di
        loop(if i0<p0 then i0+di-p0 else i0-p0)
      for i=0 to b.Length-1 do
        if b.[i] then a.Add(p0+i)
    fun n ->
      while n >= a.Count do
        grow()
      a.[n];;
val primes : (int -> int)