是否有可能让` - =`使用文字？ [英] Is it possible to get `-=` working with literals?
问题描述
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
而$ i
ret * = i
i - = 1
return ret
使用 var = newSTRef ， def ， assert 和，而和
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其中
（+ =）:: l - > r - > m（）
（ - =）:: l - > r - > m（）
（* =）:: l - > r - > m（）
实例Num a => NumMod（STRef s a）（STRef s a）（ST s）其中
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 sa）a（ST s）其中
a + = b = modifySTRef a（（+）（b））
a - = b = modifySTRef a（（+）（negate b））
a * = b = modifySTRef a（（*）（b））
只要 factorial 返回一个整数。只要我将返回类型更改为其他内容，就会失败。我试着创建另一个实例。（b）b
$ b NumMod（STRef sa）b（ST s）其中
a + = b = modifySTRef a（（+）（fromIntegral $ b））
a - = b = modifySTRef a（（+）（negate。fromIntegral $ b））
a * = b = modifySTRef a（（*）（fromIntegral b））
由于重叠的实例而失败。
实际上是否可以创建一个适合的类型类和实例来获取 factorial 为任何<$ c $运行c> Integral a ？或者会出现这个问题？
STRef sa ，并使其成为 Num 的一个实例。 解决方案
首先，我们只需要一个编译指示：
<$ $ b $ import b
import Data.STRef（STRef，newSTRef，readSTRef，modifySTRef）
import Control.Monad（when）$ p $ { - ＃LANGUAGE RankNTypes＃ - }
import Control.Monad
import Control.Monad.ST（ST，runST）
<$ c $的包装c> STRef ：
data MyRef sa
= MySTRef（STRef sa） - 参考（可以修改）
| MyVal a - 纯粹的值（忽略修改）
实例Num a => Num（MyRef s a）其中
fromInteger = MyVal。 fromInteger
几个helper用于 MyRef STRef 函数：
newMyRef :: a - > ST s（MyRef s a）
newMyRef x = do
ref< - newSTRef x
return（MySTRef ref）
readMyRef :: MyRef s a - > ST sa
readMyRef（MySTRef x）= readSTRef x
readMyRef（MyVal x）= return x
我想用 - = helper： * = $ c> 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 fy）
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 ::（全部s ST（MyRef s a）） - > a
def m = runST $ m>> = readMyRef
while ::（Num a，Ord a）=> MyRef s a - > ST s（） - >当（n> 0）$ m>>时，ST s（）
当$ m $ go
时，
go = do
n< - readMyRef i
。 go
assert :: Monad m =>布尔 - >字符串 - > m（）
assert b str = when（not b）$ error str
factorial :: Integral a => a - > a
因子n = def $ do
assert（n> = 0）负因子
ret < - var 1
i < - var n
而我
ret * = i
i - = 1
返回ret
main :: IO（）
main = print。因子$ 1000
讨论
code> Num 这样的实例感觉有点不好意思，但是我们在Haskell中没有 FromInteger 类型类，所以我想它是OK。
另一个痒事是 3 * = 10 ，它是 return（）。我认为可以使用幻像类型来指示 MyRef 是否为 ST 或纯的，并且只允许 ST 在 alter 的LHS上。
Today I found this post on Quora, which claimed that
factorial(n) = def $ do
assert (n<=0) "Negative factorial"
ret <- var 1
i <- var n
while i $ do
ret *= i
i -= 1
return ret
could be correct Haskell code. I got curious, and ended up with
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
using var = newSTRef, canonical definitions for def, assert and while, and
a *= b = readSTRef b >>= \b -> modifySTRef a ((*) b)
a -= b = modifySTRef a ((+) (negate b))
However, (*=) and (-=) have different types:
(-=) :: Num a => STRef s a -> a -> ST s ()
(*=) :: Num a => STRef s a -> STRef s a -> ST s ()
So ret -= i wouldn't work. I've tried to create a fitting type class for this:
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))
That actually works, but only as long as factorial returns an Integer. As soon as I change the return type to something else it fails. I've tried to create another instance
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))
which fails due to overlapping instances.
Is it actually possible to create a fitting typeclass and instances to get the factorial running for any Integral a? Or will this problem always occur?
The idea
Idea is simple: wrap STRef s a in a new data type and make it an instance of Num.
Solution
First, we'll need only one pragma:
{-# LANGUAGE RankNTypes #-}
import Data.STRef (STRef, newSTRef, readSTRef, modifySTRef)
import Control.Monad (when)
import Control.Monad.ST (ST, runST)
Wrapper for 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
A few helpers for MyRef to resemble STRef functions:
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
I'd like to implement -= and *= using a bit more general alter helper:
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 (*)
Other functions are almost unchanged:
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
Discussion
Making Num instances like this feels a bit hacky, but we don't have FromInteger type class in Haskell, so I guess it's OK.
Another itchy thing is 3 *= 10 which is return (). I think it is possible to use phantom type to indicate whether MyRef is ST or pure and allow only ST on the LHS of alter.
这篇关于是否有可能让` - =`使用文字？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
