使用Maybe monad来终止相互递归函数

下面是两个互相递归函数对的例子。第一个示例终止并产生预期的结果。第二个例子是类似的，除了它使用Maybe monad。 fun1'在被调用时不会终止。使用Maybe monad来终止相互递归函数

fun1 = 1 + fun2 
fun2 = let x = fun1 
     in 2 
-- terminates. result is 3. 

fun1' = do a <- Just 1 
      b <- fun2' 
      return $ a + b 
fun2' = do x <- fun1' 
      return 2 
-- does not terminate.

这里是另外两个例子。再次，第一个示例终止于预期结果，第二个示例（使用Maybe monad）不终止。

fun1'' = fun2'' : [1] 
fun2'' = (head . tail $ fun1'') + 1 
-- terminates. result is [2,1] 

fun1''' = do a <- Just [1] 
      b <- fun2''' 
      return $ b : a    
fun2''' = do x <- fun1''' 
      return $ (head . tail $ x) + 1 
-- does not terminate.

我相信我有一种情况，在语义上类似于我的真实代码中的最后一个例子。我的选择是什么让它终止？我会被迫放弃Maybe monad吗？

更新这是我最终使用的解决方案;

fun1'''' = do a <- Just [1] 
       b <- fun2'''' 
       return $ b : a 
fun2'''' = do return $ (head . tail . fromJust $ fun1'''') + 1 
-- terminates :)

的关键区别是fun2''''不再fun1''''使用bind操作者操作。相反，它明确使用fromJust（并假定fun1''''不是Nothing）。

在我的真实代码fun2实际上调用了一些其他功能。这些其他函数与fun2不相互递归，并且可能会返回Nothing结果。幸运的是，我仍然可以在符号中隐式使用bind运算符来访问其他所需的值。

来源

2014-07-12 knick

这里的问题是您的终止函数fun1并不相互排斥，即使这似乎是。事实上，您的fun2'函数实际上只是指值2。示例：

λ> let x = undefined in 2 
2

undefined零件根本没有得到评估。因此，您的x = fun1根本不会在您的fun2函数中进行评估，因此它会成功终止，因为fun2的计算结果为2。

而在您的fun2'示例中，它不会降低到任何值。所以，它不会终止。逸岸，如果你真的把你的fun2'功能为让表情就像你fun2例如那么它将终止：

fun2' = let x = fun1' 
     in (Just 2)

fun2''是一个相互递归函数是指重视2：

λ> tail fun1'' 
[1] 
λ> head $ tail fun1'' 
1 
λ> (head $ tail fun1'') + 1 
2

所以fun2''实际上是指价值2。

来源

2014-07-12 13:50:42 Sibi

好吧，我明白你说的fun1/fun2实际上并不是相互递归的。这很有意义，因为fun1实际上并不需要使用fun2来产生结果。但是，我会认为fun1'/ fun2'可以被认为是相互递归的，因为如果没有其他的结果，它们都不会产生结果。 – knick

@knick是的，你是对的。适当更新它。 – Sibi

是fun1'/fun2'不终止的原因是Maybe单子的绑定操作（>>=）需要检查的第一个参数是Nothing或者如果它是Just (...)。所以当你做x <- fun1'在fun2'，即使你不使用x，你仍然需要检查是否fun1'是Nothing或Just (...)（你不关心（...），它将被绑定到x，您不会使用它）。但要检查，你需要知道fun2'是Just还是Nothing，因为你绑定b的结果是fun1'（b <- fun2'） - >无限递归。

在第一种情况下也不会发生这种情况，因为在fun2中，您不使用x，所以fun1从不需要评估！

来源

2014-07-12 13:56:21 bennofs

我想你别无选择，只能放弃Maybe monad。

请记住，单子表示可以链接在一起的计算序列。 monad代表可能失败的计算，并且当序列中的某个计算失败时，最后我们得到一个Nothing。尽管看起来像x的值不是必需的（因此我们预计由于惰性评估而导致程序暂停），但它是按顺序排列的，因此必须对其进行评估，从而导致无限递归。

相反试试这个：

fun1' = do a <- Just 1 
      b <- fun2' 
      return $ a + b 
fun2' = do Nothing 
      fun1' 
      return 2 
main = print $ fun1'

这会停止，因为，在Nothing将绕过所有其他计算。

来源

2014-07-12 14:07:21 Priyatham

如果你有需要的Maybe单子与相互递归合并，那么也许你想RecursiveDo notation，它允许monadically计算的mdo块递归地称呼对方（对于单子支持MonadFix类）内的值。以下内容编译并给出您可能期望的结果Just ([2,1],2)。

{-# LANGUAGE RecursiveDo #-} 

maybeFuns = mdo 
    fun1''' <- do a <- Just [1] 
        return $ fun2''' : a    
    fun2''' <- return $ (head . tail $ fun1''') + 1 
    return (fun1''', fun2''')

你需要一个mdo块来定义它，而不是作为独立的功能，虽然。虽然你可能取代maybeFuns =由Just (fun1''', fun2''') =如果你不在乎如果某个部分评估为Nothing得到一个错误。

来源

2014-07-12 21:04:09

使用Maybe monad来终止相互递归函数

回答

相关问题