The Author Online Book Forums are Moving

The Author Online Book Forums will soon redirect to Manning's liveBook and liveVideo. All book forum content will migrate to liveBook's discussion forum and all video forum content will migrate to liveVideo. Log in to liveBook or liveVideo with your Manning credentials to join the discussion!

Thank you for your engagement in the AoF over the years! We look forward to offering you a more enhanced forum experience.

tempusfugit (144) [Avatar] Offline
#1
12.2.2 Using infinite sequences: "Infinite lists in Haskell and sequence caching in F#" p.331 (Question)

[pre]let rec nums =
seq { yield 1
for n in nums do yield n + 1 } |> Seq.cache
[/pre]
behaving like Haskell's
[pre]
let nums = 1 : [ n + 1 | n <- nums ]
[/pre]
is interesting however being within the F# environment wouldn't one tend to go with something like
[pre]
let nums =
let rec nseq n = seq { yield n; yield! nseq (n + 1) }
nseq 1
[/pre]
(based on the factorial example)?

Also the internal workings of that "recursive for" may require some additional explanation. I can come up with two implementation scenarios - neither of which could benefit from the application of Seq.cache - therefore those "implementation scenarios" must be wrong.

Scenario 1: "n" is simply an alias for "Current" of "nums". In that case there shouldn't be a performance issue and Seq.cache would be unnecessary.

Scenario 2: Each generated sequence element for the top level sequence results in a new sequence at the deepest recursion level. This may make it clearer:

elem0: seq0(1)
elem1: seq0(2)<-seq1(1)
elem2: seq0(3)<-seq1(2)<-seq2(1)
elem3: seq0(4)<-seq1(3)<-seq2(2)<-seq3(1)
..
elemN: seq0(m)<-seq1(m-1)<-...<-seqN(1)

If this was the case, caching the seq0 values (which is all Seq.cache should conceivably have access to) wouldn't help because you need to create seqN to advance all seq"i<N" in order to determine elemN - in other words, the next seq0 value doesn't depend on the previous seq0 value but the next seq1 value (and so on). >

So what is actually going on?
tempusfugit (144) [Avatar] Offline
#2
Re: 12.2.2 Using infinite sequences: "sequence caching in F#" p.331 (Question)
The uncached version seems to crank through a new IEnumerator each time the "Next" element in the sequence is accessed. To me at least this type of behavior isn't evident from the syntax of
[pre]
let rec nums =
seq { yield 1
for n in nums do yield n + 1 }
[/pre]
Should the behavior be apparent from the plain code or is this some kind of implementation behavior that is necessary for something like thread safety - which Seq.cache can take responsibility for once it is "wrapped around" the sequence?
Tomas Petricek (160) [Avatar] Offline
#3
Re: 12.2.2 Using infinite sequences: "sequence caching in F#" p.331 (Question)
Hi,
First of all, your version of the code for generating nunmbers (based on the factorial example) is better option than the code used in the sidebar. Caching is more a workaround for situations when you can't write it more nicely (but I don't think it's used very often).

Regarding the internal workings of "nums" - the important thing is that seq<'a> type is the IEnumerable<T> type (and not IEnumerator<T>smilie. This means that when we work with it, we always have to ask it to start generating elements one by one from the beginning. So, when you start pulling elements from "nums", it yields 1 and then gets elements from "nums" again.

Now, if we don't use Seq.cache, then the "for" loop simply re-evaluates "nums" starting from the first element (so we're creating a chain of sequences that reference each other and each new element adds one sequence). When we use "cache", then the "nums" sequence contains a list of already generated elements. When we start reading elements from it (we still have to create a new IEnumerator to do that), it first returns all already generated elements. If we ran out of elements, it would generate more using the code in sequence expression. That doesn't happen in the case here, because before we need Nth element, we're already generating N+1th element.

I hope this helps at least a little bit - understanding this kind of code in F# can be really difficult, because there are quite a lot of hidden side-effects. I'll add a note that this is example only for curiosity and that a version implemented like yours (based on factorial sample) would be more idiomatic and better F#.

Thanks for the feedback!
Tomas