Haskell Cont monad如何以及爲何工作？

Question

這是續單子是如何定義的：

newtype Cont r a = Cont { runCont :: (a -> r) -> r } 

instance Monad (Cont r) where 
    return a = Cont ($ a) 
    m >>= k = Cont $ \c -> runCont m $ \a -> runCont (k a) c 

你能解釋一下如何以及爲什麼這個工程？它在做什麼？

Answer 1

關於延續monad的第一件事情是，從根本上說，它並不是真的做什麼都沒有。這是真的！

繼續的基本思想一般是它代表計算的其餘部分。假設我們有這樣一個表達式：foo (bar x y) z。現在，只提取括號內的部分，bar x y - 這是部分的總表達式，但它不僅僅是我們可以應用的函數。相反，這是我們需要應用功能到。因此，在這種情況下，我們可以談論「其餘計算」爲\a -> foo a z，我們可以將其應用於bar x y以重建完整的表單。

現在，這種「剩餘計算」的概念很有用，但是使用起來很尷尬，因爲它是我們正在考慮的子表達式之外的東西。爲了讓事情變得更好，我們可以將事情從內到外：提取我們感興趣的子表達式，然後將其包含在一個函數中，該函數接受一個表示其餘計算的參數：\k -> k (bar x y)。

這個修改後的版本給我們帶來了很大的靈活性 - 它不僅提取及其上下文的子表達式，但它讓我們操縱子表達式本身內外部環境。我們可以認爲它是一種暫停計算，給我們明確控制接下來會發生什麼。現在，我們怎麼概括這個？那麼，這個子表達式幾乎沒有改變，所以讓我們用一個參數替換它，然後給我們\x k -> k x--換句話說，只不過是功能應用，反轉。我們可以輕鬆地編寫flip ($)，或添加一些異國情調的外語風格，並將其定義爲運營商|>。

現在，將每一個表達片段翻譯成這種形式簡單，儘管繁瑣且令人生畏地混淆。幸運的是，還有更好的方法。作爲Haskell程序員，當我們認爲在後臺上下文中構建計算接下來我們認爲是說，這是一個單子嗎？而在這種情況下，答案是是的，是的。

要變成一個單子，我們開始具有兩個基本組成部分：

• 對於單子m，m a類型的值表示單子的範圍內具有訪問a類型的值。
• 我們的「暫停計算」的核心是翻轉函數應用程序。

在這種情況下訪問a類型的東西是什麼意思？這僅表示對於某些值x :: a，我們已應用flip ($)至x，給我們一個函數，該函數採用一個函數，該函數採用類型爲a的參數，並將該函數應用於x。假設我們有一個暫停的計算，其值爲Bool。這給了我們什麼類型？

> :t flip ($) True 
flip ($) True :: (Bool -> b) -> b 

所以對暫停計算，m a工程以(a -> b) -> b ...這也許是一個虎頭蛇尾的，因爲我們已經知道了簽名Cont對於現在的類型，但我的幽默。

一個有趣的事情，這裏要注意的是，一種「逆轉」也適用於單子的類型：Cont b a代表一個函數，函數a -> b和評估爲b。作爲延續表示計算的「未來」，因此簽名中的a代表某種意義上的「過去」。

因此，用Cont b a替換(a -> b) -> b，我們的反函數應用的基本構建塊的monadic類型是什麼？ a -> (a -> b) -> b轉換爲a -> Cont b a ...與return相同的類型簽名，實際上，這正是它的原因。

從這裏開始，一切都差不多從類型中去除了：除了實際的實現之外，基本上沒有明智的方法來實現>>=。但究竟是做？

在這一點上我們回到我剛纔說的話：延續單子並不是真的做什麼都沒有。 Cont r a類型的東西只是簡單地通過將id作爲參數提供給掛起的計算而簡單地等同於a類型的東西。這可能會導致人們詢問，如果Cont r a是一個monad但轉換是如此微不足道，不應該單獨a也成爲monad？當然，這不起作用，因爲沒有類型構造函數來定義爲Monad實例，但是說我們添加了一個簡單的包裝，如data Id a = Id a。這確實是一個monad，即身份monad。

>>=對身份monad做什麼？類型簽名是Id a -> (a -> Id b) -> Id b，相當於a -> (a -> b) -> b，這只是簡單的函數應用程序。確定Cont r a簡直等於Id a，我們可以推斷在這種情況下，(>>=)只是功能應用。

