7

I am looking for a way to create a sequence consisting of every nth element of another sequence, but don't seem to find a way to do that in an elegant way. I can of course hack something, but I wonder if there is a library function that I'm not seeing.

The sequence functions whose names end in -i seem to be quite good for the purpose of figuring out when an element is the nth one or (multiple of n)th one, but I can only see iteri and mapi, none of which really lends itself to the task.

Example:

let someseq = [1;2;3;4;5;6]
let partial = Seq.magicfunction 3 someseq

Then partial should be [3;6]. Is there anything like it out there?

Edit:

If I am not quite as ambitious and allow for the n to be constant/known, then I've just found that the following should work:

let rec thirds lst =
    match lst with
    | _::_::x::t -> x::thirds t // corrected after Tomas' comment
    | _ -> []

Would there be a way to write this shorter?

Alexander Rautenberg
  • 2,205
  • 2
  • 22
  • 20
  • 3
    You could use `mapi` to turn each element of the list into a `Some` or a `None`, `filter` out the `None`s, and then `map` them back to the undecorated type again. – Anon. Jan 13 '11 at 03:36
  • Your solution using lists looks good (but you probably wanted to write `_::_::x::t` (instead of `(_, _, x)::t` which uses list of tuples). The difference is that `Seq` will work with other collections than lists, but that may not be a problem for you. Your version with lists is a nice functional code. – Tomas Petricek Jan 13 '11 at 03:52
  • Yes, of course, it must be `_::_::x::t`, should have asked the compiler before pasting it in here. – Alexander Rautenberg Jan 13 '11 at 03:55
  • Still wondering what the optimally efficient solution would be for the general case, but for my problem at hand I am going with the pattern matching now. Thanks for taking the time to answer this. – Alexander Rautenberg Jan 13 '11 at 04:00

2 Answers2

10

Seq.choose works nicely in these situations because it allows you do the filter work within the mapi lambda.

let everyNth n elements =
    elements
    |> Seq.mapi (fun i e -> if i % n = n - 1 then Some(e) else None)
    |> Seq.choose id

Similar to here.

Community
  • 1
  • 1
Stephen Swensen
  • 22,107
  • 9
  • 81
  • 136
8

You can get the behavior by composing mapi with other functions:

let everyNth n seq = 
  seq |> Seq.mapi (fun i el -> el, i)              // Add index to element
      |> Seq.filter (fun (el, i) -> i % n = n - 1) // Take every nth element
      |> Seq.map fst                               // Drop index from the result

The solution using options and choose as suggested by Annon would use only two functions, but the body of the first one would be slightly more complicated (but the principle is essentially the same).

A more efficient version using the IEnumerator object directly isn't too difficult to write:

let everyNth n (input:seq<_>) = 
  seq { use en = input.GetEnumerator()
        // Call MoveNext at most 'n' times (or return false earlier)
        let rec nextN n = 
          if n = 0 then true
          else en.MoveNext() && (nextN (n - 1)) 
        // While we can move n elements forward...
        while nextN n do
          // Retrun each nth element
          yield en.Current }

EDIT: The snippet is also available here: http://fssnip.net/1R

Tomas Petricek
  • 240,744
  • 19
  • 378
  • 553
  • Don't know who was faster, you or 'Anon.', but it's both the same suggestion, isn't it? It doesn't look horribly efficient, though, does it? – Alexander Rautenberg Jan 13 '11 at 03:40
  • It isn't horribly efficient (there are some additional function calls and indirections, because it uses 3 iterators under the cover), but it may not be too bad (there are no intermediate lists that would have to be allocated). For a more efficient version, you'll either need mutation (in sequence expression) or use the underlying `IEnumerator` – Tomas Petricek Jan 13 '11 at 03:45