title: pure Knuth/Fisher-Yates shuffle in haskell
body: <p>In go I could write a function like this:</p>
  
  <pre><code>func pureFisherYates(s []int, swaps []int) []int {
      newS := copy(s)
      for i, _ := range newS {
              for _, j := range swaps {
                      newS[i], newS[j] = newS[j], newS[i]
              }
      }
  }
  </code></pre>
  
  <p>To me this seems like a pure function. It always returns the same output given the same input, and it doesn't mutate the state of the world (except in some strict sense the same way that any other function does, taking up cpu resources, creating heat energy, etc). Yet whenever I look for how to do pure shuffling I find stuff like <a href="http://okmij.org/ftp/Haskell/perfect-shuffle.txt" rel="nofollow noreferrer">this</a>, and whenever I look for specifically Haskell implementation Fisher-Yates I either get an <code>0^2</code> Fisher-Yates implemented with a list or a <code>[a] -&gt; IO [a]</code> implementation. Does there exist a <code>[a] -&gt; [a]</code> <code>O(n)</code> shuffle and if not why is my above go implementation impure.</p>