Rfactor this F # code to tail recursion

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 не эффективен.

Кто-нибудь поможет мне найти рефератРаспечатать до хвост рекурсии если возможно?

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

Answer 1

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

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

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

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

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

Answer 2

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

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 3

Альтернативой является использование дополнительного аргумента продолжения, чтобы сделать 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 4

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

я описал быструю произвольную величину решета Эратосфена в F # here что накопленная свои результаты в постоянно растущую 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) 

Answer 5

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

Рассмотрите наивную реализацию функции 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 []