F# — вернуть элемент из последовательности

Осторожно, спойлеры! Вы увидите решение для projecteuler.net-Problem 7.

Извините, если это дубликат, но я не смог найти здесь вопрос, задающий то же самое.

Я вычисляю последовательность чисел в функции и хочу вернуть n-е число.

let isPrime x = 
    {2..x/2}
    |> Seq.exists (fun e -> x%e=0)
    |> not

let PrimeNumber nth = 
    let unfolder a =
        a
        |> Seq.unfold (fun e -> Some(e, e+1))
        |> Seq.find isPrime
        |> fun e -> Some(e, e)

    2
    |> Seq.unfold unfolder
    |> Seq.skip (nth-1) 
    |> Seq.head

let ans = PrimeNumber 10001

ans всегда будет 2, но почему?

Когда я оцениваю последнее выражение в PrimeNumber с помощью nth=10001, возвращается правильный элемент. Я что-то упускаю?


f# seq
person itmuckel    schedule 10.05.2016    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Проблема заключается в использовании вами Seq.find.

Seq.find из документации возвращает первый элемент, для которого условие истинно. В данном случае это 2.

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

Чтобы увидеть это, запустите только этот фрагмент кода:

2
|> Seq.unfold unfolder

//output: val it : seq<int> = seq [2; 2; 2; 2; ...]
person Pash101    schedule 10.05.2016
comment
Изменение |> fun e -> Some(e, e) на |> fun e -> Some(e, e+1) исправило это. Спасибо за подсказку. После перезапуска Visual Studio он не нашел правильного решения. Я не знаю, почему это работало раньше. - person itmuckel; 10.05.2016
comment
@Micha90 : Пересмотрите e+1 - это будет бессмысленно проверять каждое четное число. - person ildjarn; 10.05.2016
comment
Что ты посоветуешь? e+2 пропускает 3 как простое, когда я начинаю с 2. Также это дает неправильное решение, nth+1 простое число. И он не работает быстрее, но я не понимаю, почему. Я ожидал, что он будет работать примерно в два раза быстрее. - person itmuckel; 10.05.2016
comment
@ Micha90: начните с 3 и вручную введите 2 в начало последовательности; например 2 |> Seq.unfold unfolder |> Seq.skip (nth-1) становится 3 |> Seq.unfold unfolder |> Seq.append (Seq.singleton 2) |> Seq.skip (nth-1). - person ildjarn; 10.05.2016

arrow_upward
2
arrow_downward

Вам нужен Seq.filter, если вам нужно придерживаться этого решения:

let isPrime x = 
{2..x/2}
|> Seq.exists (fun e -> x%e=0)
|> not

let PrimeNumber nth = 
    let unfolder a =
       a
       |> Seq.unfold (fun e -> Some(e, e+1))
       |> Seq.filter isPrime

    2
    |> unfolder
    |> Seq.skip (nth-1) 
    |> Seq.item 0

let ans = PrimeNumber 100 даст вам 541 Но, как ускользнуло в комментариях, есть и другие более эффективные решения.

person s952163    schedule 10.05.2016