content: module Numeric.Algebra.Factorable
    ( -- * Factorable Multiplicative Semigroups
      Factorable(..)
    ) where
  
  import Data.List.NonEmpty
  import Numeric.Algebra.Class (Multiplicative(..))
  import Prelude hiding (concat)
  
  -- | `factorWith f c` returns a non-empty list containing `f a b` for all `a, b` such that `a * b = c`.
  --
  -- Results of factorWith f 0 are undefined and may result in either an error or an infinite list.
  
  class Multiplicative m => Factorable m where
    factorWith :: (m -> m -> r) -> m -> NonEmpty r
  
  instance Factorable Bool where
    factorWith f False = f False False :| [f False True, f True False]
    factorWith f True  = f True True :| []
  
  instance Factorable () where
    factorWith f () = f () () :| []
  
  concat :: NonEmpty (NonEmpty a) -> NonEmpty a
  concat m = m >>= id
  
  instance (Factorable a, Factorable b) => Factorable (a,b) where
    factorWith f (a,b) = concat $ factorWith (\ax ay ->
                                  factorWith (\bx by -> f (ax,bx) (ay,by)) b) a
  
  instance (Factorable a, Factorable b, Factorable c) => Factorable (a,b,c) where
    factorWith f (a,b,c) = concat $ factorWith (\ax ay ->
                              concat $ factorWith (\bx by ->
                                       factorWith (\cx cy -> f (ax,bx,cx) (ay,by,cy)) c) b) a
  
  instance (Factorable a, Factorable b, Factorable c,Factorable d ) => Factorable (a,b,c,d) where
    factorWith f (a,b,c,d) = concat $ factorWith (\ax ay ->
                             concat $ factorWith (\bx by ->
                             concat $ factorWith (\cx cy ->
                                      factorWith (\dx dy -> f (ax,bx,cx,dx) (ay,by,cy,dy)) d) c) b) a
  
  instance (Factorable a, Factorable b, Factorable c,Factorable d, Factorable e) => Factorable (a,b,c,d,e) where
    factorWith f (a,b,c,d,e) = concat $ factorWith (\ax ay ->
                               concat $ factorWith (\bx by ->
                               concat $ factorWith (\cx cy ->
                               concat $ factorWith (\dx dy ->
                                        factorWith (\ex ey -> f (ax,bx,cx,dx,ex) (ay,by,cy,dy,ey)) e) d) c) b) a
  
  
  