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

Question

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

let newRes = curr :: res - small improvement – Lasse Espeholt Aug 17 '10 at 14:36 — Lasse Espeholt, Aug 17 '10 at 14:36

score 3 · Accepted Answer · edited May 23 '17 at 12:13

3

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

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.

edited May 23 '17 at 12:13

Community

1
1

answered Aug 17 '10 at 14:25

Brian

117,631
17
236
300

thank you Brian. Not planning to use this list in real life :) , just tried to make a simple example of something I am trying to get done. (I ll change the size of the seq so that things are more reasonable) – jlezard Aug 17 '10 at 14:33
1

Well, now I presume your question about StackOverflow makes no sense. :) – Brian Aug 17 '10 at 14:39
arrg, you tricked me there !!! , I've reversed the change to something that is just big enough to overflow and yet reasonable :) – jlezard Aug 17 '10 at 14:43

score 1 · Answer 2 · edited May 23 '17 at 12:19

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

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

Thank you for your comment. Still wondering about the stack overflow why is it happening ? — jlezard, Aug 17 '10 at 14:10
I can't help you with that. I'm a novice when it comes to F#. — Lasse Espeholt, Aug 17 '10 at 14:14
@jlezard I think lassespeholt is actually on the track to the stack overflow. If Seq.skip is creating a new enumerable each time as suggested, by the time you reach the end of the sequence, the `s` parameter to `copy` is a very deeply nested IEnumerable object and the chained call to MoveNext is probably what is overflowing. — Gideon Engelberth, Aug 17 '10 at 16:30

score 1 · Answer 3 · answered Aug 17 '10 at 15:13

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.

JaredPar · Answer 4 · 2010-08-17T14:55:40.243

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"

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

4 Answers4