Back to Questions
1.7k
views2
comments
Reverse Sequence on an Array or List<T>
f#

Hi,
I was wondering if there's an efficient builtin method or composition of methods in F# to create a Seq<a> on top of an .NET Array of List<a> that will provide the elements in reverse. I'm sort of looking for something that is conceptually similar to List.rev only without copying and memory or creating temporary lists, but instead using in-place indexes / pointers, Ultimately it could also accept a "slice" or the array, so that if I have an array with 1000 elements I could have "slicing" operators that return a sequence: let ar = [|1..1000|] // This returns a sequence that traverses indexes 100 -> 200 in the ORIGINAL array let slice_forward = get_slice_from_array 100 200 // This return a sequence that traverses indexes 200 -> 100 in the ORIGINAL array let slice_forward = get_rev_slice_from_array 100 200 I hope I've made myself clear enough. I know that I can probably implement it myself somehow, I'm interested in seeing an efficient and succinct F# implementation...

.

Hi,
you can write this using sequences - this means that the sequence will iterate over the elements and it will return them one by one on demand:

1
2
3
4
5
6
7
8
9
10
11

let sliceFromArray fromIdx toIdx (arr:'a[]) =
  seq { for i in fromIdx .. toIdx do // iterate over elements
          yield arr.[ i ] };; // return a single elementotherwise)

let sliceFromArrayReverse fromIdx toIdx (arr:'a[]) =
  seq { for i in fromIdx .. -1 .. toIdx do // iterate in the opposite order
          yield arr.[ i ] };; // return a single element

// To use this you can write...
> sliceFromArrayRev 2 1 ar;;
val it : seq<int> = seq [3; 2]

This returns a lazy Seq<'a> type, so if you convert the returned sequence to array, you'll get the same thing as Array.rev does (because it will create a new array and copy the results to this array). If you'll use it with "for" loop or with other Seq.Xyz functions, then it will not allocate an array for the whole slice.

By on 11/17/2008 8:49 AM ()

Thanks.
That's basically what I did except I didn't know you can do:
for i in fromIdx .. -1 .. toIdx do

so I did:
let get_rev_slice_as_seq (l: 'a array) start finish =
seq {
for i = 0 to finish - start do
yield l.[finish - i]
}

Thanks for the tip.
I was somehow assuming that there's some builtin functionality that achieves this without having to write imperative code.

Generally speaking I would love to know if anyone happened to implement array slicing that creates these sorts of sequences in-situ without creating fresh copies of the array...

By on 11/17/2008 9:08 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