有可能让` - =`与文字一起工作吗？

Question

今天我在Quora上发现了这篇帖子,声称这一点

factorial(n) = def $ do    
    assert (n<=0) "Negative factorial"    
    ret <- var 1    
    i <- var n    
    while i $ do    
        ret *= i    
        i -= 1
    return ret

可能是正确的Haskell代码.我好奇,最后得到了

factorial :: Integer -> Integer
factorial n = def $ do
  assert (n >= 0) "Negative factorial"
  ret <- var 1
  i   <- var n
  while i $ do
      ret *= i
      i   -= 1
  return ret

使用var = newSTRef,规范定义def,assert和while,和

a *= b = readSTRef b >>= \b -> modifySTRef a ((*) b)
a -= b = modifySTRef a ((+) (negate b))

然而,(*=)和(-=)有不同的类型:

(-=) :: Num a => STRef s a -> a -> ST s ()
(*=) :: Num a => STRef s a -> STRef s a -> ST s ()

所以ret -= i不行.我试图为此创建一个拟合类型:

class (Monad m) => NumMod l r m where
  (+=) :: l -> r -> m ()
  (-=) :: l -> r -> m ()
  (*=) :: l -> r -> m ()

instance Num a => NumMod (STRef s a) (STRef s a) (ST s) where
  a += b    = readSTRef b >>= \b -> modifySTRef a ((+) b)
  a -= b    = readSTRef b >>= \b -> modifySTRef a ((+) (negate b))
  a *= b    = readSTRef b >>= \b -> modifySTRef a ((*) b)

instance (Num a) => NumMod (STRef s a) a (ST s) where
  a += b    = modifySTRef a ((+) (b))
  a -= b    = modifySTRef a ((+) (negate b))
  a *= b    = modifySTRef a ((*) (b))

这实际上有效,但只要factorial返回一个Integer.一旦我将返回类型更改为其他类型,它就会失败.我试图创建另一个实例

instance (Num a, Integral b) => NumMod (STRef s a) b (ST s) where
  a += b    = modifySTRef a ((+) (fromIntegral $ b))
  a -= b    = modifySTRef a ((+) (negate . fromIntegral $ b))
  a *= b    = modifySTRef a ((*) (fromIntegral b))

由于实例重叠而失败.

实际上是否可以创建一个适合的类型类和实例来factorial运行任何Integral a？或者这个问题总会发生吗？

Answer 1

这个想法

想法很简单:包装STRef s a一个新的数据类型并使其成为一个实例Num.

解

首先,我们只需要一个pragma:

{-# LANGUAGE RankNTypes #-}

import Data.STRef    (STRef, newSTRef, readSTRef, modifySTRef)
import Control.Monad (when)
import Control.Monad.ST (ST, runST)

包装STRef:

data MyRef s a
  = MySTRef (STRef s a)  -- reference (can modify)
  | MyVal a              -- pure value (modifications are ignored)

instance Num a => Num (MyRef s a) where
  fromInteger = MyVal . fromInteger

一些MyRef类似STRef功能的助手:

newMyRef :: a -> ST s (MyRef s a)
newMyRef x = do
  ref <- newSTRef x
  return (MySTRef ref)

readMyRef :: MyRef s a -> ST s a
readMyRef (MySTRef x) = readSTRef x
readMyRef (MyVal   x) = return x

我想实现-=并*=使用更一般的alter帮助器:

alter :: (a -> a -> a) -> MyRef s a -> MyRef s a -> ST s ()
alter f (MySTRef x) (MySTRef y) = readSTRef y >>= modifySTRef x . flip f
alter f (MySTRef x) (MyVal   y) = modifySTRef x (flip f y)
alter _ _ _ = return ()

(-=) :: Num a => MyRef s a -> MyRef s a -> ST s ()
(-=) = alter (-)

(*=) :: Num a => MyRef s a -> MyRef s a -> ST s ()
(*=) = alter (*)

其他功能几乎没有变化:

var :: a -> ST s (MyRef s a)
var = newMyRef

def :: (forall s. ST s (MyRef s a)) -> a
def m = runST $ m >>= readMyRef

while :: (Num a, Ord a) => MyRef s a -> ST s () -> ST s ()
while i m = go
  where
    go = do
      n <- readMyRef i
      when (n > 0) $ m >> go

assert :: Monad m => Bool -> String -> m ()
assert b str = when (not b) $ error str

factorial :: Integral a => a -> a
factorial n = def $ do
    assert (n >= 0) "Negative factorial"
    ret <- var 1
    i   <- var n
    while i $ do
      ret *= i
      i -= 1
    return ret

main :: IO ()
main = print . factorial $ 1000

讨论

制作这样的Num实例感觉有点hacky,但是我们FromInteger在Haskell中没有类型类,所以我猜它没关系.

另一个痒的事3 *= 10是return ().我认为有可能使用幻像类型来表示MyRef是ST纯还是纯,只允许ST在LHS上alter.