重复动作的类型类直到定点

Question

我注意到执行动作的常见模式,直到它停止具有某些效果,当一个人知道这表示一个固定点时(即,没有未来的效果).这是一个类型类吗？

这是MonadFix所涵盖的吗？看着代码,它似乎会是,但我被维基页面吓到了"它很诱人看到"递归"并猜测它意味着递归或重复执行动作.不."

在我看来,固定点就像是身份的双重性.也就是说,当与非身份相结合时,身份会消失(0代表(+),1代表(*),[]代表追加等).而固定点导致任何非固定点在下面的"放松"操作下消失.有没有办法正式化这种二元性,这样做有用吗？即,MonadPlus和/或Monoid和MonadRelax之间是否存在关系？

最后,我注意到放松几乎是展开/变形.表达它会更好吗？

{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies #-}

import Control.Monad.Loops (iterateUntilM) -- cabal install monad-loops

-- states that relax to a fixed point under step
class Monad m => MonadRelax m s | s -> m where
isFixed :: s -> Bool
step :: s -> m s -- often (not always): step s = return s iff isFixed s

relax :: MonadRelax m s => s -> m s
relax = iterateUntilM isFixed step

Answer 1

你所要求的，实际上是一个简单的fix：

cd :: (Monad m) => Int -> Int -> m Int
cd = fix (\f c i -> if i == 0 then return c else f (c+i) (i-1))

这将重复计算，直到i变成 0。（我添加了c一个有意义的计算；但你可以假设s=(Int,Int)其中一个是滚动总和，另一个是计数器）

> cd 0 4 :: [Int]
[10]

这与：

relax = fix (\f s -> if isFix s then return s else f (step s))

我相信，这就是 的定义iterateUntilM。