6

实例定义为

instance MonadFix [] where
  mfix f = case fix (f . head) of
             []    -> []
             (x:_) -> x : mfix (tail . f)

[]但是对于被视为非确定性计算的单子，我无法理解其背后的直观含义。In mfix ffunctionf的参数不能严格，因此它不能检查参数。而且根据定义，它也不能在其输出中的任何地方使用该参数，否则在某些时候它会碰撞fix (f . head)和发散。那么对于列表还有什么用途（或很好的例子）mfix，除了mfix (const someList)？

4

2 回答 2

4

像这样说可能是最容易的。完全定义的函数f是的脊椎不依赖的函数，所以可以写成mfix ff xx

f x = [f1 x, ..., fn x]

对于一些n（可能是无穷大）和一些f1, ..., fn. 然后

mfix f = [fix f1, ..., fix fn]

（当然，要真正完全定义这一点，fix fi还必须定义每个）。

mfix可以被认为是非确定性地给你一个非确定性函数的不动点。相当严格的限制是非确定性计算的形状不能以任何方式依赖于输入。我们似乎需要对计算进行某种限制才能开始，但您可能希望至少能够有条件地终止计算的一个分支（例如，如果某个中间计算是否定的）。我一直认为应该可以mfix通过使用不同的非确定性单子来以这种方式使用，其选择操作不是关联的，但从未解决过细节。

于 2016-07-03T13:59:52.087 回答
0

如果您实际上将它们与严格的功能一起使用，所有fix变体都会出现问题，但那是在实际用例中通常不是问题† :a基本上总是一个函数类型，并且任何 lambda 都已经在 NF 中。

所以，至于具体用途......好吧，这里至少有一些收敛的东西：

f :: (Int -> Int) -> [Int -> Int]

f f' = [\x -> if x>0 then f' (x-1) * i else 1 | i<-[0..]]

f基本上生成一个幂函数列表。

GHCi> take 20 $ mfix f <*> [1,2] [0,0,1,1,2,4,3,9,4,16,5,25,6,36,7,49,8,64,9,81]

我不确定这实际上有什么用，但它确实有非常有趣的行为。

我刚刚注意到这是一个不好的例子，因为它实际上相当于一个fix (f . head). 嗯……

†您似乎很正确：在 的情况下这是一个问题a -> [a]，因为没有明显的方法可以使列表结构依赖于参数而不变得严格。

于 2016-07-03T11:39:06.187 回答