haskell - 使用 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

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

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也会。两者都必须从简单的非 monadic 函数变成两个 monadic 函数，即使它们使用 State Monad/randomness 的原因确实很深。

我不禁认为所有代码都变得更加复杂，因为它必须是单子(monad)的。我是不是遗漏了什么，或者在 Haskell 中这样的情况下总是如此吗？

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

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

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

1. 这是个坏主意吗？我不认为它很优雅。
2. 从单子(monad)代码到非单子(monad)代码的“切割”应该在哪里？因为我也有这样的函数 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

问题变成了是否在 genPrime 等之前或之后进行“剪切”。

Answer 1

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

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

• eff ( example program with randomness )

• F*

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

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

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