使用 State Monad 将我所有的函数变成 monadic 函数

Question

我在 Haskell 中编写了一个密码学库来学习密码学和 monad。（不是用于现实世界！）我的素数测试函数的类型是

prime :: (Integral a, Random a, RandomGen g) => a -> State g Bool

正如您所看到的，我使用了 State Monad，所以我不会一直让线程通过生成器。素数函数在内部使用依赖于随机数的 Miller-Rabin 测试，这就是素数函数也必须依赖于随机数的原因。这在某种程度上是有道理的，因为 prime 函数只进行概率测试。

仅供参考，下面是完整的prime函数，但我认为您不需要阅读。

-- | findDS n, for odd n, gives odd d and s >= 0 s.t. n=2^s*d.
findDS :: Integral a => a -> (a, a)
findDS n = findDS' (n-1) 0
  where
    findDS' q s
      | even q = findDS' (q `div` 2) (s+1)
      | odd  q = (q,s)

-- | millerRabinOnce n d s a does one MR round test on
-- n using a.
millerRabinOnce :: Integral a => a -> a -> a -> a -> Bool
millerRabinOnce n d s a
  | even n           = False
  | otherwise        = not (test1 && test2)
  where
    (d,s) = findDS n

    test1 = powerModulo a d n /= 1
    test2 = and $ map (\t -> powerModulo a ((2^t)*d) n /= n-1) 
                      [0..s-1]

-- | millerRabin k n does k MR rounds testing n for primality.
millerRabin :: (RandomGen g, Random a, Integral a) =>
  a -> a -> State g Bool
millerRabin k n = millerRabin' k
  where
    (d, s)          = findDS n
    millerRabin' 0 = return True
    millerRabin' k = do
      rest <- millerRabin' $ k - 1
      test <- randomR_st (1, n - 1)
      let this = millerRabinOnce n d s test
      return $ this && rest

-- | primeK k n. Probabilistic primality test of n
-- using k Miller-Rabin rounds.
primeK :: (Integral a, Random a, RandomGen g) => 
  a -> a -> State g Bool
primeK k n
  | n < 2            = return False
  | n == 2 || n == 3 = return True
  | otherwise        = millerRabin (min n k) n

-- | Probabilistic primality test with 64 Miller-Rabin rounds.
prime :: (Integral a, Random a, RandomGen g) => 
  a -> State g Bool
prime = primeK 64

问题是，在我需要使用素数的任何地方，我也必须将该函数转换为单子函数。即使它看起来不涉及任何随机性。例如，下面是我的 former 函数，用于恢复 Shamir 的秘密共享计划中的秘密。确定性操作，对吗？

recover :: Integral a => [a] -> [a] -> a -> a
recover pi_s si_s q = sum prods `mod` q
  where
    bi_s  = map (beta pi_s q) pi_s
    prods = zipWith (*) bi_s si_s

那时我使用了一个朴素的、确定性的素性测试函数。我还没有重写 recover 函数，但我已经知道 beta 函数依赖于素数，因此它和 recover 都会。两者都必须从简单的非单子函数变成两个单子函数，即使它们使用状态单子/随机性的原因确实很深。

我不禁认为所有代码都变得更加复杂，因为它必须是单子的。我是不是遗漏了什么，或者在 Haskell?

这样的情况下总是这样吗？

我能想到的一个解决方案是

prime' n = runState (prime n) (mkStdGen 123)

并改用 prime'。这个解决方案提出了两个问题。

这是个坏主意吗？我觉得不是很优雅
从单子代码到非单子代码的 "cut" 应该在哪里？因为我也有这样的函数 genPrime:

_

genPrime :: (RandomGen g, Random a, Integral a) => a -> State g a
genPrime b = do
  n  <- randomR_st (2^(b-1),2^b-1)
  ps <- filterM prime [n..]
  return $ head ps

问题变成了 "cut" 是在 genPrime 之前还是之后等等。

Answer 1

这确实是对 monad 的有效批评，因为它们在 Haskell 中实现。从短期来看，我没有看到比你提到的更好的解决方案，将所有代码切换为 monadic 风格可能是最健壮的，即使它们比自然风格更重量级，而且确实会很痛苦移植大型代码库，但如果您想添加更多外部效果，稍后可能会有所回报。

我认为代数效应可以优雅地解决这个问题，例如：

所有函数都用它们的效果注释 a -> eff b，但是，与 Haskell 相反，它们都可以像纯函数一样简单地组合 a -> b（因此是有效的功能，具有空的效果签名）。该语言然后确保效果形成半格，以便可以组合具有不同效果的函数。

Haskell好像很难有这样的系统。 Free(r) monads 库允许以类似的方式组合各种类型的效果，但仍然需要在术语级别明确的 monadic 样式。一个有趣的想法是重载函数应用程序，因此它可以隐式更改为 (>>=)，但我不知道这样做的原则性方法。主要问题是函数 a -> m b 既被视为在 m 和 codomain b 中具有效果的有效函数，又被视为具有 codomain m b 的纯函数。我们如何推断何时使用 ($) 或 (>>=)？

在随机性的特殊情况下，我曾经有一个涉及可拆分随机生成器（无耻插件）的有点相关的想法：https://blog.poisson.chat/posts/2017-03-04-splittable-generators.html

使用 State Monad 将我所有的函数变成 monadic 函数

Using State Monad turns all of my functions into monadic functions

monads

haskell

state-monad