Хвост рекурсивной копии последовательности в список в F # - PullRequest
Новая
       2

Хвост рекурсивной копии последовательности в список в F #

2 голосов
/ 17 августа 2010

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

open System


let s = seq[for i in 2..4350 -> i,2*i]

let rec copy s res = 
     if  (s|>Seq.isEmpty)  then 
         res
     else
         let (a,b) = s |> Seq.head
         Console.WriteLine(string a)
         let newS = s |> Seq.skip(1)|> Seq.cache
         let newRes = List.append res ([(a,b)])
         copy newS newRes



copy s ([])

Две проблемы:

. получая переполнение стека, что означает, что мой хвост рецидив уловка

и

. почему код в 100 раз быстрее, когда я ставлю |> Seq.cache здесь let newS = s |> Seq.skip(1)|> Seq.cache.

(Обратите внимание, что это всего лишь небольшое упражнение, я понимаю, что вы можете выполнять Seq.toList и т. Д.) *

Большое спасибо

Один из способов это работает (эти две точки все еще остаются немного странными для меня): 

let toList (s:seq<_>) =

    let rec copyRev res (enum:Collections.Generic.IEnumerator<_*_>) = 
         let somethingLeft = enum.MoveNext()
         if  not(somethingLeft)  then 
             res
         else
             let curr = enum.Current
             Console.WriteLine(string curr)
             let newRes = curr::res
             copyRev newRes enum

    let enumerator = s.GetEnumerator()
    (copyRev ([]) (enumerator)) |>List.rev

Ответы [ 4 ]

3 голосов
/ 17 августа 2010

Вы говорите, что это просто упражнение, но полезно указать на мой ответ на

Хотя или хвостовой рекурсии в F #, что использовать, когда?

и повторяем, что вам следует отдавать предпочтение более аппликативным / декларативным конструкциям, когда это возможно Э.Г. 

let rec copy2 s = [
    for tuple in s do
        System.Console.WriteLine(string(fst tuple))
        yield tuple
    ]

- это хороший и эффективный способ выразить вашу конкретную функцию.

Тем не менее, я бы почувствовал себя упущенным, если бы не сказал "никогда не создавайте такой большой список". Для больших данных вам нужен либо массив, либо последовательность.

1 голос
/ 17 августа 2010

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

let mutable s = seq { 1 .. 20001 }
for i in 1 .. 20000 do
  s <- Seq.skip 1 s
let v = Seq.head s

Возможно, вы видите расплывчатую связь с вашим собственным кодом, который также в конечном итоге берет на себя заголовок последовательности, что является результатом неоднократного применения Seq.skip 1 к вашей исходной последовательности.

1 голос
/ 17 августа 2010

По моему короткому опыту работы с F # не очень хорошая идея использовать Seq.skip 1, как если бы вы использовали списки с tail Seq.skip создает новый IEnumerable/sequence, а не просто пропускает n. Поэтому ваша функция будет НАМНОГО медленнее, чем List.toSeq. Вы должны правильно сделать это обязательно с 

s.GetEnumerator()

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

В этом вопросе

Взять N элементов из последовательности с N различными индексами в F #

Я начал делать что-то похожее на то, что вы делаете, но обнаружил, что это очень медленно. Смотрите мой метод для вдохновения, как это сделать.

Дополнение: Я написал это: 

let seqToList (xs : seq<'a>) =
    let e = xs.GetEnumerator()
    let mutable res = []

    while e.MoveNext() do
        res <- e.Current :: res

    List.rev res

И обнаружил, что метод встроенного интерфейса на самом деле делает нечто очень похожее (включая обратную часть). Однако он проверяет, является ли предоставленная вами последовательность на самом деле списком или массивом.

Вы сможете сделать код полностью функциональным: (что я и сделал сейчас - не смог устоять; -)) 

let seqToList (xs : seq<'a>) =
        Seq.fold (fun state t -> t :: state) [] xs |> List.rev
0 голосов
/ 17 августа 2010

Попробуйте следующий код.

Предупреждение. Перед запуском этого кода необходимо включить генерацию хвостовых вызовов в Visual Studio. Это можно сделать с помощью вкладки «Сборка» на странице свойств проекта. Если это не включено, код будет StackOverflow обрабатывать продолжение. 

open System
open System.Collections.Generic

    let s = seq[for i in 2..1000000 -> i,2*i]

    let rec copy (s : (int * int) seq) = 
        use e = s.GetEnumerator()
        let rec inner cont =
            if e.MoveNext() then 
                let (a,b) = e.Current
                printfn "%d" b
                inner (fun l -> cont (b :: l))
            else cont []
        inner (fun x -> x)

    let res = copy s 
    printfn "Done"
...