當然，Cont r a是一個瘋狂倒立的世界裏，每個人都有山羊鬍，所以實際發生周圍混淆的方式，以鏈上的兩個暫停的計算涉及到洗牌的東西放在一起進入一個新的暫停計算，但在本質上，ISN實際上什麼都不正常！將函數應用於參數，哼哼，功能程序員生活中的另一天。

Answer 2

編輯：文章遷移到下面的鏈接。

我已經寫了一個教程直接解決這個問題，我希望你會覺得有用。 （這當然有助於鞏固我的理解！）在堆棧溢出主題中放置一段時間太長了，所以我將它移植到了Haskell Wiki。

請參閱：MonadCont under the hood

Answer 3

這裏的斐波那契數：

fib 0 = 0 
fib 1 = 1 
fib n = fib (n-1) + fib (n-2) 

想象一下，你有一臺機器沒有調用棧 - 只允許尾遞歸。如何在該機器上執行fib？您可以輕鬆地將函數重寫爲線性工作，而不是指數時間，但這需要一點洞察力，而且不是機械的。

使其尾遞歸的障礙是第三行，其中有兩個遞歸調用。我們只能打一個電話，也必須給出結果。這裏是延續輸入的地方。

我們將fib (n-1)作爲附加參數，這是一個函數，指定在計算結果後應該做些什麼，稱之爲x。當然，它會增加。所以：要計算fib n那麼你在那之後計算fib (n-1)，如果你調用結果x，則計算，之後，如果你調用結果y，則返回x+y。

在你要告訴換句話說：

如何做好以下計算：「fib' n c =計算fib n和應用c到結果」？

答案是，你做了以下內容：「計算fib (n-1)和應用d的結果」，其中d x的意思是「計算和應用e的結果」，其中e y意味着c (x+y)。在代碼：

fib' 0 c = c 0 
fib' 1 c = c 1 
fib' n c = fib' (n-1) d 
      where d x = fib' (n-2) e 
       where e y = c (x+y) 

同樣地，我們可以使用lambda表達式：

fib' 0 = \c -> c 0 
fib' 1 = \c -> c 1 
fib' n = \c -> fib' (n-1) $ \x -> 
       fib' (n-2) $ \y -> 
       c (x+y) 

要獲得實際的斐波那契使用身份：fib' n id。您可以認爲行fib (n-1) $ ...將其結果x傳遞給下一個。

最後三行聞起來像do塊，而事實上

fib' 0 = return 0 
fib' 1 = return 1 
fib' n = do x <- fib' (n-1) 
      y <- fib' (n-2) 
      return (x+y) 

是一樣的，最多newtypes，由單子Cont的定義。注意差異。在開頭有\c ->，而不是x <- ...有... $ \x ->和c而不是return。

嘗試使用CPS以尾部遞歸樣式編寫factorial n = n * factorial (n-1)。

>>=如何工作？m >>= k相當於

do a <- m 
    t <- k a 
    return t 

使得翻譯回來，在相同的風格在fib'，你

\c -> m $ \a -> 
     k a $ \t -> 
     c t 

簡化\t -> c t到c

m >>= k = \c -> m $ \a -> k a c 

添加newtypes你

m >>= k = Cont $ \c -> runCont m $ \a -> runCont (k a) c 

這是在這個頁面的頂部。這很複雜，但如果您知道如何在do表示法和直接使用之間進行翻譯，則無需知道>>=的確切定義！如果你看看do-blocks，繼續單子更清晰。

單子和延續

如果你看看這個使用列表單子...

do x <- [10, 20] 
    y <- [3,5] 
    return (x+y) 

[10,20] >>= \x -> 
    [3,5] >>= \y -> 
    return (x+y) 

([10,20] >>=) $ \x -> 
    ([3,5] >>=) $ \y -> 
    return (x+y) 

，看起來像延續！實際上，當您應用一個參數時，（>> =）的類型爲(a -> m b) -> m b，即Cont (m b) a。有關說明，請參閱sigfpe的Mother of all monads。我認爲這是一個很好的繼續monad教程，儘管它不是這個意思。因爲continuations和monad在兩個方向上如此密切相關，我認爲適用於monad的適用於continuations：只有努力工作才能教會你，而不是閱讀一些捲餅比喻或類比。

