使用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來終止相互遞歸函數

回答

相關問題