从F#中的N个不同索引的序列中取N个元素

Question

我是F#的新手,正在寻找一个能够获取N*个索引和一个序列并给出N个元素的函数.如果我有N个索引它应该等于concat Seq.nth index0,Seq.nth index1 .. Seq.nth indexN但它应该只扫描序列中的indexN元素(O(N))而不是index0 + index1 + .. .+ indexN(O(N ^ 2)).

总结一下,我正在寻找类似的东西:

//For performance, the index-list should be ordered on input, be padding between elements instead of indexes or be ordered when entering the function
seq {10 .. 20} |> Seq.takeIndexes [0;5;10] 
Result: 10,15,20

我可以通过使用seq {yield ...}并使用一个索引计数器来勾选一些元素应该被传递掉但是如果F#提供了一个很好的标准方法我宁愿使用它.

谢谢 :)...

另外:我做了以下几点.它有效,但不漂亮.欢迎提出建议

let seqTakeIndexes (indexes : int list) (xs : seq<int>) =
    seq {
        //Assume indexes is sorted
        let e = xs.GetEnumerator()
        let i = ref indexes 
        let curr = ref 0

        while e.MoveNext() && not (!i).IsEmpty do
            if !curr = List.head !i then
                i := (!i).Tail
                yield e.Current

            curr := !curr + 1
    }

Answer 1

如果要按索引访问元素,那么使用序列并不是一个好主意.序列旨在允许顺序迭代.我会将序列的必要部分转换为数组,然后按索引选择元素:

let takeIndexes ns input = 
  // Take only elements that we need to access (sequence could be infinite)
  let arr = input |> Seq.take (1 + Seq.max ns) |> Array.ofSeq
  // Simply pick elements at the specified indices from the array
  seq { for index in ns -> arr.[index] }

seq [10 .. 20] |> takeIndexes [0;5;10]  

关于你的实现 - 我认为它不会变得更加优雅.当实现需要以交错方式从多个源获取值的函数时,这是一个普遍问题 - 没有优雅的方法来编写它们!

但是,你可以使用这样的递归以函数方式编写它:

let takeIndexes indices (xs:seq<int>) = 
  // Iterates over the list of indices recursively
  let rec loop (xe:IEnumerator<_>) idx indices = seq {
    let next = loop xe (idx + 1)
    // If the sequence ends, then end as well
    if xe.MoveNext() then
      match indices with
      | i::indices when idx = i -> 
        // We're passing the specified index 
        yield xe.Current
        yield! next indices
      | _ -> 
        // Keep waiting for the first index from the list
        yield! next indices }
  seq {
    // Note: 'use' guarantees proper disposal of the source sequence
    use xe = xs.GetEnumerator()
    yield! loop xe 0 indices }

seq [10 .. 20] |> takeIndexes [0;5;10]