[]的MonadFix实例

Question

该实例定义为

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

但是我没有理解它背后的直观含义,因为[]monad被视为非确定性计算.在mfix f功能f不能在它的参数严格,所以它无法检查的说法.并且根据定义,它也不能在其输出中的任何地方使用该参数,否则在某些时候它会受到影响fix (f . head)和分歧.那么列表是否有任何用途(或很好的例子)mfix,除了mfix (const someList)？

Answer 1

这样说可能是最简单的。f完全定义的函数mfix f是 的主干f x不依赖的函数x，因此它们可以写成以下形式

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

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

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

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

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