type-level-prng (empty) → 0.1.0

raw patch · 8 files changed

+222/−0 lines, 8 filesdep +basedep +defun-core

Dependencies added: base, defun-core

Files

• CHANGELOG.md +4/−0
• LICENSE +20/−0
• README.md +17/−0
• src/Data/TypeLevel/PRNG/Common.hs +23/−0
• src/Data/TypeLevel/PRNG/LCG.hs +41/−0
• src/Data/TypeLevel/PRNG/Xorshift.hs +24/−0
• src/Raehik/GHC/TypeNats/Bits.hs +39/−0
• type-level-prng.cabal +54/−0

@@ -0,0 +1,4 @@+## 0.1.0 (2025-11-24)+Initial release.++* LCG, Xorshift PRNGs

@@ -0,0 +1,20 @@+Copyright (c) 2025 Ben Orchard (@raehik) <thefirstmuffinman@gmail.com>++Permission is hereby granted, free of charge, to any person obtaining+a copy of this software and associated documentation files (the+"Software"), to deal in the Software without restriction, including+without limitation the rights to use, copy, modify, merge, publish,+distribute, sublicense, and/or sell copies of the Software, and to+permit persons to whom the Software is furnished to do so, subject to+the following conditions:++The above copyright notice and this permission notice shall be included+in all copies or substantial portions of the Software.++THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,+EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF+MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.+IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY+CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,+TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE+SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

@@ -0,0 +1,17 @@+# type-level-prng+Type level pseudorandom number generators.+Ever wanted convenient access to randomness in your type-level Haskell programs?+Trick question, I don't care, you can now have it anyway.++Due to the specific limitations of GHC's opaque type-level natural numbers,+the PRNGs defined here have wildly different performance.+This library provides defunctionalized symbols, so that your+type-level programs can be parameterized on their PRNG implementation.++## Contributing+I would gladly accept further combinators or other suggestions. Please add an+issue or pull request, or contact me via email or whatever (I'm raehik+everywhere).++## License+Provided under the MIT license. See `LICENSE` for license text.

@@ -0,0 +1,23 @@+module Data.TypeLevel.PRNG.Common+  ( type PRNG, type SimplePRNG, type FromSimplePRNG+  ) where++import GHC.TypeNats ( type Natural )+import DeFun.Core ( type App, type (@@), type (~>) )++-- | A PRNG takes some state, and returns a new state and some random data.+--+-- The characteristics of the 'Natural' data returned are dependent on the PRNG.+type PRNG state = state ~> (state, Natural)++-- | A simple PRNG where the state is the previous output.+type SimplePRNG = Natural ~> Natural++-- | Turn a simple PRNG into a regular one.+type FromSimplePRNG :: SimplePRNG -> PRNG Natural+data FromSimplePRNG prng n+type instance App (FromSimplePRNG prng) n = Dup (prng @@ n)+-- @(prng @@ n, prng @@ n)@ probably re-does the computation, so.++type Dup :: a -> (a, a)+type Dup a = '(a, a)

