<commit_before>--------------------------------------------------------------------------------
-- |
-- Module      : Project.Core.Factorization
-- Note        : Ein paar kleine Funktionen, um mit Faktorisierungen zu Arbeiten
--
--
--
--------------------------------------------------------------------------------
module Projekt.Core.Factorization
  ( toFact, unFact
  , potFact, appFact, aggFact
  , isTrivialFact
  -- Faktoriesierungen
  , obviousFactor, appObFact, findTrivialsOb
  , findTrivialsNs
  )where
import Data.List

import Control.Parallel
import Control.Parallel.Strategies

import Projekt.Core.FiniteFields
import Projekt.Core.Polynomials

--------------------------------------------------------------------------------
-- Eine Faktoriesierung wird dargestellt als Liste von Paaren (Int, Polynom a)
-- wobei ein Paar (i,f) den Faktor f^i repräsentiert.
--
-- Ein Faktoriesierungsalgorithmus ist also gegeben durch eine Funktion:
--      Polynom a -> [(Int,Polynom a)]

-- |Erzeugt eine triviale Faktoriesierung zu einem Polynom
toFact :: Polynom a -> [(Int,Polynom a)]
toFact f = [(1,f)]

-- |Multipliziert eine Faktoriesierung aus
unFact :: (FiniteField a, Num a, Fractional a) => [(Int,Polynom a)] -> Polynom a
unFact [(1,f)] = f
unFact [(i,f)] = f^i
unFact fs      = product $ map (\(i,f) -> f^i) fs

-- |Ersetzt eine Faktoriesierung, durch die n-te Potenz dieser Faktoriesierung
potFact :: (Num a) => Int -> [(Int,Polynom a)]
                                                           -> [(Int,Polynom a)]
potFact _ []         = []
potFact n ((i,f):ts) = (i*n,f) : potFact n ts

-- |Nimmt eine Faktoriesierung und wendet auf diese einen gegebenen
-- Faktoriesierungsalgorithmus an
appFact :: (Num a) =>
  (Polynom a -> [(Int,Polynom a)]) -> [(Int,Polynom a)] -> [(Int,Polynom a)]
appFact alg = withStrategy (parList rpar) . concatMap
  (\(i,f) -> potFact i (alg f))

-- |Fasst in einer Faktoriesierung gleiche Funktionen Zusammen
aggFact :: (Num a, Eq a) => [(Int,Polynom a)]
                                                            -> [(Int,Polynom a)]
aggFact l = [(sum [i | (i,g) <- l , f==g],f) | f <- nub [f | (_,f) <- l], f /= P[1]]

isTrivialFact :: [(Int,a)] -> Bool
isTrivialFact [] = error "[] is not a factorization"
isTrivialFact [(1,_)] = True
isTrivialFact ms = sum (map fst ms) == 1

-- |Gibt alle Faktorisierungen zurück, welche nach der offensichtlichen
-- Faktoriesierung noch trivial sind
findTrivialsOb :: (Show a, Fractional a, Num a, FiniteField a) => [Polynom a] -> [[(Int,Polynom a)]]
findTrivialsOb ps = [fs | fs <- parMap rpar appObFact
                        [(toFact . aggP) f | f <- ps , f /= P[]]
                      , isTrivialFact fs]

findTrivialsNs :: (Show a, Fractional a, Num a, FiniteField a) => [Polynom a] -> [[(Int,Polynom a)]]
findTrivialsNs ps = [toFact f | f <- ps,
    not (hasNs f es) || uDegP f < 2]
  where es = elems $ getReprP $ head ps

--------------------------------------------------------------------------------
--  Einfache / offensichtliche Faktorisierungen

obviousFactor :: (Num a, Eq a) => Polynom a -> [(Int,Polynom a)]
obviousFactor (P[])      = [(1,P[])]
obviousFactor (P[m])     = [(1,P[m])]
obviousFactor (P[m0,m1]) = [(1,P[m0,m1])]
obviousFactor (P (0:ms)) = aggFact $ (1,P[0,1]) : obviousFactor (P ms)
obviousFactor f          = toFact f