Answer 4

我認爲掌握Cont monad最簡單的方法是瞭解如何使用它的構造函數。我要承擔現在下面定義，雖然transformers包的現實稍有不同：

newtype Cont r a = Cont { runCont :: (a -> r) -> r } 

這給：

Cont :: ((a -> r) -> r) -> Cont r a 

所以要建立Cont r a類型的值，我們需要給一個函數來Cont：

value = Cont $ \k -> ... 

現在，k本身的類型爲a -> r，並且lambda的主體需要具有類型r。一個顯而易見的做法是將k應用於類型爲a的值，並獲得類型r的值。我們可以這樣做，是的，但這只是我們可以做的許多事情之一。請記住value在r中不需要是多態，它可能是Cont String Integer或其他具體的類型。所以：

• 我們可以申請k於a類型的幾個值，並將結果以某種方式結合起來。
• 我們可以將k應用於類型爲a的值，觀察結果，然後決定將k應用於基於此的其他內容。
• 我們可以完全忽略k，只是自己產生一個類型r的值。

但這是什麼意思？ k最終會成爲什麼？那麼，在一個做塊，我們可能有一些看起來像這樣：

flip runCont id $ do 
    v <- thing1 
    thing2 v 
    x <- Cont $ \k -> ... 
    thing3 x 
    thing4 

這裏是最有趣的部分：我們可以在我們的腦海中，有點非正式的，兩個在的發生分裂做塊Cont的構造函數，並將作爲本身的值考慮整個計算的其餘部分。但是且慢，什麼是取決於什麼x是，所以這是一個真正的功能從值xa型的一些結果值：

restOfTheComputation x = do 
    thing3 x 
    thing4 

事實上，這restOfTheComputation是粗略地講什麼k結束了。換句話說，您呼叫k的值爲Cont計算的結果x，其餘計算運行，然後r產生的風返回到您的lambda中，作爲調用k的結果。所以：

• 如果您多次調用k，其餘計算將運行多次，並且結果可能會與您想要的結合。
• 如果您根本沒有撥打k，則整個計算的其餘部分將被跳過，並且封閉的runCont調用將返回您設法合成的r類型的值。也就是說，除非計算的其他部分正在呼籲你從他們k，並擺弄結果...

如果你還是跟我在這一點上應該很容易看到這可能是相當強大的。爲了說明這一點，我們來實現一些標準類型類。

instance Functor (Cont r) where 
    fmap f (Cont c) = Cont $ \k -> ... 

我們給予Cont值和綁定結果a型x和功能f :: a -> b，我們希望做一個Cont值與b類型的綁定結果f x。好了，設置綁定結果，只需調用k ...

fmap f (Cont c) = Cont $ \k -> k (f ... 

等待，我們在哪裏得到x而來？那麼，這將涉及我們尚未使用的c。記住c是如何工作的：它得到一個函數，然後用它的綁定結果調用該函數。我們想要我們的函數與f適用於該綁定結果。所以：

fmap f (Cont c) = Cont $ \k -> c (\x -> k (f x)) 

田田！接下來，Applicative：

instance Applicative (Cont r) where 
    pure x = Cont $ \k -> ... 

這一個簡單的。我們希望綁定結果是我們得到的x。

pure x = Cont $ \k -> k x 

現在，<*>：

Cont cf <*> Cont cx = Cont $ \k -> ... 

這有點麻煩，但本質上使用相同的想法，在FMAP：首先從第一Cont獲得的功能，通過使拉姆達爲它調用：

Cont cf <*> Cont cx = Cont $ \k -> cf (\fn -> ... 

然後從第二獲得的價值x，使fn x綁定結果：

Cont cf <*> Cont cx = Cont $ \k -> cf (\fn -> cx (\x -> k (fn x))) 

Monad是大同小異，雖然需要runCont或情況，或讓解壓NEWTYPE。

這個答案已經很長了，所以我不會進入ContT（簡而言之：它與Cont完全一樣！唯一的區別在於類型構造函數的種類，所有的實現都是相同的）或callCC（一種有用的組合子，提供了一種方便的方式來忽略k，實現從子塊中提前退出）。

對於一個簡單而合理的應用程序，試試Edward Z. Yang的博客文章labelled break and continue in for loops。