title: Get all permutations of a list in Haskell
body: <p>I'm trying to do this from scratch, without the use of a library outside the standard lib. Heres my code:</p>
  
  <pre><code>permutations :: [a] -&gt; [[a]]
  permutations (x:xs) = [x] : permutations' xs
      where permutations' (x:xs) = (:) &lt;$&gt; [x] &lt;*&gt; split xs
              split l = [[x] | x &lt;- l]
  </code></pre>
  
  <p>The problem is that this only produces one fork of the non-deterministic computation. Ideally I'd want</p>
  
  <pre><code>(:) &lt;$&gt; [x] &lt;*&gt; ((:) &lt;$&gt; [x] &lt;*&gt; ((:) &lt;$&gt; [x] &lt;*&gt; ((:) &lt;$&gt; [x] &lt;*&gt; xs)))
  </code></pre>
  
  <p>But I can't find a way to do this cleanly. My desired result is something like this:</p>
  
  <pre><code>permutations "abc" -&gt; ["abc", "acb", "bac", "bca", "cab", "cba"]
  </code></pre>
  
  <p>How do I do this?</p>