GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

mirrored fromhttps://github.com/microsoft/qdkAvailable

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
sccarda/BlochLearning

Branches

Tags

  • No tags available.
0Branches0Tags
Go to file
Add file
Code

Clone

HTTPS

Download ZIP

qdk/library/std/src/Std

library/std/src/Std/Arrays.qs

1486lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4import Std.Diagnostics.*;
5import Std.Math.*;
6
7/// # Summary
8/// Given an array and a predicate that is defined
9/// for the elements of the array, and checks if all elements of the
10/// array satisfy the predicate.
11///
12/// # Type Parameters
13/// ## 'T
14/// The type of `array` elements.
15///
16/// # Input
17/// ## predicate
18/// A function from `'T` to `Bool` that is used to check elements.
19/// ## array
20/// An array of elements over `'T`.
21///
22/// # Output
23/// A `Bool` value of the AND function of the predicate applied to all elements.
24///
25/// # Example
26/// The following code checks whether all elements of the array are non-zero:
27/// ```qsharp
28/// let allNonZero = All(x -> x != 0, [1, 2, 3, 4, 5]);
29/// ```
30function All<'T>(predicate : ('T -> Bool), array : 'T[]) : Bool {
31 for element in array {
32 if not predicate(element) {
33 return false;
34 }
35 }
36
37 true
38}
39
40/// # Summary
41/// Given an array and a predicate that is defined
42/// for the elements of the array, checks if at least one element of
43/// the array satisfies the predicate.
44///
45/// # Type Parameters
46/// ## 'T
47/// The type of `array` elements.
48///
49/// # Input
50/// ## predicate
51/// A function from `'T` to `Bool` that is used to check elements.
52/// ## array
53/// An array of elements over `'T`.
54///
55/// # Output
56/// A `Bool` value of the OR function of the predicate applied to all elements.
57///
58/// # Example
59/// ```qsharp
60/// let anyEven = Any(x -> x % 2 == 0, [1, 3, 6, 7, 9]);
61/// ```
62function Any<'T>(predicate : ('T -> Bool), array : 'T[]) : Bool {
63 for element in array {
64 if predicate(element) {
65 return true;
66 }
67 }
68
69 false
70}
71
72/// # Summary
73/// Splits an array into multiple parts of equal length.
74///
75/// # Input
76/// ## chunkSize
77/// The length of each chunk. Must be positive.
78/// ## array
79/// The array to be split in chunks.
80///
81/// # Output
82/// A array containing each chunk of the original array.
83///
84/// # Remarks
85/// Note that the last element of the output may be shorter
86/// than `chunkSize` if `Length(array)` is not divisible by `chunkSize`.
87function Chunks<'T>(chunkSize : Int, array : 'T[]) : 'T[][] {
88 Fact(chunkSize > 0, "`chunkSize` must be positive");
89 mutable output = [];
90 mutable remaining = array;
91 while (not IsEmpty(remaining)) {
92 let chunkSizeToTake = MinI(Length(remaining), chunkSize);
93 set output += [remaining[...chunkSizeToTake - 1]];
94 set remaining = remaining[chunkSizeToTake...];
95 }
96
97 output
98}
99
100/// # Summary
101/// Shift an array circularly left or right by a specific step size.
102///
103/// # Type Parameters
104/// ## 'T
105/// The type of the array elements.
106///
107/// # Input
108/// ## stepCount
109/// The amount of positions by which the array elements will be shifted.
110/// If this is positive, `array` is circularly shifted to the right.
111/// If this is negative, `array` is circularly shifted to the left.
112/// ## array
113/// Array to be circularly shifted.
114///
115/// # Output
116/// An array `output` that is the `array` circularly shifted to the right or left
117/// by the specified step size.
118///
119/// # Example
120/// ```qsharp
121/// let array = [10, 11, 12];
122/// // The following line returns [11, 12, 10].
123/// let output = CircularlyShifted(2, array);
124/// // The following line returns [12, 10, 11].
125/// let output = CircularlyShifted(-2, array);
126/// ```
127function CircularlyShifted<'T>(stepCount : Int, array : 'T[]) : 'T[] {
128 let arrayLength = Length(array);
129 if arrayLength <= 1 {
130 return array;
131 }
132
133 // normalize circular shift count to be within the bounds of the array length
134 let normalizedShift = stepCount % arrayLength;
135 let effectiveShift = normalizedShift >= 0 ? arrayLength - normalizedShift | -normalizedShift;
136
137 // no shift needed
138 if effectiveShift == 0 {
139 return array;
140 }
141
142 let leftPart = array[...effectiveShift - 1];
143 let rightPart = array[effectiveShift..arrayLength - 1];
144
145 rightPart + leftPart
146}
147
148/// # Summary
149/// Extracts a column from a matrix.
150///
151/// # Description
152/// This function extracts a column in a matrix in row-wise order.
153/// Extracting a row corresponds to element access of the first index
154/// and therefore requires no further treatment.
155///
156/// # Type Parameters
157/// ## 'T
158/// The type of each element of `matrix`.
159///
160/// # Input
161/// ## column
162/// Column of the matrix
163/// ## matrix
164/// 2-dimensional matrix in row-wise order
165///
166/// # Example
167/// ```qsharp
168/// let matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
169/// let column = ColumnAt(0, matrix);
170/// // same as: column = [1, 4, 7]
171/// ```
172///
173/// # See Also
174/// - [Std.Arrays.Transposed](xref:Qdk.Std.Arrays.Transposed)
175/// - [Std.Arrays.Diagonal](xref:Qdk.Std.Arrays.Diagonal)
176function ColumnAt<'T>(column : Int, matrix : 'T[][]) : 'T[] {
177 Fact(IsRectangularArray(matrix), "`matrix` is not a rectangular array");
178 mutable columnValues = [];
179 for row in matrix {
180 set columnValues += [row[column]];
181 }
182 columnValues
183}
184
185/// # Summary
186/// Given an array and a predicate that is defined
187/// for the elements of the array, returns the number of elements
188/// an array that consists of those elements that satisfy the predicate.
189///
190/// # Type Parameters
191/// ## 'T
192/// The type of `array` elements.
193///
194/// # Input
195/// ## predicate
196/// A function from `'T` to Boolean that is used to filter elements.
197/// ## array
198/// An array of elements over `'T`.
199///
200/// # Output
201/// The number of elements in `array` that satisfy the predicate.
202///
203/// # Example
204/// ```qsharp
205/// let evensCount = Count(x -> x % 2 == 0, [1, 3, 6, 7, 9]);
206/// // evensCount is 1.
207/// ```
208function Count<'T>(predicate : ('T -> Bool), array : 'T[]) : Int {
209 mutable count = 0;
210 for element in array {
211 if predicate(element) {
212 set count += 1;
213 }
214 }
215 count
216}
217
218/// # Summary
219/// Returns an array of diagonal elements of a 2-dimensional array
220///
221/// # Description
222/// If the 2-dimensional array has not a square shape, the diagonal over
223/// the minimum over the number of rows and columns will be returned.
224///
225/// # Type Parameters
226/// ## 'T
227/// The type of each element of `matrix`.
228///
229/// # Input
230/// ## matrix
231/// 2-dimensional matrix in row-wise order.
232///
233/// # Example
234/// ```qsharp
235/// let matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
236/// let diagonal = Diagonal(matrix);
237/// // same as: column = [1, 5, 9]
238/// ```
239///
240/// # See Also
241/// - [Std.Arrays.Transposed](xref:Qdk.Std.Arrays.Transposed)
242function Diagonal<'T>(matrix : 'T[][]) : 'T[] {
243 Fact(IsRectangularArray(matrix), "`matrix` is not a rectangular array");
244 let rows = Length(matrix);
245 let columns = rows == 0 ? 0 | Length(Head(matrix));
246 let rangeLimit = MinI(rows, columns) - 1;
247 mutable diagonal = [];
248 for index in 0..rangeLimit {
249 set diagonal += [matrix[index][index]];
250 }
251
252 diagonal
253}
254
255/// # Summary
256/// Repeats an operation for a given number of samples, collecting its outputs
257/// in an array.
258///
259/// # Input
260/// ## op
261/// The operation to be called repeatedly.
262/// ## nSamples
263/// The number of samples of calling `op` to collect.
264/// ## input
265/// The input to be passed to `op`.
266///
267/// # Type Parameters
268/// ## TInput
269/// The type of input expected by `op`.
270/// ## TOutput
271/// The type of output returned by `op`.
272///
273/// # Example
274/// The following samples an alternating array of results.
275/// ```qsharp
276/// use qubit = Qubit();
277/// let results = Std.Arrays.DrawMany(q => {X(q); M(q)}, 3, qubit);
278/// ```
279operation DrawMany<'TInput, 'TOutput>(op : ('TInput => 'TOutput), nSamples : Int, input : 'TInput) : 'TOutput[] {
280 mutable outputs = [];
281 for _ in 1..nSamples {
282 set outputs += [op(input)];
283 }
284 outputs
285}
286
287/// # Summary
288/// Given an array, returns a new array containing elements of the original
289/// array along with the indices of each element.
290///
291/// # Type Parameters
292/// ## 'TElement
293/// The type of elements of the array.
294///
295/// # Input
296/// ## array
297/// An array whose elements are to be enumerated.
298///
299/// # Output
300/// A new array containing elements of the original array along with their
301/// indices.
302///
303/// # Example
304/// The following `for` loops are equivalent:
305/// ```qsharp
306/// for (idx in IndexRange(array)) {
307/// let element = array[idx];
308/// ...
309/// }
310/// for ((idx, element) in Enumerated(array)) { ... }
311/// ```
312function Enumerated<'TElement>(array : 'TElement[]) : (Int, 'TElement)[] {
313 MappedByIndex((index, element) -> (index, element), array)
314}
315
316/// # Summary
317/// Returns an array containing the elements of another array,
318/// excluding elements at a given list of indices.
319///
320/// # Type Parameters
321/// ## 'T
322/// The type of the array elements.
323///
324/// # Input
325/// ## remove
326/// An array of indices denoting which elements should be excluded.
327/// from the output.
328/// ## array
329/// Array of which the values in the output array are taken.
330///
331/// # Output
332/// An array `output` such that `output[0]` is the first element
333/// of `array` whose index does not appear in `remove`,
334/// such that `output[1]` is the second such element, and so
335/// forth.
336///
337/// # Example
338/// ```qsharp
339/// let array = [10, 11, 12, 13, 14, 15];
340/// // The following line returns [10, 12, 15].
341/// let subarray = Excluding([1, 3, 4], array);
342/// ```
343function Excluding<'T>(remove : Int[], array : 'T[]) : 'T[] {
344 let arrayLength = Length(array);
345 mutable toKeep = Repeated(true, arrayLength);
346 for indexToRemove in remove {
347 set toKeep w/= indexToRemove <- false;
348 }
349 mutable output = [];
350 for index in 0..arrayLength - 1 {
351 if toKeep[index] {
352 set output += [array[index]];
353 }
354 }
355 output
356}
357
358/// # Summary
359/// Given an array and a predicate that is defined
360/// for the elements of the array, returns an array that consists of
361/// those elements that satisfy the predicate.
362///
363/// # Type Parameters
364/// ## 'T
365/// The type of `array` elements.
366///
367/// # Input
368/// ## predicate
369/// A function from `'T` to Boolean that is used to filter elements.
370/// ## array
371/// An array of elements over `'T`.
372///
373/// # Output
374/// An array `'T[]` of elements that satisfy the predicate.
375///
376/// # Example
377/// The following code creates an array that contains only even numbers.
378/// ```qsharp
379/// Filtered(x -> x % 2 == 0, [0, 1, 2, 3, 4])
380/// ```
381function Filtered<'T>(predicate : ('T -> Bool), array : 'T[]) : 'T[] {
382 mutable filtered = [];
383 for element in array {
384 if predicate(element) {
385 set filtered += [element];
386 }
387 }
388 filtered
389}
390
391/// # Summary
392/// Given an array and a function that maps an array element to some output
393/// array, returns the concatenated output arrays for each array element.
394///
395/// # Type Parameters
396/// ## 'TInput
397/// The type of `array` elements.
398/// ## 'TOutput
399/// The `mapper` function returns arrays of this type.
400///
401/// # Input
402/// ## mapper
403/// A function from `'TInput` to `'TOutput[]` that is used to map array elements.
404/// ## array
405/// An array of elements.
406///
407/// # Output
408/// An array of `'TOutput[]` which is the concatenation of all arrays generated by
409/// the mapping function.
410///
411/// # Example
412/// The following code creates an array with each element of the input array repeated twice.
413/// ```qsharp
414/// let repeatedPairs = FlatMapped(x -> Repeated(x, 2), [1, 2, 3]);
415/// // repeatedPairs is [1, 1, 2, 2, 3, 3].
416/// ```
417function FlatMapped<'TInput, 'TOutput>(mapper : ('TInput -> 'TOutput[]), array : 'TInput[]) : 'TOutput[] {
418 mutable output = [];
419 for element in array {
420 set output += mapper(element);
421 }
422 output
423}
424
425/// # Summary
426/// Given an array of arrays, returns the concatenation of all arrays.
427///
428/// # Type Parameters
429/// ## 'T
430/// The type of `array` elements.
431///
432/// # Input
433/// ## arrays
434/// Array of arrays.
435///
436/// # Output
437/// Concatenation of all arrays.
438///
439/// # Example
440/// ```qsharp
441/// let flattened = Flattened([[1, 2], [3], [4, 5, 6]]);
442/// // flattened = [1, 2, 3, 4, 5, 6]
443/// ```
444function Flattened<'T>(arrays : 'T[][]) : 'T[] {
445 mutable output = [];
446 for array in arrays {
447 set output += array;
448 }
449 output
450}
451
452/// # Summary
453/// Iterates a function `f` through an array `array`, returning
454/// `f(...f(f(initialState, array[0]), array[1]), ...)`.
455///
456/// # Type Parameters
457/// ## 'State
458/// The type of states the `folder` function operates on, i.e., accepts as its first
459/// argument and returns.
460/// ## 'T
461/// The type of `array` elements.
462///
463/// # Input
464/// ## folder
465/// A function to be folded over the array.
466/// ## state
467/// The initial state of the folder.
468/// ## array
469/// An array of values to be folded over.
470///
471/// # Output
472/// The final state returned by the folder after iterating over
473/// all elements of `array`.
474///
475/// # Example
476/// ```qsharp
477/// let sum = Fold((x, y) -> x + y, 0, [1, 2, 3, 4, 5]); // `sum` is 15.
478/// ```
479function Fold<'State, 'T>(folder : (('State, 'T) -> 'State), state : 'State, array : 'T[]) : 'State {
480 mutable current = state;
481 for element in array {
482 set current = folder(current, element);
483 }
484 current
485}
486
487/// # Summary
488/// Given an array and an operation that is defined
489/// for the elements of the array, returns a new array that consists
490/// of the images of the original array under the operation.
491///
492/// # Type Parameters
493/// ## 'T
494/// The type of `array` elements.
495/// ## 'U
496/// The result type of the `action` operation.
497///
498/// # Input
499/// ## action
500/// An operation from `'T` to `'U` that is applied to each element.
501/// ## array
502/// An array of elements over `'T`.
503///
504/// # Output
505/// An array `'U[]` of elements that are mapped by the `action` operation.
506///
507/// # See Also
508/// - [Std.Arrays.Mapped](xref:Qdk.Std.Arrays.Mapped)
509operation ForEach<'T, 'U>(action : ('T => 'U), array : 'T[]) : 'U[] {
510 mutable output = [];
511 for element in array {
512 set output += [action(element)];
513 }
514 output
515}
516
517/// # Summary
518/// Returns the first element of the array.
519///
520/// # Type Parameters
521/// ## 'A
522/// The type of the array elements.
523///
524/// # Input
525/// ## array
526/// Array of which the first element is taken. Array must have at least 1 element.
527///
528/// # Output
529/// The first element of the array.
530function Head<'A>(array : 'A[]) : 'A {
531 Fact(Length(array) > 0, "Array must have at least 1 element");
532 array[0]
533}
534
535/// # Summary
536/// Returns a tuple of first and all remaining elements of the array.
537///
538/// # Type Parameters
539/// ## 'A
540/// The type of the array elements.
541///
542/// # Input
543/// ## array
544/// An array with at least one element.
545///
546/// # Output
547/// A tuple of first and all remaining elements of the array.
548function HeadAndRest<'A>(array : 'A[]) : ('A, 'A[]) {
549 (Head(array), Rest(array))
550}
551
552/// # Summary
553/// Returns the first index of the first element in an array that satisfies
554/// a given predicate. If no such element exists, returns -1.
555///
556/// # Input
557/// ## predicate
558/// A predicate function acting on elements of the array.
559/// ## array
560/// An array to be searched using the given predicate.
561///
562/// # Output
563/// Either the smallest index of an element for which `predicate(array[index])` is true,
564/// or -1 if no such element exists.
565///
566/// # Example
567/// The following code gets the index of the first even number in the input array.
568/// ```qsharp
569/// let indexOfFirstEven = IndexOf(x -> x % 2 == 0, [1, 3, 17, 2, 21]);
570/// // `indexOfFirstEven` is 3.
571/// ```
572function IndexOf<'T>(predicate : ('T -> Bool), array : 'T[]) : Int {
573 for index in 0..Length(array) - 1 {
574 if predicate(array[index]) {
575 return index;
576 }
577 }
578 -1
579}
580
581/// # Summary
582/// Given an array, returns a range over the indices of that array, suitable
583/// for use in a for loop.
584///
585/// # Type Parameters
586/// ## 'TElement
587/// The type of elements of the array.
588///
589/// # Input
590/// ## array
591/// An array for which a range of indices should be returned.
592///
593/// # Output
594/// A range over all indices of the array.
595///
596/// # Example
597/// The following `for` loops are equivalent:
598/// ```qsharp
599/// for idx in IndexRange(array) { ... }
600/// for idx in 0 .. Length(array) - 1 { ... }
601/// ```
602function IndexRange<'TElement>(array : 'TElement[]) : Range {
603 0..Length(array) - 1
604}
605
606/// # Summary
607/// Interleaves two arrays of (almost) same size.
608///
609/// # Description
610/// This function returns the interleaving of two arrays, starting
611/// with the first element from the first array, then the first
612/// element from the second array, and so on.
613///
614/// The first array must either be
615/// of the same length as the second one, or can have one more element.
616///
617/// # Type Parameters
618/// ## 'T
619/// The type of each element of `first` and `second`.
620///
621/// # Input
622/// ## first
623/// The first array to be interleaved.
624///
625/// ## second
626/// The second array to be interleaved.
627///
628/// # Output
629/// Interleaved array
630///
631/// # Example
632/// ```qsharp
633/// // same as interleaved = [1, -1, 2, -2, 3, -3]
634/// let interleaved = Interleaved([1, 2, 3], [-1, -2, -3])
635/// ```
636function Interleaved<'T>(first : 'T[], second : 'T[]) : 'T[] {
637 let firstLength = Length(first);
638 let secondLength = Length(second);
639 Fact(
640 firstLength == secondLength or firstLength == secondLength + 1,
641 "Array `first` must either be of same size as `second` or have one more element"
642 );
643
644 let interleavedLength = firstLength + secondLength;
645 mutable interleaved = [];
646 for index in 0..interleavedLength - 1 {
647 let originalIndex = index / 2;
648 let value = if index % 2 == 0 { first[originalIndex] } else { second[originalIndex] };
649 set interleaved += [value];
650 }
651 interleaved
652}
653
654/// # Summary
655/// Returns true if and only if an array is empty.
656///
657/// # Input
658/// ## array
659/// The array to be checked.
660///
661/// # Output
662/// `true` if and only if the array is empty (has length 0).
663function IsEmpty<'T>(array : 'T[]) : Bool {
664 Length(array) == 0
665}
666
667/// # Summary
668/// Returns whether a 2-dimensional array has a rectangular shape
669///
670/// # Type Parameters
671/// ## 'T
672/// The type of each element of `array`.
673///
674/// # Input
675/// ## array
676/// A 2-dimensional array of elements.
677///
678/// # Output
679/// `true` if the array is rectangular, `false` otherwise.
680///
681/// # Example
682/// ```qsharp
683/// IsRectangularArray([[1, 2], [3, 4]]); // true
684/// IsRectangularArray([[1, 2, 3], [4, 5, 6]]); // true
685/// IsRectangularArray([[1, 2], [3, 4, 5]]); // false
686/// ```
687///
688/// # See Also
689/// - [Std.Arrays.IsSquareArray](xref:Qdk.Std.Arrays.IsSquareArray)
690function IsRectangularArray<'T>(array : 'T[][]) : Bool {
691 if (Length(array) > 0) {
692 let columnCount = Length(Head(array));
693 for index in 1..Length(array) - 1 {
694 if Length(array[index]) != columnCount {
695 return false;
696 }
697 }
698 }
699
700 true
701}
702
703/// # Summary
704/// Given an array, returns whether that array is sorted as defined by
705/// a given comparison function.
706///
707/// # Type Parameters
708/// ## 'T
709/// The type of each element of `array`.
710///
711/// # Input
712/// ## comparison
713/// A function that compares two elements such that `a` is considered to
714/// be less than or equal to `b` if `comparison(a, b)` is `true`.
715/// ## array
716/// The array to be checked.
717///
718/// # Output
719/// `true` if and only if for each pair of elements `a` and `b` of
720/// `array` occurring in that order, `comparison(a, b)` is `true`.
721///
722/// # Remarks
723/// The function `comparison` is assumed to be transitive, such that
724/// if `comparison(a, b)` and `comparison(b, c)`, then `comparison(a, c)`
725/// is assumed.
726function IsSorted<'T>(comparison : (('T, 'T) -> Bool), array : 'T[]) : Bool {
727 for index in 1..Length(array) - 1 {
728 if not comparison(array[index - 1], array[index]) {
729 return false;
730 }
731 }
732 true
733}
734
735/// # Summary
736/// Returns whether a 2-dimensional array has a square shape
737///
738/// # Type Parameters
739/// ## 'T
740/// The type of each element of `array`.
741///
742/// # Input
743/// ## array
744/// A 2-dimensional array of elements.
745///
746/// # Example
747/// ```qsharp
748/// IsSquareArray([[1, 2], [3, 4]]); // true
749/// IsSquareArray([[1, 2, 3], [4, 5, 6]]); // false
750/// IsSquareArray([[1, 2], [3, 4], [5, 6]]); // false
751/// ```
752///
753/// # Output
754/// `true` if the array is square, `false` otherwise.
755///
756/// # See Also
757/// - [Std.Arrays.IsRectangularArray](xref:Qdk.Std.Arrays.IsRectangularArray)
758function IsSquareArray<'T>(array : 'T[][]) : Bool {
759 if (Length(array) > 0) {
760 let columnCount = Length(array);
761 for column in array {
762 if Length(column) != columnCount {
763 return false;
764 }
765 }
766 }
767
768 true
769}
770
771/// # Summary
772/// Given an array and a function that is defined
773/// for the elements of the array, returns a new array that consists
774/// of the images of the original array under the function.
775///
776/// # Type Parameters
777/// ## 'T
778/// The type of `array` elements.
779/// ## 'U
780/// The result type of the `mapper` function.
781///
782/// # Input
783/// ## mapper
784/// A function from `'T` to `'U` that is used to map elements.
785/// ## array
786/// An array of elements over `'T`.
787///
788/// # Output
789/// An array `'U[]` of elements that are mapped by the `mapper` function.
790///
791/// # See Also
792/// - [Std.Arrays.ForEach](xref:Qdk.Std.Arrays.ForEach)
793function Mapped<'T, 'U>(mapper : ('T -> 'U), array : 'T[]) : 'U[] {
794 mutable mapped = [];
795 for element in array {
796 set mapped += [mapper(element)];
797 }
798 mapped
799}
800
801/// # Summary
802/// Given an array and a function that is defined
803/// for the indexed elements of the array, returns a new array that consists
804/// of the images of the original array under the function.
805///
806/// # Type Parameters
807/// ## 'T
808/// The type of `array` elements.
809/// ## 'U
810/// The result type of the `mapper` function.
811///
812/// # Input
813/// ## mapper
814/// A function from `(Int, 'T)` to `'U` that is used to map elements
815/// and their indices.
816/// ## array
817/// An array of elements over `'T`.
818///
819/// # Output
820/// An array `'U[]` of elements that are mapped by the `mapper` function.
821///
822/// # Example
823/// The following two lines are equivalent:
824/// ```qsharp
825/// let array = MappedByIndex(f, [x0, x1, x2]);
826/// ```
827/// and
828/// ```qsharp
829/// let array = [f(0, x0), f(1, x1), f(2, x2)];
830/// ```
831///
832/// # See Also
833/// - [Std.Arrays.Mapped](xref:Qdk.Std.Arrays.Mapped)
834function MappedByIndex<'T, 'U>(mapper : ((Int, 'T) -> 'U), array : 'T[]) : 'U[] {
835 mutable mapped = [];
836 for index in 0..Length(array) - 1 {
837 set mapped += [mapper(index, array[index])];
838 }
839 mapped
840}
841
842/// # Summary
843/// Given a range and a function that takes an integer as input,
844/// returns a new array that consists
845/// of the images of the range values under the function.
846///
847/// # Type Parameters
848/// ## 'T
849/// The result type of the `mapper` function.
850///
851/// # Input
852/// ## mapper
853/// A function from `Int` to `'T` that is used to map range values.
854/// ## range
855/// A range of integers.
856///
857/// # Output
858/// An array `'T[]` of elements that are mapped by the `mapper` function.
859///
860/// # Example
861/// This example adds 1 to a range of even numbers:
862/// ```qsharp
863/// let numbers = MappedOverRange(x -> x + 1, 0..2..10);
864/// // numbers = [1, 3, 5, 7, 9, 11]
865/// ```
866///
867/// # See Also
868/// - [Std.Arrays.Mapped](xref:Qdk.Std.Arrays.Mapped)
869function MappedOverRange<'T>(mapper : (Int -> 'T), range : Range) : 'T[] {
870 mutable output = [];
871 for element in range {
872 set output += [mapper(element)];
873 }
874 output
875}
876
877/// # Summary
878/// Creates an array that is equal to an input array except that the last array
879/// element is dropped.
880///
881/// # Type Parameters
882/// ## 'T
883/// The type of the array elements.
884///
885/// # Input
886/// ## array
887/// An array whose first to second-to-last elements are to form the output array.
888///
889/// # Output
890/// An array containing the elements `array[0..Length(array) - 2]`.
891function Most<'T>(array : 'T[]) : 'T[] {
892 array[...Length(array) - 2]
893}
894
895/// # Summary
896/// Returns a tuple of all but one and the last element of the array.
897///
898/// # Type Parameters
899/// ## 'A
900/// The type of the array elements.
901///
902/// # Input
903/// ## array
904/// An array with at least one element.
905///
906/// # Output
907/// A tuple of all but one and the last element of the array.
908function MostAndTail<'A>(array : 'A[]) : ('A[], 'A) {
909 (Most(array), Tail(array))
910}
911
912/// # Summary
913/// Returns an array padded at with specified values up to a
914/// specified length.
915///
916/// # Type Parameters
917/// ## 'T
918/// The type of the array elements.
919///
920/// # Input
921/// ## paddedLength
922/// The length of the padded array. If this is positive, `array`
923/// is padded at the head. If this is negative, `array` is padded
924/// at the tail.
925/// ## defaultElement
926/// Default value to use for padding elements.
927/// ## array
928/// Array to be padded.
929///
930/// # Output
931/// An array `output` that is the `array` padded at the head or the tail
932/// with `defaultElement`s until `output` has length `paddedLength`
933///
934/// # Example
935/// ```qsharp
936/// let array = [10, 11, 12];
937/// // The following line returns [10, 12, 15, 2, 2].
938/// let output = Padded(-5, 2, array);
939/// // The following line returns [2, 2, 10, 12, 15].
940/// let output = Padded(5, 2, array);
941/// ```
942function Padded<'T>(paddedLength : Int, defaultElement : 'T, inputArray : 'T[]) : 'T[] {
943 let nElementsInitial = Length(inputArray);
944 let nAbsElementsTotal = AbsI(paddedLength);
945 if nAbsElementsTotal < nElementsInitial {
946 fail "Specified output array length must be at least as long as `inputArray` length.";
947 }
948 let nElementsPad = nAbsElementsTotal - nElementsInitial;
949 let padArray = Repeated(defaultElement, nElementsPad);
950 if (paddedLength >= 0) {
951 padArray + inputArray // Padded at head.
952 } else {
953 inputArray + padArray // Padded at tail.
954 }
955}
956
957/// # Summary
958/// Splits an array into multiple parts.
959///
960/// # Input
961/// ## partitionSizes
962/// Number of elements in each split part of array.
963/// ## array
964/// Input array to be split.
965///
966/// # Output
967/// Multiple arrays where the first array is the first `partitionSizes[0]` of `array`
968/// and the second array are the next `partitionSizes[1]` of `array` etc. The last array
969/// will contain all remaining elements. If the array is split exactly, the
970/// last array will be the empty array, indicating there are no remaining elements.
971/// In other words, `Tail(Partitioned(...))` will always return the remaining
972/// elements, while `Most(Partitioned(...))` will always return the complete
973/// partitions of the array.
974///
975/// # Example
976/// ```qsharp
977/// // The following returns [[2, 3], [5], [7]];
978/// let split = Partitioned([2, 1], [2, 3, 5, 7]);
979/// // The following returns [[2, 3], [5, 7], []];
980/// let split = Partitioned([2, 2], [2, 3, 5, 7]);
981/// ```
982function Partitioned<'T>(partitionSizes : Int[], array : 'T[]) : 'T[][] {
983 mutable output = Repeated([], Length(partitionSizes) + 1);
984 mutable partitionStartIndex = 0;
985 for index in IndexRange(partitionSizes) {
986 let partitionEndIndex = partitionStartIndex + partitionSizes[index] - 1;
987 if partitionEndIndex >= Length(array) {
988 fail "Partitioned argument out of bounds.";
989 }
990 set output w/= index <- array[partitionStartIndex..partitionEndIndex];
991 set partitionStartIndex = partitionEndIndex + 1;
992 }
993 set output w/= Length(partitionSizes) <- array[partitionStartIndex..Length(array) - 1];
994 output
995}
996
997/// # Summary
998/// Creates an array that is equal to an input array except that the first array
999/// element is dropped.
1000///
1001/// # Type Parameters
1002/// ## 'T
1003/// The type of the array elements.
1004///
1005/// # Input
1006/// ## array
1007/// An array whose second to last elements are to form the output array.
1008///
1009/// # Output
1010/// An array containing the elements `array[1..Length(array) - 1]`.
1011function Rest<'T>(array : 'T[]) : 'T[] {
1012 array[1...]
1013}
1014
1015/// # Summary
1016/// Create an array that contains the same elements as an input array but in reversed
1017/// order.
1018///
1019/// # Type Parameters
1020/// ## 'T
1021/// The type of the array elements.
1022///
1023/// # Input
1024/// ## array
1025/// An array whose elements are to be copied in reversed order.
1026///
1027/// # Output
1028/// An array containing the elements `array[Length(array) - 1]` .. `array[0]`.
1029function Reversed<'T>(array : 'T[]) : 'T[] {
1030 array[...-1...]
1031}
1032
1033/// # Summary
1034/// Get an array of integers in a given interval.
1035///
1036/// # Input
1037/// ## from
1038/// An inclusive start index of the interval.
1039/// ## to
1040/// An inclusive end index of the interval that is not smaller than `from`.
1041///
1042/// # Output
1043/// An array containing the sequence of numbers `from`, `from + 1`, ...,
1044/// `to`.
1045///
1046/// # Example
1047/// ```qsharp
1048/// let arr1 = SequenceI(0, 3); // [0, 1, 2, 3]
1049/// let arr2 = SequenceI(23, 29); // [23, 24, 25, 26, 27, 28, 29]
1050/// let arr3 = SequenceI(-5, -2); // [-5, -4, -3, -2]
1051///
1052/// let numbers = SequenceI(0, _); // function to create sequence from 0 to `to`
1053/// let naturals = SequenceI(1, _); // function to create sequence from 1 to `to`
1054/// ```
1055function SequenceI(from : Int, to : Int) : Int[] {
1056 Fact(to >= from, "`to` must be larger than `from`.");
1057 mutable array = [];
1058 for index in from..to {
1059 set array += [index];
1060 }
1061 array
1062}
1063
1064/// # Summary
1065/// Get an array of integers in a given interval.
1066///
1067/// # Input
1068/// ## from
1069/// An inclusive start index of the interval.
1070/// ## to
1071/// An inclusive end index of the interval that is not smaller than `from`.
1072///
1073/// # Output
1074/// An array containing the sequence of numbers `from`, `from + 1`, ...,
1075/// `to`.
1076///
1077/// # Remarks
1078/// The difference between `from` and `to` must fit into an `Int` value.
1079///
1080/// # Example
1081/// ```qsharp
1082/// let arr1 = SequenceL(0L, 3L); // [0L, 1L, 2L, 3L]
1083/// let arr2 = SequenceL(23L, 29L); // [23L, 24L, 25L, 26L, 27L, 28L, 29L]
1084/// let arr3 = SequenceL(-5L, -2L); // [-5L, -4L, -3L, -2L]
1085/// ```
1086function SequenceL(from : BigInt, to : BigInt) : BigInt[] {
1087 Fact(to >= from, "`to` must be larger than `from`");
1088 mutable array = [];
1089 mutable current = from;
1090 while current <= to {
1091 set array += [current];
1092 set current += 1L;
1093 }
1094
1095 array
1096}
1097
1098/// # Summary
1099/// Given an array, returns the elements of that array sorted by a given
1100/// comparison function.
1101///
1102/// # Type Parameters
1103/// ## 'T
1104/// The type of each element of `array`.
1105///
1106/// # Input
1107/// ## comparison
1108/// A function that compares two elements such that `a` is considered to
1109/// be less than or equal to `b` if `comparison(a, b)` is `true`.
1110/// ## array
1111/// The array to be sorted.
1112///
1113/// # Output
1114/// An array containing the same elements as `array`, such that for all
1115/// elements `a` occurring earlier than elements `b`, `comparison(a, b)`
1116/// is `true`.
1117///
1118/// # Example
1119/// The following snippet sorts an array of integers to occur in ascending
1120/// order:
1121/// ```qsharp
1122/// let sortedArray = Sorted(LessThanOrEqualI, [3, 17, 11, -201, -11]);
1123/// ```
1124///
1125/// # Remarks
1126/// The function `comparison` is assumed to be transitive, such that
1127/// if `comparison(a, b)` and `comparison(b, c)`, then `comparison(a, c)`
1128/// is assumed. If this property does not hold, then the output of this
1129/// function may be incorrect.
1130function Sorted<'T>(comparison : (('T, 'T) -> Bool), array : 'T[]) : 'T[] {
1131 if Length(array) <= 1 {
1132 return array;
1133 }
1134
1135 let pivotIndex = Length(array) / 2;
1136 let left = array[...pivotIndex - 1];
1137 let right = array[pivotIndex...];
1138
1139 // Sort each sublist, then merge them back into a single combined
1140 // list and return.
1141 SortedMerged(
1142 comparison,
1143 Sorted(comparison, left),
1144 Sorted(comparison, right)
1145 )
1146}
1147
1148/// # Summary
1149/// Given two sorted arrays, returns a single array containing the
1150/// elements of both in sorted order. Used internally by `Sorted`.
1151internal function SortedMerged<'T>(comparison : (('T, 'T) -> Bool), left : 'T[], right : 'T[]) : 'T[] {
1152 mutable output = [];
1153 mutable remainingLeft = left;
1154 mutable remainingRight = right;
1155 while (not IsEmpty(remainingLeft)) and (not IsEmpty(remainingRight)) {
1156 if comparison(Head(remainingLeft), Head(remainingRight)) {
1157 set output += [Head(remainingLeft)];
1158 set remainingLeft = Rest(remainingLeft);
1159 } else {
1160 set output += [Head(remainingRight)];
1161 set remainingRight = Rest(remainingRight);
1162 }
1163 }
1164
1165 // Note that at this point, either or both of `remainingLeft` and `remainingRight` are empty,
1166 // such that we can simply append both to our output to get the whole merged array.
1167 output + remainingLeft + remainingRight
1168}
1169
1170/// # Summary
1171/// Takes an array and a list of locations and
1172/// produces a new array formed from the elements of the original
1173/// array that match the given locations.
1174///
1175/// # Remarks
1176/// If `locations` contains repeated elements, the corresponding elements
1177/// of `array` will likewise be repeated.
1178///
1179/// # Type Parameters
1180/// ## 'T
1181/// The type of `array` elements.
1182///
1183/// # Input
1184/// ## locations
1185/// A list of locations in the input array that is used to define the subarray.
1186/// ## array
1187/// An array from which a subarray will be generated.
1188///
1189/// # Output
1190/// An array `out` of elements whose locations correspond to the subarray,
1191/// such that `out[index] == array[locations[index]]`.
1192///
1193/// # Example
1194///
1195/// ```qsharp
1196/// let array = [1, 2, 3, 4];
1197/// let permutation = Subarray([3, 0, 2, 1], array); // [4, 1, 3, 2]
1198/// let duplicates = Subarray([1, 2, 2], array); // [2, 3, 3]
1199/// ```
1200function Subarray<'T>(locations : Int[], array : 'T[]) : 'T[] {
1201 mutable subarray = [];
1202 for location in locations {
1203 set subarray += [array[location]];
1204 }
1205 subarray
1206}
1207
1208/// # Summary
1209/// Applies a swap of two elements in an array.
1210///
1211/// # Input
1212/// ## firstIndex
1213/// Index of the first element to be swapped.
1214///
1215/// ## secondIndex
1216/// Index of the second element to be swapped.
1217///
1218/// ## array
1219/// Array with elements to be swapped.
1220///
1221/// # Output
1222/// The array with the in place swap applied.
1223///
1224/// # Example
1225/// ```qsharp
1226/// // The following returns [0, 3, 2, 1, 4]
1227/// Swapped(1, 3, [0, 1, 2, 3, 4]);
1228/// ```
1229function Swapped<'T>(firstIndex : Int, secondIndex : Int, array : 'T[]) : 'T[] {
1230 array
1231 w/ firstIndex <- array[secondIndex]
1232 w/ secondIndex <- array[firstIndex]
1233}
1234
1235/// # Summary
1236/// Returns the transpose of a matrix represented as an array
1237/// of arrays.
1238///
1239/// # Description
1240/// Input as an r x c matrix with r rows and c columns. The matrix
1241/// is row-based, i.e., `matrix[i][j]` accesses the element at row `i` and column `j`.
1242///
1243/// This function returns the c x r matrix that is the transpose of the
1244/// input matrix.
1245///
1246/// # Type Parameters
1247/// ## 'T
1248/// The type of each element of `matrix`.
1249///
1250/// # Input
1251/// ## matrix
1252/// Row-based r x c matrix.
1253///
1254/// # Output
1255/// Transposed c x r matrix.
1256///
1257/// # Example
1258/// ```qsharp
1259/// // same as [[1, 4], [2, 5], [3, 6]]
1260/// let transposed = Transposed([[1, 2, 3], [4, 5, 6]]);
1261/// ```
1262function Transposed<'T>(matrix : 'T[][]) : 'T[][] {
1263 let rowCount = Length(matrix);
1264 Fact(rowCount > 0, "Matrix must have at least 1 row");
1265 let columnCount = Length(Head(matrix));
1266 Fact(columnCount > 0, "Matrix must have at least 1 column");
1267 Fact(IsRectangularArray(matrix), "Matrix is not a rectangular array");
1268 mutable transposed = [];
1269 for columnIndex in 0..columnCount - 1 {
1270 mutable newRow = [];
1271 for rowIndex in 0..rowCount - 1 {
1272 set newRow += [matrix[rowIndex][columnIndex]];
1273 }
1274 set transposed += [newRow];
1275 }
1276 transposed
1277}
1278
1279/// # Summary
1280/// Returns the last element of the array.
1281///
1282/// # Type Parameters
1283/// ## 'A
1284/// The type of the array elements.
1285///
1286/// # Input
1287/// ## array
1288/// Array of which the last element is taken. Array must have at least 1 element.
1289///
1290/// # Output
1291/// The last element of the array.
1292function Tail<'A>(array : 'A[]) : 'A {
1293 let size = Length(array);
1294 Fact(size > 0, "Array must have at least 1 element");
1295 array[size - 1]
1296}
1297
1298/// # Summary
1299/// Given an array of 2-tuples, returns a tuple of two arrays, each containing
1300/// the elements of the tuples of the input array.
1301///
1302/// # Type Parameters
1303/// ## 'T
1304/// The type of the first element in each tuple.
1305/// ## 'U
1306/// The type of the second element in each tuple.
1307///
1308/// # Input
1309/// ## array
1310/// An array containing 2-tuples.
1311///
1312/// # Output
1313/// Two arrays, the first one containing all first elements of the input
1314/// tuples, the second one containing all second elements of the input tuples.
1315///
1316/// # Example
1317/// ```qsharp
1318/// // split is same as ([5, 4, 3, 2, 1], [true, false, true, true, false])
1319/// let split = Unzipped([(5, true), (4, false), (3, true), (2, true), (1, false)]);
1320/// ```
1321///
1322/// # See Also
1323/// - [Std.Arrays.Zipped](xref:Qdk.Std.Arrays.Zipped)
1324function Unzipped<'T, 'U>(array : ('T, 'U)[]) : ('T[], 'U[]) {
1325 mutable first = [];
1326 mutable second = [];
1327 for index in 0..Length(array) - 1 {
1328 let (left, right) = array[index];
1329 set first += [left];
1330 set second += [right];
1331 }
1332 return (first, second);
1333}
1334
1335/// # Summary
1336/// Given a predicate and an array, returns the indices of that
1337/// array where the predicate is true.
1338///
1339/// # Type Parameters
1340/// ## 'T
1341/// The type of `array` elements.
1342///
1343/// # Input
1344/// ## predicate
1345/// A function from `'T` to Boolean that is used to filter elements.
1346/// ## array
1347/// An array of elements over `'T`.
1348///
1349/// # Output
1350/// An array of indices where `predicate` is true.
1351function Where<'T>(predicate : ('T -> Bool), array : 'T[]) : Int[] {
1352 mutable indexes = [];
1353 for index in 0..Length(array) - 1 {
1354 if predicate(array[index]) {
1355 set indexes += [index];
1356 }
1357 }
1358 indexes
1359}
1360
1361/// # Summary
1362/// Returns all consecutive subarrays of length `size`.
1363///
1364/// # Description
1365/// This function returns all `n - size + 1` subarrays of
1366/// length `size` in order, where `n` is the length of `array`.
1367/// The first subarrays are `array[0..size - 1], array[1..size], array[2..size + 1]`
1368/// until the last subarray `array[n - size..n - 1]`.
1369///
1370/// # Type Parameters
1371/// ## 'T
1372/// The type of `array` elements.
1373///
1374/// # Input
1375/// ## size
1376/// Length of the subarrays.
1377///
1378/// ## array
1379/// An array of elements.
1380///
1381/// # Example
1382/// ```qsharp
1383/// // same as [[1, 2, 3], [2, 3, 4], [3, 4, 5]]
1384/// let windows = Windows(3, [1, 2, 3, 4, 5]);
1385/// ```
1386///
1387/// # Remarks
1388/// The size of the window must be a positive integer no greater than the size of the array
1389function Windows<'T>(size : Int, array : 'T[]) : 'T[][] {
1390 let arrayLength = Length(array);
1391 Fact(
1392 size > 0 or size <= arrayLength,
1393 "The size of the window must be a positive integer no greater than the size of the array"
1394 );
1395
1396 mutable windows = [];
1397 for index in 0..arrayLength - size {
1398 set windows += [array[index..index + size - 1]];
1399 }
1400 windows
1401}
1402
1403/// # Summary
1404/// Given two arrays, returns a new array of pairs such that each pair
1405/// contains an element from each original array.
1406///
1407/// # Type Parameters
1408/// ## 'T
1409/// The type of the left array elements.
1410/// ## 'U
1411/// The type of the right array elements.
1412///
1413/// # Input
1414/// ## left
1415/// An array containing values for the first element of each tuple.
1416/// ## right
1417/// An array containing values for the second element of each tuple.
1418///
1419/// # Output
1420/// An array containing pairs of the form `(left[index], right[index])` for
1421/// each `index`. If the two arrays are not of equal length, the output will
1422/// be as long as the shorter of the inputs.
1423///
1424/// # Example
1425/// ```qsharp
1426/// let left = [1, 3, 71];
1427/// let right = [false, true];
1428/// let pairs = Zipped(left, right); // [(1, false), (3, true)]
1429/// ```
1430///
1431/// # See Also
1432/// - [Std.Arrays.Unzipped](xref:Qdk.Std.Arrays.Unzipped)
1433function Zipped<'T, 'U>(left : 'T[], right : 'U[]) : ('T, 'U)[] {
1434 let arrayLength = MinI(Length(left), Length(right));
1435 mutable zipped = [];
1436 for index in 0..arrayLength - 1 {
1437 set zipped += [(left[index], right[index])];
1438 }
1439 zipped
1440}
1441
1442export
1443 All,
1444 Any,
1445 Chunks,
1446 CircularlyShifted,
1447 ColumnAt,
1448 Count,
1449 Diagonal,
1450 DrawMany,
1451 Enumerated,
1452 Excluding,
1453 Filtered,
1454 FlatMapped,
1455 Flattened,
1456 Fold,
1457 ForEach,
1458 Head,
1459 HeadAndRest,
1460 IndexOf,
1461 IndexRange,
1462 Interleaved,
1463 IsEmpty,
1464 IsRectangularArray,
1465 IsSorted,
1466 IsSquareArray,
1467 Mapped,
1468 MappedByIndex,
1469 MappedOverRange,
1470 Most,
1471 MostAndTail,
1472 Padded,
1473 Partitioned,
1474 Rest,
1475 Reversed,
1476 SequenceI,
1477 SequenceL,
1478 Sorted,
1479 Subarray,
1480 Swapped,
1481 Transposed,
1482 Tail,
1483 Unzipped,
1484 Where,
1485 Windows,
1486 Zipped;