Seq head and tail

3
votes

Is there a one-liner way to do implement nextLine?

let s = ref seqOfLines
let nextLine() =
  let hd = Seq.head !s
  s := Seq.skip 1 !s
  hd

seqOfLines is assumed to be infinite

3
f#
It is a really bad idea to use augmenting of sequences like s := Seq.skip 1 !s because it creates a new sequence object on top of the other, so your algorithm ends up in O(n^2). Correct me if I´m wrong. - Lasse Espeholt
Why do you want the nextLine function in the first place? Why not just iterate over the sequence you have which results in a pure function. You wouldn't even make this sort of thing in C#. If you insist on what you are doing, you should properly use s.GetEnumerator() and use that in your nextLine function. - Lasse Espeholt
You can look at the source code here: github.com/fsharp/fsharp/blob/master/src/fsharp/FSharp.Core/… It does create a new sequence, does a bunch of memory allocations, etc. Since you know you only want to move one step each time, you're best bet is to call MoveNext yourself. - Chris Smith
@Chris Smith Cool insight :) I can see you know a lot about F#, but can you tell me, why it is not just mappings to Enumerable.Skip etc.? instead of programming those twice. - Lasse Espeholt
@lasseespeholt Intentional design decision. Enumerable.Skip requires the .NET framework 3.5 or higher, which we didn't want to do for the first release of F#. Requiring a higher runtime makes installing it a pain in the ass, hurts adoption, etc. Taking a dependency on a 100MB redist isn't worth the cost of not reimplementing methods like Enumerable.Skip. (Once F# has been out a few years this might get revisited...) - Chris Smith

3 Answers

5
votes

One way to do this is to utilize the underlying IEnumerator<String>. It isn't quite a one-liner, but it appears to be a bit cleaner than the implementation you have. (Doesn't rely on mutable, properly uses the .NET idioms.)

Essentially you get the IEnumerator<'a> interface from the sequence, and then just loop on calling MoveNext. This will work fine on an infinite sequence.

> let getNextFunc (seqOfLines : seq<'a>) =               
-     let linesIE : IEnumerator<'a> = seqOfLines.GetEnumerator()
-     (fun () -> ignore (linesIE.MoveNext()); linesIE.Current);;

val getNextFunc : seq<'a> -> (unit -> 'a)

To use, just pass getNextFunc a sequence, and it will return your nextLine function.

> let sequenceOfStrings = seq { for i = 0 to 10000 do yield i.ToString() };;

val sequenceOfStrings : seq<string>

> let nextLine = getNextFunc sequenceOfStrings;;  

val nextLine : (unit -> string)

> nextLine();;
val it : string = "0"
> nextLine();;
val it : string = "1"
> nextLine();;
val it : string = "2"
> nextLine();;
val it : string = "3"
2
votes

Hmmm, I think you're trying to approach this too imperatively, and as a result, you're going to end up writing some funky code and losing the benefits of function programming.

You might benefit by re-writing your function so it takes current state and returns value * next state. This will keep your function purely functional. You also might find it easier to convert your infinite seq to a LazyList instead (you need to reference the F# PowerPack for this), so you don't have to touch the underlying enumerator directly:

> open LazyList
let seqOfLines = Seq.initInfinite (fun i -> i) |> LazyList.ofSeq
let nextLine = function Cons(x, xs) -> x, xs | Nil -> failwith "Empty list";;

val seqOfLines : LazyList<int>
val nextLine : LazyList<'a> -> 'a * LazyList<'a>

> nextLine seqOfLines;;
val it : int * LazyList<int> = (0, seq [1; 2; 3; 4; ...])
> nextLine (snd it);;
val it : int * LazyList<int> = (1, seq [2; 3; 4; 5; ...])
> nextLine (snd it);;
val it : int * LazyList<int> = (2, seq [3; 4; 5; 6; ...])
> nextLine (snd it);;
val it : int * LazyList<int> = (3, seq [4; 5; 6; 7; ...])
1
votes

FSharpx.Collections has some useful/efficient functions such as Seq.tail, Seq.Head and Seq.UnCons that might be useful if you want to decompose a Seq into head and tail.