title: Polynomial factorization in Haskell
body: <p>With <a href="https://stackoverflow.com/questions/7563092/data-constructor-in-template-haskell">hammar's help</a> I have made a template Haskell bit which compiles </p>
  
  <pre><code>$(zModP 5)
  </code></pre>
  
  <p>to </p>
  
  <pre><code>newtype Z5 = Z5 Int
  instance Additive.C Z5 where
    (Z5 x) + (Z5 y) = Z5 $ (x + y) `mod` 5
  ...
  </code></pre>
  
  <p>I'm now facing a problem that I don't think I can solve this way. </p>
  
  <p>A remarkable fact about polynomials is that they are irreducible in the rationals if they are irreducible modulo some prime <code>p</code>. I already have a method which brute-force attempts to factor polynomials over a given (finite) field.</p>
  
  <p>I want to try running this function for multiple fields. Here's kind of what I want:</p>
  
  <pre><code>isIrreducible :: (FiniteField.C a) =&gt; Poly.T a -&gt; Bool
  isIrreducible p = ...
  
  intPolyIrreducible :: Poly.T Int -&gt; Bool
  intPolyIrreducible p = isIrreducible (p :: Poly.T Z2) ||
                         isIrreducible (p :: Poly.T Z3) ||
                         isIrreducible (p :: Poly.T Z5) ||
                         ...
  </code></pre>
  
  <p>Basically I want to try running my factoring algorithm for a large number of definitions of "division".</p>
  
  <p>I think this is possible to do with TH, but it seems like it would take forever. I'm wondering if it would be easier to just pass my arithmetical operations in as a parameter to <code>isIrreducible</code>?  </p>
  
  <p>Alternatively it seems like this might be something the Newtype module could help with, but I can't think of how it would work without using TH in a way which would be just as hard...</p>
  
  <p>Anyone have any thoughts on how best to accomplish this?</p>