хвостовая рекурсивная/эффективная функция для подсчета элементов списка (без использования List.count/Seq.count)

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

lstcountr [1..98765432];;

Я получаю это:

System.OutOfMemoryException: возникло исключение типа «System.OutOfMemoryException».

это моя функция (которую я считал хвостовой рекурсией/эффективной):

let lstcountr ls =
    let rec loop ls total = 
        match ls with
        | [] -> total
        | hd::tl -> loop tl total+1I
    loop ls 0I

это можно сделать лучше?


f# tail-recursion
person Omu    schedule 25.04.2012    source источник
comment
Версия с использованием seq<_> может выглядеть примерно так: let count = Seq.fold (fun i _ -> i + 1I) 0I   -  person Daniel    schedule 25.04.2012
comment
@ Даниэль, ты должен был опубликовать это как ответ.   -  person Onorio Catenacci    schedule 25.04.2012
comment
Раньше я действительно беспокоился о рекурсивных функциях, но, обнаружив, что вы можете делать то же самое со сгибами (как указывает @Daniel выше), я никогда не беспокоюсь об этом. Складки намного проще в использовании, и я считаю, что хвостовая рекурсия в значительной степени встроена.   -  person Onorio Catenacci    schedule 25.04.2012

Ответы (3)


arrow_upward
8
arrow_downward

Ваша функция не является хвостовой рекурсией.

| hd::tl -> loop tl total+1I

Должно быть

| hd::tl -> loop tl (total+1I)

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

Кроме того, как сказал Тейс, вы создаете список из слишком большого количества элементов, что вызывает ваш OutOfMemoryException. Вы пробовали использовать seq { }?

person Guvante    schedule 25.04.2012
comment
Хороший улов о расчете (всего + 1I). Действительно тонкий момент. - person Onorio Catenacci; 25.04.2012

arrow_upward
5
arrow_downward

Слишком много рекурсии будет означать, что вы получите StackOverflowException, а не OutOfMemoryException - это потому, что вы пытаетесь создать список из 98765432 элементов одновременно.

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

person Tejs    schedule 25.04.2012
comment
хорошо, я попытался сделать это отдельно, и список был составлен (это занимает некоторое время), и после того, как я попытался подсчитать его, я получил StackOverflowException, так что он все еще не работает, я думаю, что в любом случае это слишком много рекурсии - person Omu; 25.04.2012

arrow_upward
2
arrow_downward

Вот два способа написания основанной на последовательности версии, полиморфной по возвращаемому типу:

module Seq =
  open LanguagePrimitives

  let inline count items = Seq.fold (fun i _ -> i + GenericOne) GenericZero items

  //faster
  let inline count (items: seq<_>) =
    use e = items.GetEnumerator()
    let rec loop n =
      if e.MoveNext() then loop (n + GenericOne)
      else n
    loop GenericZero

Это позволяет вам вычислять длину, используя наиболее подходящий тип:

let n : bigint = Seq.count {1I .. 987298234982374923847I}
let n : float = Seq.count {1I .. 987298234982374923847I}
person Daniel    schedule 25.04.2012