module SomeFunctions
    (
    common,
    diff,
    merge,
    merge',
    groupOrd,
    nubOrd,
    legendreDePolignac,
    listPrimes,
    listNonPrimes,
    listPrimesLow,
    isPrime,
    listFirstPrimes,
    nPrime,
    primeFactors,
    primeFactors',
    numDiv,
    phi,
    listProducts,
    listNubProducts,
    listDiv,
    sumProductsList,
    listFib,
    nFib,
    listTriangNum,
    listPentNum,
    listHexNum,
    listFact,
    nFact,
    tartaLP,
    ) where


import Data.List

common::(Ord a)=>[a]->[a]->[a]
common xs [] = []
common [] ys = []
common xs@(x:xt) ys@(y:yt)
    |x<y  = common xt ys
    |x==y = x:common xt yt
    |x>y  = common xs yt

diff::(Ord a)=>[a]->[a]->[a]
diff xs [] = xs
diff [] ys = []
diff xs@(x:xt) ys@(y:yt)
    |x<y  = x:diff xt ys
    |x==y = diff xt yt
    |x>y  = diff xs yt

merge::(Ord a)=>[a]->[a]->[a]
merge xs [] = xs
merge [] ys = ys
merge xs@(x:xt) ys@(y:yt)
    |x<y  = x:merge xt ys
    |x==y = x:merge xt yt
    |x>y  = y:merge xs yt

merge'::(Ord a)=>[a]->[a]->[a]
merge' [] ys = ys
merge' xs [] = xs
merge' xs@(x:xt) ys@(y:yt)
    |x<y  = x:merge' xt ys
    |x==y = x:y:merge' xt yt
    |x>y  = y:merge' xs yt

groupOrd::(Ord a)=>[a]->[[a]]
groupOrd [] = []
groupOrd (x:xt) = f [x] xt
    where f xs [] = [xs]
          f xs (y:yt)
              |x==y      = f (x:xs) yt
              |otherwise = xs:groupOrd (y:yt)

nubOrd::(Ord a)=>[a]->[a]
nubOrd [] = []
nubOrd (x:xt) = x:(f xt)
    where f [] = []
          f (y:yt)
              |x==y      = f yt
              |otherwise = nubOrd (y:yt)

legendreDePolignac::Int->Int->Int
legendreDePolignac m n = f 0 n
    where f k n
            |n<m       = k
            |otherwise = f (k+(n`quot`m)) (n`quot`m)

listPrimes::[Int]
listNonPrimes::[Int]
listPrimes    = 2:3:5:7:(diff [9,11..] listNonPrimes) 
listNonPrimes = foldr1 f.map g.tail $listPrimes
    where f (x:xt) ys = x:(merge xt ys)
          g p         = [p*p,p*(p+2)..]

listPrimesLow::Int->[Int]
listPrimesLow n = takeWhile (<=n) listPrimes

isPrime::Int->Bool
isPrime n = n==(head.dropWhile (<n) $listPrimes)

listFirstPrimes::Int->[Int]
listFirstPrimes n = take n listPrimes

nPrime::Int->Int
nPrime n = listPrimes!!n

primeFactors::Int->[Int]
primeFactors n = f n listPrimes
    where f n (p:pt)
             |p*p>n      = [n]
             |n`rem`p/=0 = f n pt
             |otherwise  = p:f (n`quot`p) (p:pt)

primeFactors'::Int->[(Int,Int)]
primeFactors' n = map f.groupOrd.primeFactors $n
    where f (x:xt) = (x,1+length xt)

numDiv::Int->Int
numDiv n = product.map (\xs->1+length xs).groupOrd.primeFactors $n

phi::Int->Int
phi 1 = 1
phi n = product.map (\(x:xt)->x^(1+length xt)-x^(length xt)).groupOrd.primeFactors $n

listProducts::[Int]->[Int]
listProducts'::[Int]->[Int]->[Int]
listProducts xs = listProducts' [] xs
listProducts' ys [] = ys
listProducts' ys (x:xt) = listProducts' (f ys x) xt
    where f [] x = [x]
          f (y:yt) x = y:(y*x):(f yt x)

listNubProducts::[Int]->[Int]
listNubProducts'::[Int]->[Int]->[Int]
listNubProducts xs = listNubProducts' [] xs
listNubProducts' ys [] = ys
listNubProducts' ys (x:xt) = listNubProducts' (nub.f ys $x) xt
    where f [] x = [x]
          f (y:yt) x = y:(y*x):(f yt x)

listDiv::Int->[Int]
listDiv 0 = []
listDiv n = (1:).listNubProducts.primeFactors $n

sumProductsList::[Int]->Int
sumProductsList xs = foldl1' (\acc x->acc*(x+1)) $xs

listFib::[Int]
listFib = 0:1:(zipWith (+) listFib $tail listFib)

nFib::Int->Int
nFib n = listFib!!n

listTriangNum::[Int]
listTriangNum = scanl1 (+) [1..]

listPentNum::[Int]
listPentNum = scanl1 (+) [1,4..]

listHexNum::[Int]
listHexNum = scanl1 (+) [1,5..]

listFact::[Integer]
listFact = scanl (*) 1 [1..]

nFact::Int->Integer
nFact n = listFact!!n

tartaLP::Int->Int->Integer
tartaLP l p = (nFact l)`quot`((nFact p)*(nFact $l-p))
