Tail recursive copy of a seq to a list in F#

Question

Hello,

I am trying to build a list from a sequence by recursively appending the first element of the sequence to the list:

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 ([])

Two problems:

. getting a Stack overflow which means my tail recusive ploy sucks

and

. why is the code 100x faster when I put |> Seq.cache here let newS = s |> Seq.skip(1)|> Seq.cache.

(Note this is just a little exercise, I understand you can do Seq.toList etc.. )

Thanks a lot

One way that works is ( the two points still remain a bit weird to me ):

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

Answer 1

In my short experience with F# it is not a good idea to use Seq.skip 1 like you would with lists with tail. Seq.skip creates a new IEnumerable/sequence and not just skips n. Therefore your function will be A LOT slower than List.toSeq. You should properly do it imperative with

s.GetEnumerator()

and iterates through the sequence and hold a list which you cons every single element.

In this question

http://stackoverflow.com/questions/3323088/take-n-elements-from-sequence-with-n-different-indexes-in-f

I started to do something similar to what you do but found out it is very slow. See my method for inspiration for how to do it.

Addition: I have written this:

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

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

    List.rev res

And found out that the build in method actually does something very similar (including the reverse part). It do, however, checks whether the sequence you have supplied is in fact a list or an array.

You will be able to make the code entirely functional: (which I also did now - could'nt resist ;-))

let seqToList (xs : seq<'a>) =
        Seq.fold (fun state t -> t :: state) [] xs |> List.rev

Answer 2

Try the following code.

Warning: Before running this code you will need to enable tail call generation in Visual Studio. This can be done through the Build tab on the project properties page. If this is not enabled the code will StackOverflow processing the continuation.

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"

Answer 3

You say it's just an exercise, but it's useful to point to my answer to

http://stackoverflow.com/questions/1797241/while-or-tail-recursion-in-f-what-to-use-when

and reiterate that you should favor more applicative/declarative constructs when possible. E.g.

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

is a nice and performant way to express your particular function.

That said, I'd feel remiss if I didn't also say "never create a list that big". For huge data, you want either array or seq.

Answer 4

Your function is properly tail recursive, so the recursive calls themselves are not what is overflowing the stack. Instead, the problem is that Seq.skip is poorly behaved when used recursively, as others have pointed out. For instance, this code overflows the stack on my machine:

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

Perhaps you can see the vague connection to your own code, which also eventually takes the head of a sequence which results from repeatedly applying Seq.skip 1 to your initial sequence.