    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