title: How do I return an array of objects using `impl Trait` from a function without boxing?
body: <p>I'm implementing a Sudoku crate, and I'd like to allow the possibility of higher-dimension Sudokus. In 2 dimensions, there are 3 groups that need to be checked for correctness (the prime rule contains only 3 subrules) and position (by definition) requires only 2 coordinates to fully specify, but in higher dimensions this obviously increases.</p>
  
  <p>I wrote the following method signature, but it doesn't work, and I'd like to avoid boxing at all costs due to the environments for which I'm developing.</p>
  
  <pre><code>pub fn groups(position: [u8; DIMENSIONS]) -&gt; [impl Group; DIMENSIONS + 1]
  </code></pre>
  
  <p>The actual type of each group will be known at compile time (the actual type will be something like <code>[Box, Stack, Band]</code>), but it appears that the compiler doesn't like this even though it'll know the size of each element.</p>
  
  <p>I'd love to be able to use a tuple with size determined at compile time, but that doesn't seem to be easily supported, unless I'm missing something.</p>
  
  <hr>
  
  <p>The idea is that there are <a href="https://en.wikipedia.org/wiki/Glossary_of_Sudoku#Terminology_and_grid_layout" rel="nofollow noreferrer">three types of <code>Group</code></a>: a <code>Stack</code> (column), a <code>Band</code> (row), and a <code>Box</code>. The definition for <code>Group</code> is given below.</p>
  
  <pre><code>pub trait Group {
      /// A group is considered valid if it has contains only unique elements.
      fn is_valid(&amp;self) -&gt; bool { /* Default implementation elided. */ }
      /// Returns an owned copy of the group's constituent elements.
      fn elements(&amp;self) -&gt; Vec&lt;Option&lt;Element&gt;&gt;;
  }
  </code></pre>
  
  <p>Let's start with the two-dimensional case. For a given element, we can write the element's index as a double (i.e. 2-tuple) <code>(x, y)</code>. The groups associated with this element are then one <code>Box</code> (as always; this is where <code>DIMENSION + 1</code> comes from), one <code>Stack</code>, and one <code>Band</code>.</p>
  
  <p>In three dimensions, a given element is indexed (by definition) by a triple (i.e. 3-tuple) <code>(x, y, z)</code>. The groups associated with this element are then one <code>Box</code>, one <code>Stack</code>, and <em>two</em> <code>Band</code>s.</p>
  
  <p>This trend continues into higher dimensions, and I want to enable the user to use a different dimensionality — thus the compile-time determination of sizes.</p>
  
  <p>To check the puzzle for correctness, the caller simply calls <code>Group::is_valid()</code> on each of <code>puzzle.groups()</code>; they can also iterate over each to render the puzzle as appropriate.</p>