@@ -0,0 +1,41 @@+{-# LANGUAGE UndecidableInstances #-}++-- | Linear congruential generators (and Lehmer RNGs).++module Data.TypeLevel.PRNG.LCG where++import Data.TypeLevel.PRNG.Common+import GHC.TypeNats+import DeFun.Core ( type App )++-- TODO are the constants re-calculated each usage?+-- should I calculate @2^31 - 1@ and insert manually? benchmark.++-- | Calculate the next term in a linear congruential generator.+--+-- The previous term is given in @n@.+type LCGNext :: Natural -> Natural -> Natural -> SimplePRNG+data LCGNext m a c n+type instance App (LCGNext m a c) n = (a * n + c) `Mod` m++-- | Knuth's MMIX RNG. An LCG.+--+-- As I understand, the bits have a period of 2^n where n is their bit position.+-- So the low bits have very low randomness: e.g. it flips between odd & even!+-- Consider only using the top 32 bits.+type MMIX = LCGNext (2^64) 6364136223846793005 1442695040888963407++-- | Calculate the next term in a Lehmer random number generator (a type of+--   linear congruential generator). A type of LCG.+--+-- The previous term is given in @n@.+--+-- Very few operations.+type LehmerNext :: Natural -> Natural -> SimplePRNG+data LehmerNext m a n+type instance App (LehmerNext m a) n = (a * n) `Mod` m++-- | minstd_rand from C++11. A Lehmer RNG.+--+-- Seems pretty good. Low bits aren't as low period like many other LCGs.+type MinstdRand = LehmerNext (2^31 - 1) 48271

@@ -0,0 +1,24 @@+{-# LANGUAGE UndecidableInstances #-}++-- | Xorshift PRNGs.++module Data.TypeLevel.PRNG.Xorshift where++import Data.TypeLevel.PRNG.Common+import GHC.TypeNats+import Raehik.GHC.TypeNats.Bits+import DeFun.Core ( type App )++-- tested a handful of iterations against Wikipedia C program+type Xorshift64 :: SimplePRNG+data Xorshift64 x+type instance App Xorshift64 x = Xorshift64_2 ((x `Xor` (x `ShiftL` 13)) `Mod` (2^64))+type Xorshift64_2 x =            Xorshift64_3  (x `Xor` (x `ShiftR` 7))+type Xorshift64_3 x =                          (x `Xor` (x `ShiftL` 17)) `Mod` (2^64)++-- Seems to be no faster than Xorshift64.+type Xorshift32 :: SimplePRNG+data Xorshift32 x+type instance App Xorshift32 x = Xorshift32_2 ((x `Xor` (x `ShiftL` 13)) `Mod` (2^32))+type Xorshift32_2 x =            Xorshift32_3  (x `Xor` (x `ShiftR` 17))+type Xorshift32_3 x =                          (x `Xor` (x `ShiftL` 5))  `Mod` (2^32)

@@ -0,0 +1,39 @@+{-# LANGUAGE UndecidableInstances #-}++-- | Type-level "Data.Bits" definitions, over GHC opaque type-level 'Natural's.++module Raehik.GHC.TypeNats.Bits where++import GHC.TypeNats+import GHC.TypeError qualified as TE++-- | Left shift.+type ShiftL x i = x * 2^i++-- | Logical right shift. (But these are nats, is arithmetic shiftR even diff??)+type ShiftR x i = x `Div` 2^i++-- | The exclusive or of the binary representation of two 'Natural's.+type Xor n m = XorLoop 1 0 n m++-- calculates one binary digit at a time, so should be O(log n) with value...+-- but with a very high constant factor (8 ops, 2 pattern matches).+-- I would love to compute this more efficiently!+type family XorLoop factor acc n m where+    XorLoop factor acc 0 0 = acc+    XorLoop factor acc n m =+      XorLoop+        (factor*2)+        (acc + factor * (((n `Mod` 2) `BitXor` (m `Mod` 2))))+        (n `Div` 2)+        (m `Div` 2)++-- | Exclusive or on two "bit" 'Natural's.+--+-- Both 'Natural's must be either 0 or 1, or it emits a type error.+type family BitXor n m where+    BitXor 0 0 = 0+    BitXor 0 1 = 1+    BitXor 1 0 = 1+    BitXor 1 1 = 0+    BitXor n m = TE.TypeError (TE.Text "BitXor: got non-bit Naturals")

@@ -0,0 +1,54 @@+cabal-version: 1.12++-- This file has been generated from package.yaml by hpack version 0.38.2.+--+-- see: https://github.com/sol/hpack++name:           type-level-prng+version:        0.1.0+synopsis:       Type level pseudorandom number generators+description:    Please see README.md.+category:       Types, Data+homepage:       https://github.com/raehik/type-level-prng#readme+bug-reports:    https://github.com/raehik/type-level-prng/issues+author:         Ben Orchard+maintainer:     Ben Orchard <thefirstmuffinman@gmail.com>+license:        MIT+license-file:   LICENSE+build-type:     Simple+tested-with:+    GHC==9.12+extra-source-files:+    README.md+    CHANGELOG.md++source-repository head+  type: git+  location: https://github.com/raehik/type-level-prng++library+  exposed-modules:+      Data.TypeLevel.PRNG.Common+      Data.TypeLevel.PRNG.LCG+      Data.TypeLevel.PRNG.Xorshift+      Raehik.GHC.TypeNats.Bits+  other-modules:+      Paths_type_level_prng+  hs-source-dirs:+      src+  default-extensions:+      LambdaCase+      NoStarIsType+      DerivingVia+      DeriveAnyClass+      GADTs+      RoleAnnotations+      DefaultSignatures+      TypeFamilies+      DataKinds+      MagicHash+  ghc-options: -fhide-source-paths -Wall+  build-depends:+      base >=4.18 && <5+    , defun-core ==0.1.*+  default-language: GHC2021