{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE Rank2Types #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# OPTIONS_GHC -Wall #-}
{-# OPTIONS_HADDOCK show-extensions #-}
-----------------------------------------------------------------------------
-- |
-- Module      :  ToySolver.Data.Polynomial.Factorization.Zassenhaus
-- Copyright   :  (c) Masahiro Sakai 2012-2013
-- License     :  BSD-style
--
-- Maintainer  :  masahiro.sakai@gmail.com
-- Stability   :  provisional
-- Portability :  non-portable
--
-- Factoriation of integer-coefficient polynomial using Zassenhaus algorithm.
--
-- References:
--
-- * <http://www.math.kobe-u.ac.jp/Asir/ca.pdf>
--
-----------------------------------------------------------------------------
module ToySolver.Data.Polynomial.Factorization.Zassenhaus
  ( factor
  , zassenhaus
  ) where

import Control.Monad
import Control.Monad.ST
import Control.Exception (assert)
import Data.List
import Data.Maybe
import Data.Numbers.Primes (primes)
import Data.Ratio
import Data.STRef

import ToySolver.Data.Polynomial.Base (UPolynomial)
import qualified ToySolver.Data.Polynomial.Base as P
import ToySolver.Data.Polynomial.Factorization.FiniteField ()
import ToySolver.Data.Polynomial.Factorization.SquareFree ()
import qualified ToySolver.Data.Polynomial.Factorization.Hensel as Hensel

import Data.Proxy
import GHC.TypeLits
import Data.FiniteField

-- import Text.PrettyPrint.HughesPJClass

factor :: UPolynomial Integer -> [(UPolynomial Integer, Integer)]
factor :: UPolynomial Integer -> [(UPolynomial Integer, Integer)]
factor UPolynomial Integer
f = [(UPolynomial Integer
h,Integer
n) | (UPolynomial Integer
g,Integer
n) <- UPolynomial Integer -> [(UPolynomial Integer, Integer)]
forall a. SQFree a => a -> [(a, Integer)]
P.sqfree UPolynomial Integer
f, UPolynomial Integer
h <- if UPolynomial Integer -> Integer
forall t. Degree t => t -> Integer
P.deg UPolynomial Integer
g Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
> Integer
0 then UPolynomial Integer -> [UPolynomial Integer]
zassenhaus UPolynomial Integer
g else UPolynomial Integer -> [UPolynomial Integer]
forall a. a -> [a]
forall (m :: * -> *) a. Monad m => a -> m a
return UPolynomial Integer
g]

zassenhaus :: UPolynomial Integer -> [UPolynomial Integer]
zassenhaus :: UPolynomial Integer -> [UPolynomial Integer]
zassenhaus UPolynomial Integer
f = Maybe [UPolynomial Integer] -> [UPolynomial Integer]
forall a. (?callStack::CallStack) => Maybe a -> a
fromJust (Maybe [UPolynomial Integer] -> [UPolynomial Integer])
-> Maybe [UPolynomial Integer] -> [UPolynomial Integer]
forall a b. (a -> b) -> a -> b
$ [Maybe [UPolynomial Integer]] -> Maybe [UPolynomial Integer]
forall (t :: * -> *) (m :: * -> *) a.
(Foldable t, MonadPlus m) =>
t (m a) -> m a
msum [(forall (p :: Nat).
 KnownNat p =>
 Proxy p -> Maybe [UPolynomial Integer])
-> Integer -> Maybe [UPolynomial Integer]
forall a.
(forall (p :: Nat). KnownNat p => Proxy p -> a) -> Integer -> a
withNat Proxy p -> Maybe [UPolynomial Integer]
forall (p :: Nat).
KnownNat p =>
Proxy p -> Maybe [UPolynomial Integer]
zassenhausWithP Integer
p | Integer
p <- [Integer]
forall int. Integral int => [int]
primes :: [Integer]]
  where
    zassenhausWithP :: forall p. KnownNat p => Proxy p -> Maybe [UPolynomial Integer]
    zassenhausWithP :: forall (p :: Nat).
KnownNat p =>
Proxy p -> Maybe [UPolynomial Integer]
zassenhausWithP Proxy p
_ = do
      let f_mod_p :: UPolynomial (PrimeField p)
          f_mod_p :: UPolynomial (PrimeField p)
f_mod_p = (Integer -> PrimeField p)
-> UPolynomial Integer -> UPolynomial (PrimeField p)
forall k1 k v.
(Eq k1, Num k1) =>
(k -> k1) -> Polynomial k v -> Polynomial k1 v
P.mapCoeff Integer -> PrimeField p
forall a. Num a => Integer -> a
fromInteger UPolynomial Integer
f
      Bool -> Maybe ()
forall (f :: * -> *). Alternative f => Bool -> f ()
guard (Bool -> Maybe ()) -> Bool -> Maybe ()
forall a b. (a -> b) -> a -> b
$ UPolynomial Integer -> Integer
forall t. Degree t => t -> Integer
P.deg UPolynomial Integer
f Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== UPolynomial (PrimeField p) -> Integer
forall t. Degree t => t -> Integer
P.deg UPolynomial (PrimeField p)
f_mod_p -- 主係数を割り切らないことと同値
      Bool -> Maybe ()
forall (f :: * -> *). Alternative f => Bool -> f ()
guard (Bool -> Maybe ()) -> Bool -> Maybe ()
forall a b. (a -> b) -> a -> b
$ UPolynomial (PrimeField p) -> Bool
forall k. (Eq k, Fractional k) => UPolynomial k -> Bool
P.isSquareFree UPolynomial (PrimeField p)
f_mod_p
      let fs :: [UPolynomial (PrimeField p)]
          fs :: [UPolynomial (PrimeField p)]
fs = [Bool -> UPolynomial (PrimeField p) -> UPolynomial (PrimeField p)
forall a. (?callStack::CallStack) => Bool -> a -> a
assert (Integer
nInteger -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
==Integer
1) UPolynomial (PrimeField p)
fi | (UPolynomial (PrimeField p)
fi,Integer
n) <- UPolynomial (PrimeField p)
-> [(UPolynomial (PrimeField p), Integer)]
forall a. Factor a => a -> [(a, Integer)]
P.factor UPolynomial (PrimeField p)
f_mod_p]
      [UPolynomial Integer] -> Maybe [UPolynomial Integer]
forall a. a -> Maybe a
forall (m :: * -> *) a. Monad m => a -> m a
return ([UPolynomial Integer] -> Maybe [UPolynomial Integer])
-> [UPolynomial Integer] -> Maybe [UPolynomial Integer]
forall a b. (a -> b) -> a -> b
$ UPolynomial Integer
-> [UPolynomial (PrimeField p)] -> [UPolynomial Integer]
forall (p :: Nat).
KnownNat p =>
UPolynomial Integer
-> [UPolynomial (PrimeField p)] -> [UPolynomial Integer]
lift UPolynomial Integer
f [UPolynomial (PrimeField p)]
fs

    withNat :: (forall p. KnownNat p => Proxy p -> a) -> Integer -> a
    withNat :: forall a.
(forall (p :: Nat). KnownNat p => Proxy p -> a) -> Integer -> a
withNat forall (p :: Nat). KnownNat p => Proxy p -> a
f Integer
p =
      case Integer -> Maybe SomeNat
someNatVal Integer
p of
        Just (SomeNat Proxy n
x) -> Proxy n -> a
forall (p :: Nat). KnownNat p => Proxy p -> a
f Proxy n
x
        Maybe SomeNat
Nothing -> a
forall a. (?callStack::CallStack) => a
undefined

{-
Suppose @g@ is a factor of @f@.

From Landau-Mignotte inequality,
  @sum [abs c | (c,_) <- mapCoeff ((lc f / lc g) *) $ terms g] <= 2^(deg g) * norm2 f@ holds.

This together with @deg g <= deg f@ implies
  @all [- 2^(deg f) * norm2 f <= c <= 2^(deg f) * norm2 f | (c,_) <- terms ((lc f / lc g) * g)]@.

Choose smallest @k@ such that @p^k / 2 > 2^(deg f) * norm2 f@, so that
  @all [- (p^k)/2 < c < (p^k)/2 | (c,_) <- terms ((lc f / lc g) * g)]@.

Then it call @search@ to look for actual factorization.
-}
lift :: forall p. KnownNat p => UPolynomial Integer -> [UPolynomial (PrimeField p)] -> [UPolynomial Integer]
lift :: forall (p :: Nat).
KnownNat p =>
UPolynomial Integer
-> [UPolynomial (PrimeField p)] -> [UPolynomial Integer]
lift UPolynomial Integer
f [UPolynomial (PrimeField p)
_] = [UPolynomial Integer
f]
lift UPolynomial Integer
f [UPolynomial (PrimeField p)]
fs  = Integer
-> UPolynomial Integer
-> [UPolynomial Integer]
-> [UPolynomial Integer]
search Integer
pk UPolynomial Integer
f (UPolynomial Integer
-> [UPolynomial (PrimeField p)] -> Integer -> [UPolynomial Integer]
forall (p :: Nat).
KnownNat p =>
UPolynomial Integer
-> [UPolynomial (PrimeField p)] -> Integer -> [UPolynomial Integer]
Hensel.hensel UPolynomial Integer
f [UPolynomial (PrimeField p)]
fs Integer
k)
  where
    p :: Integer
p = PrimeField p -> Integer
forall k. FiniteField k => k -> Integer
char (PrimeField p
forall a. (?callStack::CallStack) => a
undefined :: PrimeField p)
    k, pk :: Integer
    (Integer
k,Integer
pk) = [(Integer, Integer)] -> (Integer, Integer)
forall a. (?callStack::CallStack) => [a] -> a
head [(Integer
k,Integer
pk) | Integer
k <- [Integer
1,Integer
2..], let pk :: Integer
pk = Integer
pInteger -> Integer -> Integer
forall a b. (Num a, Integral b) => a -> b -> a
^Integer
k, Integer
pkInteger -> Int -> Integer
forall a b. (Num a, Integral b) => a -> b -> a
^(Int
2::Int) Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
> (Integer
2Integer -> Integer -> Integer
forall a b. (Num a, Integral b) => a -> b -> a
^(UPolynomial Integer -> Integer
forall t. Degree t => t -> Integer
P.deg UPolynomial Integer
f Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
1))Integer -> Int -> Integer
forall a b. (Num a, Integral b) => a -> b -> a
^(Int
2::Int) Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* UPolynomial Integer -> Integer
forall a. Num a => UPolynomial a -> a
norm2sq UPolynomial Integer
f]

search :: Integer -> UPolynomial Integer -> [UPolynomial Integer] -> [UPolynomial Integer]
search :: Integer
-> UPolynomial Integer
-> [UPolynomial Integer]
-> [UPolynomial Integer]
search Integer
pk UPolynomial Integer
f0 [UPolynomial Integer]
fs0 = (forall s. ST s [UPolynomial Integer]) -> [UPolynomial Integer]
forall a. (forall s. ST s a) -> a
runST ((forall s. ST s [UPolynomial Integer]) -> [UPolynomial Integer])
-> (forall s. ST s [UPolynomial Integer]) -> [UPolynomial Integer]
forall a b. (a -> b) -> a -> b
$ do
  let a :: Integer
a = MonomialOrder X -> UPolynomial Integer -> Integer
forall k v. Num k => MonomialOrder v -> Polynomial k v -> k
P.lc MonomialOrder X
P.nat UPolynomial Integer
f0
      m :: Int
m = [UPolynomial Integer] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [UPolynomial Integer]
fs0

  STRef s (UPolynomial Integer)
fRef   <- UPolynomial Integer -> ST s (STRef s (UPolynomial Integer))
forall a s. a -> ST s (STRef s a)
newSTRef UPolynomial Integer
f0
  STRef s [UPolynomial Integer]
fsRef  <- [UPolynomial Integer] -> ST s (STRef s [UPolynomial Integer])
forall a s. a -> ST s (STRef s a)
newSTRef [UPolynomial Integer]
fs0
  STRef s [UPolynomial Integer]
retRef <- [UPolynomial Integer] -> ST s (STRef s [UPolynomial Integer])
forall a s. a -> ST s (STRef s a)
newSTRef []

  [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
forM_ [Int
1 .. Int
m Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \Int
l -> do
    [UPolynomial Integer]
fs <- STRef s [UPolynomial Integer] -> ST s [UPolynomial Integer]
forall s a. STRef s a -> ST s a
readSTRef STRef s [UPolynomial Integer]
fsRef
    [[UPolynomial Integer]]
-> ([UPolynomial Integer] -> ST s ()) -> ST s ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
forM_ ([UPolynomial Integer] -> Int -> [[UPolynomial Integer]]
forall a. [a] -> Int -> [[a]]
comb [UPolynomial Integer]
fs Int
l) (([UPolynomial Integer] -> ST s ()) -> ST s ())
-> ([UPolynomial Integer] -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \[UPolynomial Integer]
s -> do
      {-
          A factor @g@ of @f@ must satisfy @(lc f / lc g) * g ≡ product s (mod p^k)@ for some @s@.
          So we construct a candidate of @(lc f / lc g) * g@ from @product s@.
       -}
      let g0 :: UPolynomial Integer
g0 = [UPolynomial Integer] -> UPolynomial Integer
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
product [UPolynomial Integer]
s
          -- @g1@ is a candidate of @(lc f / lc g) * g@
          g1 :: UPolynomial Rational
          g1 :: UPolynomial Rational
g1 = (Integer -> Rational)
-> UPolynomial Integer -> UPolynomial Rational
forall k1 k v.
(Eq k1, Num k1) =>
(k -> k1) -> Polynomial k v -> Polynomial k1 v
P.mapCoeff Integer -> Rational
conv UPolynomial Integer
g0
          conv :: Integer -> Rational
          conv :: Integer -> Rational
conv Integer
b = Rational
b3
            where
              b1 :: Rational
b1  = (Integer
a Integer -> Integer -> Rational
forall a. Integral a => a -> a -> Ratio a
% MonomialOrder X -> UPolynomial Integer -> Integer
forall k v. Num k => MonomialOrder v -> Polynomial k v -> k
P.lc MonomialOrder X
P.nat UPolynomial Integer
g0) Rational -> Rational -> Rational
forall a. Num a => a -> a -> a
* Integer -> Rational
forall a b. (Integral a, Num b) => a -> b
fromIntegral Integer
b
              -- @b1 ≡ b2 (mod p^k)@ and @0 <= b2 < p^k@
              b2 :: Rational
b2  = Rational
b1 Rational -> Rational -> Rational
forall a. Num a => a -> a -> a
- (Integer -> Rational
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Rational -> Integer
forall b. Integral b => Rational -> b
forall a b. (RealFrac a, Integral b) => a -> b
floor (Rational
b1 Rational -> Rational -> Rational
forall a. Fractional a => a -> a -> a
/ Rational
pk') :: Integer) Rational -> Rational -> Rational
forall a. Num a => a -> a -> a
* Rational
pk')
              -- @b1 ≡ b2 ≡ b3 (mod p^k)@ and @-(p^k)/2 <= b3 <= (p^k)/2@
              b3 :: Rational
b3  = if Rational
pk'Rational -> Rational -> Rational
forall a. Fractional a => a -> a -> a
/Rational
2 Rational -> Rational -> Bool
forall a. Ord a => a -> a -> Bool
< Rational
b2 then Rational
b2 Rational -> Rational -> Rational
forall a. Num a => a -> a -> a
- Rational
pk' else Rational
b2
              pk' :: Rational
pk' = Integer -> Rational
forall a b. (Integral a, Num b) => a -> b
fromIntegral Integer
pk

      UPolynomial Integer
f <- STRef s (UPolynomial Integer) -> ST s (UPolynomial Integer)
forall s a. STRef s a -> ST s a
readSTRef STRef s (UPolynomial Integer)
fRef
      let f1 :: UPolynomial Rational
f1 = (Integer -> Rational)
-> UPolynomial Integer -> UPolynomial Rational
forall k1 k v.
(Eq k1, Num k1) =>
(k -> k1) -> Polynomial k v -> Polynomial k1 v
P.mapCoeff Integer -> Rational
forall a. Num a => Integer -> a
fromInteger UPolynomial Integer
f

      Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (UPolynomial Rational -> Integer
forall t. Degree t => t -> Integer
P.deg UPolynomial Rational
g1 Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
> Integer
0 Bool -> Bool -> Bool
&& UPolynomial Rational
g1 UPolynomial Rational -> UPolynomial Rational -> Bool
forall k.
(Eq k, Fractional k) =>
UPolynomial k -> UPolynomial k -> Bool
`P.divides` UPolynomial Rational
f1) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ do
        let g2 :: Polynomial (PPCoeff Rational) X
g2 = UPolynomial Rational -> Polynomial (PPCoeff Rational) X
forall v.
Ord v =>
Polynomial Rational v -> Polynomial (PPCoeff Rational) v
forall k v.
(ContPP k, Ord v) =>
Polynomial k v -> Polynomial (PPCoeff k) v
P.pp UPolynomial Rational
g1
            -- we choose leading coefficient to be positive.
            g :: UPolynomial Integer
            g :: UPolynomial Integer
g = if MonomialOrder X -> UPolynomial Integer -> Integer
forall k v. Num k => MonomialOrder v -> Polynomial k v -> k
P.lc MonomialOrder X
P.nat UPolynomial Integer
g2 Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
0 then - UPolynomial Integer
g2 else UPolynomial Integer
g2
        STRef s (UPolynomial Integer) -> UPolynomial Integer -> ST s ()
forall s a. STRef s a -> a -> ST s ()
writeSTRef STRef s (UPolynomial Integer)
fRef (UPolynomial Integer -> ST s ()) -> UPolynomial Integer -> ST s ()
forall a b. (a -> b) -> a -> b
$! UPolynomial Integer
f UPolynomial Integer -> UPolynomial Integer -> UPolynomial Integer
`div'` UPolynomial Integer
g
        STRef s [UPolynomial Integer]
-> ([UPolynomial Integer] -> [UPolynomial Integer]) -> ST s ()
forall s a. STRef s a -> (a -> a) -> ST s ()
modifySTRef STRef s [UPolynomial Integer]
retRef (UPolynomial Integer
g UPolynomial Integer
-> [UPolynomial Integer] -> [UPolynomial Integer]
forall a. a -> [a] -> [a]
:)
        STRef s [UPolynomial Integer]
-> ([UPolynomial Integer] -> [UPolynomial Integer]) -> ST s ()
forall s a. STRef s a -> (a -> a) -> ST s ()
modifySTRef STRef s [UPolynomial Integer]
fsRef ([UPolynomial Integer]
-> [UPolynomial Integer] -> [UPolynomial Integer]
forall a. Eq a => [a] -> [a] -> [a]
\\ [UPolynomial Integer]
s)

  UPolynomial Integer
f <- STRef s (UPolynomial Integer) -> ST s (UPolynomial Integer)
forall s a. STRef s a -> ST s a
readSTRef STRef s (UPolynomial Integer)
fRef
  [UPolynomial Integer]
ret <- STRef s [UPolynomial Integer] -> ST s [UPolynomial Integer]
forall s a. STRef s a -> ST s a
readSTRef STRef s [UPolynomial Integer]
retRef
  if UPolynomial Integer
fUPolynomial Integer -> UPolynomial Integer -> Bool
forall a. Eq a => a -> a -> Bool
==UPolynomial Integer
1
    then [UPolynomial Integer] -> ST s [UPolynomial Integer]
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return [UPolynomial Integer]
ret
    else [UPolynomial Integer] -> ST s [UPolynomial Integer]
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return ([UPolynomial Integer] -> ST s [UPolynomial Integer])
-> [UPolynomial Integer] -> ST s [UPolynomial Integer]
forall a b. (a -> b) -> a -> b
$ UPolynomial Integer
f UPolynomial Integer
-> [UPolynomial Integer] -> [UPolynomial Integer]
forall a. a -> [a] -> [a]
: [UPolynomial Integer]
ret

-- |f|^2
norm2sq :: Num a => UPolynomial a -> a
norm2sq :: forall a. Num a => UPolynomial a -> a
norm2sq UPolynomial a
f = [a] -> a
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum [a
ca -> Int -> a
forall a b. (Num a, Integral b) => a -> b -> a
^(Int
2::Int) | (a
c,Monomial X
_) <- UPolynomial a -> [(a, Monomial X)]
forall k v. Polynomial k v -> [Term k v]
P.terms UPolynomial a
f]

div' :: UPolynomial Integer -> UPolynomial Integer -> UPolynomial Integer
div' :: UPolynomial Integer -> UPolynomial Integer -> UPolynomial Integer
div' UPolynomial Integer
f1 UPolynomial Integer
f2 = Bool -> UPolynomial Integer -> UPolynomial Integer
forall a. (?callStack::CallStack) => Bool -> a -> a
assert ([Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
and [Rational -> Integer
forall a. Ratio a -> a
denominator Rational
c Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 | (Rational
c,Monomial X
_) <- UPolynomial Rational -> [(Rational, Monomial X)]
forall k v. Polynomial k v -> [Term k v]
P.terms UPolynomial Rational
g3]) UPolynomial Integer
g4
  where
    g1, g2 :: UPolynomial Rational
    g1 :: UPolynomial Rational
g1 = (Integer -> Rational)
-> UPolynomial Integer -> UPolynomial Rational
forall k1 k v.
(Eq k1, Num k1) =>
(k -> k1) -> Polynomial k v -> Polynomial k1 v
P.mapCoeff Integer -> Rational
forall a. Num a => Integer -> a
fromInteger UPolynomial Integer
f1
    g2 :: UPolynomial Rational
g2 = (Integer -> Rational)
-> UPolynomial Integer -> UPolynomial Rational
forall k1 k v.
(Eq k1, Num k1) =>
(k -> k1) -> Polynomial k v -> Polynomial k1 v
P.mapCoeff Integer -> Rational
forall a. Num a => Integer -> a
fromInteger UPolynomial Integer
f2
    g3 :: UPolynomial Rational
g3 = UPolynomial Rational
g1 UPolynomial Rational
-> UPolynomial Rational -> UPolynomial Rational
forall k.
(Eq k, Fractional k) =>
UPolynomial k -> UPolynomial k -> UPolynomial k
`P.div` UPolynomial Rational
g2
    g4 :: UPolynomial Integer
g4 = (Rational -> Integer)
-> UPolynomial Rational -> UPolynomial Integer
forall k1 k v.
(Eq k1, Num k1) =>
(k -> k1) -> Polynomial k v -> Polynomial k1 v
P.mapCoeff Rational -> Integer
forall a. Ratio a -> a
numerator UPolynomial Rational
g3

comb :: [a] -> Int -> [[a]]
comb :: forall a. [a] -> Int -> [[a]]
comb [a]
_ Int
0      = [[]]
comb [] Int
_     = []
comb (a
x:[a]
xs) Int
n = [a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
ys | [a]
ys <- [a] -> Int -> [[a]]
forall a. [a] -> Int -> [[a]]
comb [a]
xs (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)] [[a]] -> [[a]] -> [[a]]
forall a. [a] -> [a] -> [a]
++ [a] -> Int -> [[a]]
forall a. [a] -> Int -> [[a]]
comb [a]
xs Int
n

-- ---------------------------------------------------------------------------