hjugement-protocol/tests/Utils.hs

   1 module Utils
   2  ( module Test.Tasty
   3  , module Data.Bool
   4  , Applicative(..)
   5  , Monad(..), forM, replicateM, unless, when
   6  , Eq(..)
   7  , Either(..), either, isLeft, isRight
   8  , ($), (.), id, const, flip
   9  , (<$>)
  10  , Int
  11  , Maybe(..)
  12  , Monoid(..), Semigroup(..)
  13  , Ord(..)
  14  , String
  15  , Text
  16  , Word8
  17  , Num, Fractional(..), Integral(..), Integer, fromIntegral
  18  , Show(..)
  19  , MonadTrans(..)
  20  , ExceptT
  21  , runExcept
  22  , throwE
  23  , StateT
  24  , evalStateT
  25  , mkStdGen
  26  , debug
  27  , nCk
  28  , combinOfRank
  29  ) where
  30
  31 import Control.Applicative (Applicative(..))
  32 import Control.Monad
  33 import Control.Monad.Trans.Class
  34 import Control.Monad.Trans.Except
  35 import Control.Monad.Trans.State.Strict
  36 import Data.Bool
  37 import Data.Either (Either(..), either, isLeft, isRight)
  38 import Data.Eq (Eq(..))
  39 import Data.Function
  40 import Data.Functor ((<$>))
  41 import Data.Int (Int)
  42 import Data.Maybe (Maybe(..))
  43 import Data.Monoid (Monoid(..))
  44 import Data.Ord (Ord(..))
  45 import Data.Semigroup (Semigroup(..))
  46 import Data.String (String)
  47 import Data.Text (Text)
  48 import Data.Word (Word8)
  49 import Debug.Trace
  50 import Prelude (Num(..), Fractional(..), Integral(..), Integer, undefined, fromIntegral)
  51 import System.Random (mkStdGen)
  52 import Test.Tasty
  53 import Text.Show (Show(..))
  54
  55 debug msg x = trace (msg<>": "<>show x) x
  56
  57 -- | @'nCk' n k@ returns the number of combinations
  58 -- of size 'k' from a set of size 'n'.
  59 --
  60 -- Computed using the formula:
  61 -- @'nCk' n (k+1) == 'nCk' n (k-1) * (n-k+1) / k@
  62 nCk :: Integral i => i -> i -> i
  63 n`nCk`k | n<0||k<0||n<k = undefined
  64         | otherwise     = go 1 1
  65         where
  66         go i acc = if k' < i then acc else go (i+1) (acc * (n-i+1) `div` i)
  67         -- Use a symmetry to compute over smaller numbers,
  68         -- which is more efficient and safer
  69         k' = if n`div`2 < k then n-k else k
  70
  71 -- | @'combinOfRank' n k r@ returns the @r@-th combination
  72 -- of @k@ elements from a set of @n@ elements.
  73 -- DOC: <http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf>, p.26
  74 combinOfRank :: Integral i => i -> i -> i -> [i]
  75 combinOfRank n k rk | rk<0||n`nCk`k<rk = undefined
  76                     | otherwise = for1K 1 1 rk
  77         where
  78         for1K i j r | i <  k    = uptoRank i j r
  79                     | i == k    = [j+r] -- because when i == k, nbCombs is always 1
  80                     | otherwise = []
  81         uptoRank i j r | nbCombs <- (n-j)`nCk`(k-i)
  82                        , nbCombs <= r = uptoRank i (j+1) (r-nbCombs)
  83                        | otherwise    = j : for1K (i+1) (j+1) r