2

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

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''''使用绑定运算符进行操作。相反，它明确使用 fromJust （并假设fun1''''不是Nothing）。

在我的真实代码fun2中实际上调用了许多其他函数。这些其他函数不会与 相互递归fun2，并且可能会返回 Nothing 结果。幸运的是，我仍然可以在 do 表示法中隐式使用绑定运算符来访问其他必需的值。

4

4 回答 4

4

fun1'/fun2'不终止的原因是Maybemonad 的绑定操作 ( >>=) 需要检查第一个参数是Nothing还是Just (...)。所以当你做x <- fun1'in时fun2'，即使你不使用x，你仍然需要检查 if fun1'is Nothingor Just (...)（你不关心 (...)，它会被绑定到x你不使用的地方）。但要检查这一点，您需要知道 if fun2'is Justor Nothing，因为您在fun1'( b <- fun2') -> 无限递归中将 b 绑定到它的结果。

在第一种情况下不会发生同样的情况，因为在 中fun2，您不使用x，所以fun1永远不需要评估！

于 2014-07-12T13:56:21.750 回答
2

这里的问题是，您的终止函数fun1并不是互斥的，即使看起来是互斥的。事实上，您的fun2'函数实际上只是引用 value 2。例子：

λ> let x = undefined in 2
2

该undefined部分根本没有得到评估。因此，您x = fun1根本不会在您的fun2函数中进行评估，因此它成功终止，因为fun2评估为2.

而在您的fun2'示例中，它不会降低到任何值。所以，它不会终止。事实上，如果你真的fun2'像你的fun2例子一样把你的函数变成 let 表达式，那么它将终止：

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

fun2''是一个相互递归的函数，它指的是 value 2：

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

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

于 2014-07-12T13:50:42.203 回答
1

如果您需要将Maybemonad 与相互递归结合起来，那么也许您需要RecursiveDonotation，它允许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-12T21:04:09.347 回答
1

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

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

而是试试这个：

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

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

于 2014-07-12T14:07:21.827 回答