Back to Questions
841
views4
comments
Must sequences be traversed in order?
f#

I am unclear as to whether sequences must be traversed in order.

For example, suppose you want you want to zero-out every nth item in a sequence.  My first attempt at this was:

1
2
3
4
5
6
7
8
9
10

let rec everynthzero n ss = seq { 

  yield! (Seq.take (n-1) ss)

  yield 0

  yield! everynthzero n (Seq.skip n ss)

}

which can be tested on 

1

everynthzero 2 {1..10}

.

What troubles me about this is even before it recurses, the Seq.take and the Seq.skip restart the sequence. Is this good practice? For example, what happens if the sequence is backed by a file?

Motivated by these concerns I rewrote it as

1
2
3
4
5
6
7
8
9
10
11
12

let rec skipper x n = seq { 

  for _ in 2..n do yield id

  yield (fun _ -> x)

  yield! skipper x n

}

let everynthzero2 n ss = Seq.map2 (|>) ss (skipper 0 n)

Is this any better?

Thanks,

Luis

[EDIT: Improved formatting]

.

This doesn't answer your question about restarting a sequence (Brian's answered that), but it does solve the code problem....

1
2

let ZeroEveryNth n s =
   s |> Seq.mapi (fun i x -> if (i + 1) % n = 0 then 0 else x)

Seq.mapi and iteri are available for processing a sequence via a numerical index.

By on 10/27/2009 8:07 PM ()

I would say that is it <i>not <i>good practice to restart the sequence. (In general, if you are using Seq.skip, it is very likely that you are doing something bad.) How about <code lang=fsharp>let ZeroEveryNth n s = seq { let i = ref 0 for x in s do incr i if !i % n = 0 then yield 0 else yield x } [1..10] |> ZeroEveryNth 3 |> Seq.iter (printfn "%d") </code>

By on 10/26/2009 4:25 PM ()

Thanks Brian.

I was wondering whether my skipper is tail recursive. It looks it (although I'm less certain with yields instead of returns) and empirically (

1

List.of_seq (everynthzero2 2 {1..1000000})

) it is. Any comments on this?

Thanks,

Luis

By on 10/27/2009 7:26 AM ()

Yes, it must be, given the empirical evidence. I also note that e.g. adding "ignore ()" after the yield! line does cause a StackOverflow, which helps confirm that the test data size is big enough to give confidence that it would be StackOverflowing if not tail-recursive. You can always look the the generated IL to confirm. In general, roughly, if something is the last call (including yield! and return!), and it's not in a 'try', then it will be a tail call.

By on 10/27/2009 8:36 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper