GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
cd67b36992d2ea20ba330acb56e2e9ac04c11938

Branches

Tags

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

Clone

HTTPS

Download ZIP

qdk/library/std

library/std/arrays.qs

1395lines · modecode

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