title: Haskell All possible partitions of a list
body: <p>I need to write a function that produces all of the possible partitions of a list, including non-contiguous partitions.  It should look something like this:</p>
  
  <pre><code>*Main&gt; ps [1,2,3,4]
  [[21, 3, 4],[31, 2, 4],[41, 2, 3],[431, 2],[21, 43],[4321],[31, 42],[421, 3],[41, 32],[321, 4],[1, 32, 4],[1, 42, 3],[1, 432],[1, 2, 43],[1, 2, 3, 4]]
  </code></pre>
  
  <p>So far I have only been able to produce a recursive function using list comprehension to produce the contiguous partitions.</p>
  
  <pre><code>ps [] = [[]]
  ps (x:xs) = [[x]:qs | qs &lt;- ps xs] ++ [(x:gs):gss | (gs):gss &lt;- ps xs]
  </code></pre>
  
  <p>I have an idea of moving the tail of each partition and prepending it to the first element of each partition, but I am not sure how I would do this in Haskell.  I'm still a newbie to this language.  Any help would be greatly appreciated!</p>