-- | Miscelleanous auxilary functions

{-# LANGUAGE BangPatterns #-}
module Math.FiniteField.Misc where

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

import Data.List
import Data.Word

--------------------------------------------------------------------------------
-- * pairs

swap :: (a,b) -> (b,a)
swap :: (a, b) -> (b, a)
swap (a
x,b
y) = (b
y,a
x)

pairs :: [a] -> [(a,a)]
pairs :: [a] -> [(a, a)]
pairs = [a] -> [(a, a)]
forall b. [b] -> [(b, b)]
go where
  go :: [b] -> [(b, b)]
go (b
x:xs :: [b]
xs@(b
y:[b]
_)) = (b
x,b
y) (b, b) -> [(b, b)] -> [(b, b)]
forall a. a -> [a] -> [a]
: [b] -> [(b, b)]
go [b]
xs
  go [b]
_            = []

pairsWith :: (a -> a -> b) -> [a] -> [b]
pairsWith :: (a -> a -> b) -> [a] -> [b]
pairsWith a -> a -> b
f = [a] -> [b]
go where
  go :: [a] -> [b]
go (a
x:xs :: [a]
xs@(a
y:[a]
_)) = a -> a -> b
f a
x a
y b -> [b] -> [b]
forall a. a -> [a] -> [a]
: [a] -> [b]
go [a]
xs
  go [a]
_            = []

--------------------------------------------------------------------------------
-- * lists

longZipWith :: a -> b -> (a -> b -> c) -> [a] -> [b] -> [c]
longZipWith :: a -> b -> (a -> b -> c) -> [a] -> [b] -> [c]
longZipWith !a
x0 !b
y0 !a -> b -> c
f = [a] -> [b] -> [c]
go where
  go :: [a] -> [b] -> [c]
go (a
x:[a]
xs) (b
y:[b]
ys) = a -> b -> c
f a
x  b
y  c -> [c] -> [c]
forall a. a -> [a] -> [a]
: [a] -> [b] -> [c]
go [a]
xs [b]
ys
  go []     (b
y:[b]
ys) = a -> b -> c
f a
x0 b
y  c -> [c] -> [c]
forall a. a -> [a] -> [a]
: [a] -> [b] -> [c]
go [] [b]
ys
  go (a
x:[a]
xs) []     = a -> b -> c
f a
x  b
y0 c -> [c] -> [c]
forall a. a -> [a] -> [a]
: [a] -> [b] -> [c]
go [a]
xs []
  go [a]
_      [b]
_      = []

{-# SPECIALIZE sum' :: [Int]     -> Int     #-}
{-# SPECIALIZE sum' :: [Integer] -> Integer #-}
sum' :: Num a => [a] -> a
sum' :: [a] -> a
sum' = (a -> a -> a) -> a -> [a] -> a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' a -> a -> a
forall a. Num a => a -> a -> a
(+) a
0

interleave :: [a] -> [a] -> [a]
interleave :: [a] -> [a] -> [a]
interleave (a
x:[a]
xs) (a
y:[a]
ys) = a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: a
y a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
interleave [a]
xs [a]
ys
interleave [a
x]    []     = a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: []
interleave []     []     = []
interleave [a]
_      [a]
_      = [Char] -> [a]
forall a. HasCallStack => [Char] -> a
error [Char]
"interleave: shouldn't happen"

evens, odds :: [a] -> [a] 
evens :: [a] -> [a]
evens (a
x:[a]
xs) = a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a]
forall a. [a] -> [a]
odds [a]
xs
evens [] = []
odds :: [a] -> [a]
odds (a
x:[a]
xs) = [a] -> [a]
forall a. [a] -> [a]
evens [a]
xs
odds [] = []

--------------------------------------------------------------------------------
-- * tuples

-- | \"Tuples\" fitting into a give shape. The order is lexicographic, that is,
--
-- > sort ts == ts where ts = tuples' shape
--
--   Example: 
--
-- > tuples' [2,3] = 
-- >   [[0,0],[0,1],[0,2],[0,3],[1,0],[1,1],[1,2],[1,3],[2,0],[2,1],[2,2],[2,3]]
--
tuples' :: [Int] -> [[Int]]
tuples' :: [Int] -> [[Int]]
tuples' [] = [[]]
tuples' (Int
s:[Int]
ss) = [ Int
xInt -> [Int] -> [Int]
forall a. a -> [a] -> [a]
:[Int]
xs | Int
x <- [Int
0..Int
s] , [Int]
xs <- [Int] -> [[Int]]
tuples' [Int]
ss ] 

word32Tuples' :: [Word32] -> [[Word32]]
word32Tuples' :: [Word32] -> [[Word32]]
word32Tuples' [] = [[]]
word32Tuples' (Word32
s:[Word32]
ss) = [ Word32
xWord32 -> [Word32] -> [Word32]
forall a. a -> [a] -> [a]
:[Word32]
xs | Word32
x <- [Word32
0..Word32
s] , [Word32]
xs <- [Word32] -> [[Word32]]
word32Tuples' [Word32]
ss ] 

-- | positive \"tuples\" fitting into a give shape.
tuples1' :: [Int] -> [[Int]]
tuples1' :: [Int] -> [[Int]]
tuples1' [] = [[]]
tuples1' (Int
s:[Int]
ss) = [ Int
xInt -> [Int] -> [Int]
forall a. a -> [a] -> [a]
:[Int]
xs | Int
x <- [Int
1..Int
s] , [Int]
xs <- [Int] -> [[Int]]
tuples1' [Int]
ss ]

tuples 
  :: Int    -- ^ length (width)
  -> Int    -- ^ maximum (height)
  -> [[Int]]
tuples :: Int -> Int -> [[Int]]
tuples Int
len Int
k = [Int] -> [[Int]]
tuples' (Int -> Int -> [Int]
forall a. Int -> a -> [a]
replicate Int
len Int
k)

tuples1 
  :: Int    -- ^ length (width)
  -> Int    -- ^ maximum (height)
  -> [[Int]]
tuples1 :: Int -> Int -> [[Int]]
tuples1 Int
len Int
k = [Int] -> [[Int]]
tuples1' (Int -> Int -> [Int]
forall a. Int -> a -> [a]
replicate Int
len Int
k)

--------------------------------------------------------------------------------
-- * products

-- | Product of list of integers, but in interleaved order (for a list of big numbers,
-- it should be faster than the linear order)
productInterleaved :: [Integer] -> Integer
productInterleaved :: [Integer] -> Integer
productInterleaved = [Integer] -> Integer
forall a. Num a => [a] -> a
go where
  go :: [a] -> a
go []    = a
1
  go [a
x]   = a
x
  go [a
x,a
y] = a
xa -> a -> a
forall a. Num a => a -> a -> a
*a
y
  go [a]
list  = [a] -> a
go ([a] -> [a]
forall a. [a] -> [a]
evens [a]
list) a -> a -> a
forall a. Num a => a -> a -> a
* [a] -> a
go ([a] -> [a]
forall a. [a] -> [a]
odds [a]
list)

--------------------------------------------------------------------------------
-- * words

w32toW64 :: Word32 -> Word64
w32toW64 :: Word32 -> Word64
w32toW64 = Word32 -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral

w64toW32 :: Word64 -> Word32
w64toW32 :: Word64 -> Word32
w64toW32 = Word64 -> Word32
forall a b. (Integral a, Num b) => a -> b
fromIntegral

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