appObFact :: (Num a, Eq a) => [(Int,Polynom a)] -> [(Int,Polynom a)]<commit_msg>füge Nullstellensuche zur irredsuche hinzu<commit_after>--------------------------------------------------------------------------------
-- |
-- Module      : Project.Core.Factorization
-- Note        : Ein paar kleine Funktionen, um mit Faktorisierungen zu Arbeiten
--
--
--
--------------------------------------------------------------------------------
module Projekt.Core.Factorization
  ( toFact, unFact
  , potFact, appFact, aggFact
  , isTrivialFact
  -- Faktoriesierungen
  , obviousFactor, appObFact, findTrivialsOb
  , findTrivialsNs
  )where
import Data.List

import Control.Parallel
import Control.Parallel.Strategies

import Projekt.Core.FiniteFields
import Projekt.Core.Polynomials

--------------------------------------------------------------------------------
-- Eine Faktoriesierung wird dargestellt als Liste von Paaren (Int, Polynom a)
-- wobei ein Paar (i,f) den Faktor f^i repräsentiert.
--
-- Ein Faktoriesierungsalgorithmus ist also gegeben durch eine Funktion:
--      Polynom a -> [(Int,Polynom a)]

-- |Erzeugt eine triviale Faktoriesierung zu einem Polynom
toFact :: Polynom a -> [(Int,Polynom a)]
toFact f = [(1,f)]

-- |Multipliziert eine Faktoriesierung aus
unFact :: (FiniteField a, Num a, Fractional a) => [(Int,Polynom a)] -> Polynom a
unFact [(1,f)] = f
unFact [(i,f)] = f^i
unFact fs      = product $ map (\(i,f) -> f^i) fs

-- |Ersetzt eine Faktoriesierung, durch die n-te Potenz dieser Faktoriesierung
potFact :: (Num a) => Int -> [(Int,Polynom a)]
                                                           -> [(Int,Polynom a)]
potFact _ []         = []
potFact n ((i,f):ts) = (i*n,f) : potFact n ts

-- |Nimmt eine Faktoriesierung und wendet auf diese einen gegebenen
-- Faktoriesierungsalgorithmus an
appFact :: (Num a) =>
  (Polynom a -> [(Int,Polynom a)]) -> [(Int,Polynom a)] -> [(Int,Polynom a)]
appFact alg = withStrategy (parList rpar) . concatMap
  (\(i,f) -> potFact i (alg f))

-- |Fasst in einer Faktoriesierung gleiche Funktionen Zusammen
aggFact :: (Num a, Eq a) => [(Int,Polynom a)]
                                                            -> [(Int,Polynom a)]
aggFact l = [(sum [i | (i,g) <- l , f==g],f) | f <- nub [f | (_,f) <- l], f /= P[1]]

isTrivialFact :: [(Int,a)] -> Bool
isTrivialFact [] = error "[] is not a factorization"
isTrivialFact [(1,_)] = True
isTrivialFact ms = sum (map fst ms) == 1

-- |Gibt alle Faktorisierungen zurück, welche nach der offensichtlichen
-- Faktoriesierung noch trivial sind
findTrivialsOb :: (Show a, Fractional a, Num a, FiniteField a) => [Polynom a] -> [[(Int,Polynom a)]]
findTrivialsOb ps = [fs | fs <- parMap rpar appObFact
                        [(toFact . aggP) f | f <- ps , f /= P[]]
                      , isTrivialFact fs]

findTrivialsNs :: (Show a, Fractional a, Num a, FiniteField a) => [Polynom a]
  -> [[(Int,Polynom a)]]
findTrivialsNs ps = [toFact f | f <- ps, not (hasNs f es) || uDegP f < 2]
  where es = elems $ getReprP $ head ps

--------------------------------------------------------------------------------
--  Einfache / offensichtliche Faktorisierungen

obviousFactor :: (Num a, Eq a) => Polynom a -> [(Int,Polynom a)]
obviousFactor (P[])      = [(1,P[])]
obviousFactor (P[m])     = [(1,P[m])]
obviousFactor (P[m0,m1]) = [(1,P[m0,m1])]
obviousFactor (P (0:ms)) = aggFact $ (1,P[0,1]) : obviousFactor (P ms)
obviousFactor f          = toFact f

appObFact :: (Num a, Eq a) => [(Int,Polynom a)] -> [(Int,Polynom a)]
{'fraction_non_alphanumeric': 0.2315206298294212, 'fraction_numerical': 0.0049569908149876074, 'mean_word_length': 2.091482649842271, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 51, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4420031', 'n_tokens_mistral': 2318, 'n_tokens_neox': 2260, 'n_words': 669}