title: Invert a permutation in linear time, using only lists
body: <p>I want to define a function</p>
  
  <pre><code>invert :: [Int] -&gt; [Int]
  </code></pre>
  
  <p>that assumes that its input is a permutation of <code>[0..(n-1)]</code>, and returns its inverse. Can one define it using only lists and tuples (without arrays) so that it runs in linear time?</p>
  
  <p>This is primarily out of academic interest; in real code I might use <code>Array</code> or <code>STArray</code> or similar.</p>