针对Cont的简化bind实现是否存在问题?
Cont类型简化bind实现的正确性验证
我为Cont类型实现了一份简化的bind操作,想确认是否存在问题,以下是我的实现代码:
{-# LANGUAGE RankNTypes #-} newtype C a = C {runCont :: forall r. (a -> r) -> r} instance Functor C where fmap f (C arr) = C $ \br -> arr $ br . f instance Applicative C where pure a = C ($ a) (C abrr) <*> (C arr) = C $ \brr -> abrr ( \ab -> arr ( brr . ab ) ) instance Monad C where -- (C arr) >>= aCbrr = C $ \br -> arr (\a -> runCont (aCbrr a) br) -- 常规实现 (C arr) >>= aCbrr = arr aCbrr -- 我的简化实现,测试结果和常规版本一致 main :: IO () main = print $ flip runCont id $ do x <- pure (5::Int) y <- pure $ 2 * x z <- pure $ take y $ repeat 'a' pure z
按照Noughtmare的建议,我补充了单子律的证明步骤,直觉上认为合理,但不确定这些步骤是否具备形式严谨性:
-- 左单位律: pure a >>= h === h a pure a >>= h C (\k -> k a) >>= h (\k -> k a) h h a -- 右单位律: m >>= pure === m m >>= pure C arr >>= pure arr pure arr ( \a -> C (\k -> k a) ) C ( \k -> k (arr id) ) -- 因为 arr 对 r 无依赖 C arr -- 因为 arr::(a->r)->r,k::a->r m -- 结合律: (m >>= f) >>= g === m >>= (\x -> f x >>= g) ((C arr) >>= f) >>= g === (C arr) >>= (\x -> f x >>= g) (arr f) >>= g f (arr id) >>= g (pure.h) (arr id) >>= g === (C arr) >>= (\x -> (pure.h) x >>= g) C (h (arr id)) >>= g === arr ( \x -> (C (h x)) >>= g ) === C (h (arr id)) >>= g
内容的提问来源于stack exchange,提问作者Adrian May
相关产品推荐
相关产品推荐

