F # - how to group the previous, this and next elements in a circular Seq

Question

In F # What is the best way to convert a finite sequence similar to seq [0; 1; 2; 3; 4] seq [0; 1; 2; 3; 4] seq [0; 1; 2; 3; 4] , in a sequence of tuples of the type seq [4,0,1 ; 0,1,2 ; 1,2,3 ; 2,3,4 ; 3,4,0] seq [4,0,1 ; 0,1,2 ; 1,2,3 ; 2,3,4 ; 3,4,0] seq [4,0,1 ; 0,1,2 ; 1,2,3 ; 2,3,4 ; 3,4,0] ?

Addition: My Seq is a cyclic data. In this case, the vertices of a closed polyline. I need neighboring elements to calculate the angle of each angle.

Answer 1

I would do it like this:

 let neighbors xs = match Array.ofSeq xs with | [||] -> [||] | [|x|] -> [|x, x, x|] | xs -> let n = xs.Length [|yield xs.[n-1], xs.[0], xs.[1] for i=1 to n-2 do yield xs.[i-1], xs.[i], xs.[i+1] yield xs.[n-2], xs.[n-1], xs.[0]|] 

Comparison is usually much faster than modulo integer arithmetic. To make this faster, pre-select the array and fill in the elements instead of using a sequence expression.

Answer 2

Here's a simple solution that uses only sequences. Please note: if the input and output are always a list, there is a slightly more complicated but faster solution that uses only lists and bypasses the input only once.

 // Example usage: neighbors [0..4] let neighbors input = let inputLength = Seq.length input input // The sequence needs to be looped three times; // the first and last time handle the previous value for the first // element in the input sequence and the next value for the last // element in the input sequence, respectively. |> Seq.replicate 3 // Start at the previous element of the first element in the input sequence. |> Seq.skip (inputLength - 1) // Take the same number of elements as the tuple. |> Seq.windowed 3 // Only keep the same number of elements as the original sequence. |> Seq.take inputLength // Convert the arrays to tuples |> Seq.map (fun values -> values.[0], values.[1], values.[2]) // Return the result as a list of tuples. |> Seq.toList 

Answer 3

This gives the correct answer, although the element that you have as the first is now the last, but this is not a problem, you can still find the angle for each set of three points.

 let cycle s = Seq.append s (Seq.take 2 s) // append the first two elements to the and |> Seq.windowed 3 // create windows of 3 |> Seq.map (fun a -> (a.[0], a.[1], a.[2])) // create tuples // test [0;1;2;3;4] |> cycle // returns: > val it : seq<int * int * int> = seq [(0, 1, 2); (1, 2, 3); (2, 3, 4); (3, 4, 0); ...] 

Answer 4

 let windowedEx n (s: seq<_>) = let r = ResizeArray(s) if r.Count > 1 then let last = r.[r.Count-1] r.Add(r.[0]) r.Insert(0, last) Seq.windowed nr 

Answer 5

There are some good answers here, here is another one. For me, this looks the most readable, has O(n) complexity, and also saves some error checking:

 // Returns the last element of a sequence. // Fails on empty sequence let last xs = let len = Seq.length xs - 1 if len < 0 then failwith "Sequence must be non-empty" xs |> Seq.skip len |> Seq.head // Converts an array into a tuple let toTuple = function | [|a; b; c|] -> (a, b, c) | _ -> failwith "Must be an array with exactly 3 elements" let windowedBy3 xs = seq { yield last xs; yield! xs; yield Seq.head xs } |> Seq.windowed 3 |> Seq.map toTuple // Usage Seq.init 5 id |> windowedBy3 |> Seq.iter (printf "%A; ") 

Answer 6

If you don't need laziness, using an intermediate array may be more efficient, like

 // get items (i-1, i, i+1) from arr; wrap around at the boundaries let adj3 i (arr: 'a[]) = // modulo operator that works correctly let inline (%%) xy = ((x % y) + y) % y let len = arr.Length arr.[(i - 1) %% len], arr.[i], arr.[(i + 1) %% len] let windowed3 s = seq { let sarr = s |> Seq.toArray for i = 0 to sarr.Length do yield adj3 i sarr } 

The complexity of time in O (n).

Answer 7

What does the general solution for Seq.circularWindowed look like? Given the size of the window n , he will need to use the first elements n - 1 in front, while maintaining laziness for the rest. If the source has at most n - 1 elements, it creates an empty sequence.

So this is a ResizeArray for the cache and a sequence expression to stitch it all together.

 module Seq = let circularWindowed n (xs : seq<_>) = let en = xs.GetEnumerator() let ra = ResizeArray() while ra.Count < n - 1 && en.MoveNext() do ra.Add en.Current seq{ if en.MoveNext() then yield! ra yield en.Current while en.MoveNext() do yield en.Current yield! ra } |> Seq.windowed n seq [0; 1; 2; 3; 4] |> Seq.circularWindowed 3 |> Seq.toList // val it : int [] list = // [[|0; 1; 2|]; [|1; 2; 3|]; [|2; 3; 4|]; [|3; 4; 0|]; [|4; 0; 1|]]