haskell 怎麼實現惰性求值

yhz515 贡献于2016-03-16

作者 acer01  创建于2016-03-15 22:03:00   修改者acer01  修改于2016-03-15 22:31:00字数12314

文档摘要:在這個教程裡,我想解釋一下惰性求值的實現原理,並講清楚 Haskell 的惰性求值在時間和空間上的佔用情況。我會先講一些關於圖規約(Graph Reduction)基礎,然後討論一下關於嚴格(Strict)的左褶疊(Left Fold),用於幫助理解內存空間洩漏問題並解決之。
关键词:

翻譯:Haskell 怎麼實現惰性求值 NOV 24TH, 2014 原文由 Heinrich Apfelmus 發表於 Hackhands,標題:How Lazy Evaluatoin Works in Haskell。 Lambda 醬想遲些再去打掃房間~ 惰性求值是 Haskell 用得最廣泛的代碼執行方法,通過之我們的程序可以寫得更簡單,更模塊化,不過惰性求值帶來的一個問題是不那麼直觀內存佔用,對新手來講這往往是個坑。譬如說,下面這個看起來很正常的表達式跑起來將會佔用上 G 的內存空間: 1 foldl (+) 0 [1..10^8] 在這個教程裡,我想解釋一下惰性求值的實現原理,並講清楚 Haskell 的惰性求值在時間和空間上的佔用情況。我會先講一些關於圖規約(Graph Reduction)基礎,然後討論一下關於嚴格(Strict)的左褶疊(Left Fold),用於幫助理解內存空間洩漏問題並解決之。 惰性求值相關的主題在很多教科書裡都有涉及,譬如 Simon Thompson 的《Haskell – The Craft of Functional Programming》一書,但是線上版本似乎不太容易找。但願這篇教程能夠起到些幫助作用吧。 惰性求值是一個需要權衡的語言特性。一方面,它能使代碼更模塊化。(很遺憾,這次我沒有時間演示這個作用。)另一方面,它使得我們無法完全理解在任一程序中求值的過程 – 它的確比你想像要難一些。在本文末尾,我會提供一些對付這種情況的方法。我們開始吧! 基礎:圖規約 表達式,圖,和 Redex Haskell 程式的執行就是求值表達式。這是函數式應用(Function Application)的主要思想。對於下面這個函數定義: 1 square x = x*x 我們可以對下面的表達式求值: 1 square (1+2) 方式是通過替換左手邊的square為其定義,然後將變量x換成實際參數: 1 2 square (1+2) => (1+2)*(1+2) 再對+和*這兩個函數求值: 1 2 3 4 (1+2)*(1+2) => 3*(1+2) => 3*3 => 9 注意,在這個例子裡,(1+2) 被求值了兩次。但事實上我們知道,兩個(1+2)其實是一樣的。因為他們都對應同一個函數參數x。 為了避免這種重複的求值,我們採用一個叫作圖規約(Graph Reduction)的方法。用這種方法,每個表達式將會被表示為一個圖。我們的例子這樣表示: 每個方塊對應一個函數式應用,函數名字寫在白色的區域,灰色區域指向函數參數。事實上,這種圖的標記法類似於編譯器在內存中通過指針來表示的表達式。 每個程序員定義的函數都對應一個規約規則(Reduction Rule)。對square函數而言,規則如下: 標記著x的圓圈是一個子圖的佔位符。注意*函數的兩個參數都指向同一個子圖。這種共享子圖的策略是避免重複求值的關鍵所在。 有規約規則的子圖被稱為可規約表達式(Reducible Expression),或者簡單稱之 redex。只要我們有一個 redex,我們就能規約(Reduce)之,只要根據規約規則去改變高亮的方塊就行了。在我們的例子裡,我們有兩個 redex:我們能夠規約square函數和+函數。 我們先規約square函數的 redex,然後進一步規約+函數的 redex,得到這樣一個過程: 每一個步驟,我們都給正在要規約的 redex 加上顏色。在倒數第二個步驟中,產生了一個新的對應著*函數的 redex。對之求值,我們會得到最終的結果9。 模範式和弱首模範式 當一個表達式(圖)不包含任何 redex 時,我們就不能再進一步規約下去了,所以規約就完成了。這時,我們就稱這個表達式為規範式(Normal form),這就是求值的最終結果。在上面的例子裡,規範式是一個數字,表示為下面這樣的一個圖: 但是像Just,Nothing這樣的構建子,又如:和[]這種列表的構建子都會規約出模範式,他們看起來像是函數,但是他們是通過data聲明的,而且不存在像函數一樣的定義,所以他們沒有進一步規約規則。譬如說,圖: 就是1:2:3:[]的模範式。 事實上,一個圖要被稱為模範式還必須滿足另外兩個條件:它必須是有窮的(Finite),而且不能包含循迴結構(No Cyles)。有時遞歸就會照成這種情況。舉例來說,下面的表達式定義: 1 ones = 1 : ones 就對應這樣的循迴圖(Cyclic Graph): 這個圖就不包含 redex,但它卻不是模範式,因為它包含循迴結構:列表的尾(Tail)指向列表自身,以至於這個列表是無窮的。正如這樣,很多表達式並沒有模範式,因為他們對應無窮循環。 在 Haskell,我們並不會求值所有表達式至其模範式。相反,我們常常會在圖達到弱首模範式(Weak Head Normal Form)時就停下來,為了簡略,我們稱弱首模範式為 WHNF。只要一個圖的最上級節點是構建子,我們就稱之為 WHNF。譬如說,表達式(7+12):[],或者圖 就屬於 WHNF,因為它最上級的節點是列表構件子(:)。它並非模範式,因為它的第一個參數包含一個 redex。 另一方面,任何不屬於 WHNF 的圖都可以被稱作待求值表達式(Unevaluated Expression)或者次程式(Thunk)。以構建子開頭的表達式都是 WHNF,但這個構建子的參數可以是待求值表達式。 上面描述的表達式 ones 是一個有趣的 WHNF 圖。畢竟它的最上級節點是一個構建子。在 Haskell 中,我們能輕鬆表達無窮列表並操縱之!因而我們可以使代碼變得更模塊化。 求值順序,惰性求值 一個表達式常常包括多個 redex,我們以不同的順序規約他們會有區別嗎? 一種規約順序,我們稱之為貪婪求值(Eager Evaluation)。依這種順序,我們會先對函數式應用的每個參數都規約到其規範式,然後再規約函數式應用本身。這種策略是大多數程式語言所採用的。 然而 Haskell 編譯器採用另一種規約順序,我們稱之惰性求值(Lazy Evaluation)。惰性求值會先規約最上級的函數式應用,因而,最終一些參數會被求值,只有在必要的時候他們才會被求值。函數是通過構建子模式匹配(Pattern Matching)來定義的,所以其參數只有在其最上級節點為構造子時才會被求值。也就是說,至少在參數被規約為 WHNF 之前,這些參數會由左至右被求值。 希望這個概念能通過下面的例子闡述清楚。讓我們想像一下(&&)函數,這個函數的作用是實現邏輯「與」的操作。它的定義如下: 1 2 3 (&&) :: Bool -> Bool -> Bool True && x = x False && x = False 根據第一個參數是True還是False,這個函數會有兩種求值規則:   現在,再看此表達式: 1 ('H' == 'i') && ('a' == 'm') 圖的形式表示如下: 它的兩個參數都是 redex,惰性求值將會從左到右求值參數,所以我們從左邊開始規約: 現在,因為最左邊的函數變成了一個 redex,因為它的第一個參數現在成了一個構造式。惰性求值總是會先規約最上級節點,所以我們就這麼做。根據(&&)的規約規則,我們會得到: 這個表達式屬於模範式,所以我們的求值就完成了! 注意,當我們儘可能先求值(&&)的函數式應用時,我們就不再需要求值第二個參數了,以此節省我們計算所需的時間。有些命令式程式語言也用了類似的技巧,叫作「短路求值」(Short-circuit Evaluation)。不過這種短路求值一般被編譯器內部實現,而且只對邏輯操作有效。但在 Haskell 裡,所有函數都能從懶惰求值裡實現到這樣的效果。 一般而言,惰性求值一個表達式得到的最終的模範式和對其貪婪求值得到的結果沒有任何區別。因此我們可以說,不同求值順序並不會關係。然而,惰性求值會因而有更少的求值步驟,而且不像貪婪求值,惰性求值還能處理帶循迴(無窮)的圖。 文字表示法 但願把表達式可視化地表示圖能幫你理解惰性求值的基礎,更特別的是因為圖的形式能夠明確表示 redex 的概念和求值順序的重要性。然而,在實際的計算中,畫圖表示 是有點太肥了。要追蹤規約,我們一般用 Haskell 語法的文字表示法(Textual Representation)來表達。 圖令得我們可以清晰看到共享子圖。在文字表示法裡,我們會給他們用let關鍵字來命名,譬如說,在我們第一個例子裡的square (1+2)的規約可以寫為: 1 2 3 4 square (1+2) => let x = (1+2) in x*x => let x = 3 in x*x => 9 let ... in 語法使我們可以共享子表達式(Subexpression)x = (1+2)。再次注意square是被先規約的,然後才是其參數x。 在我們第二個例子裡,邏輯「與」,變成了: 1 2 3 ('H' == 'i') && ('a' == 'm') => False && ('a' == 'm') => False 在這個例子裡,我們沒有共享子表達式,所以沒甚麼必要用let關鍵字。 從現在開始,我們都會用文字表示法。 時間和空間 我們現在來看惰性求值對 Haskell 程式的時間空間佔用情況。如果你只用過貪婪求值,那麼這些可能會讓你震驚,特別是空間佔用上。 時間 求值一個表達式需要多少步?對貪婪求值而言,答案很簡單,對每次函數式應用,我們都把求值函數參數和求值函數體的時間加起來就可以了。而惰性求值呢?非常幸運的,惰性求值會佔的時間總有一個上限: 定理:惰性求值不會執行比貪婪求值更多的求值步驟。 這意味著當我們分析一個算法的運行時間時,我們總能把它當成是貪婪求值來評估。譬如說,我們可以把一個排序算法用 Haskell 改寫,並保證其算法複雜度和貪婪求值下一樣(在少數情況下甚至更佳)。 然而呢,惰性求值器實現起來會帶來一些額外的代價。對於圖形處理和數值模擬這樣的要求高效能的應用程式,可能放棄惰性求值而直接接觸底層架構實現會更實際一些。即便除此,以和簡潔和模塊化著稱的惰性求值依然在這些領域頑強存在。一種叫作「流融合」(Stream Fusion)的編譯器優化策略就能帶給高效率的數組操作一個模塊化,用起來像列表一樣的接口。這個技術就在 vector 庫裡實現了。 空間 不幸的是,空間佔用的情況就要複雜多了。問題的關鍵待求值表達式的內存佔用和它規約下來的規範式可以差別很大。因為一個表達式所佔用的空間等價於表示它的圖的所佔用的空間。譬如下面的表達式: 1 ((((0 + 1) + 2) + 3) + 4) 就比其模範式10所佔的空間多得多了。但再看下面表達式: 1 enumFromTo 1 1000 或者表示為更常見的[1..1000]。這個函數式應用表達式只包含三個節點,當然空間佔用也會比其模範式,列表 1:2:3:...:1000:[] 佔用的空間少多了,因為後者包含上千個節點。 當第一種情況越發嚴重導致無法控制時,我們稱之為空間洩漏(Space Leak)。解決方法就是手動控制求值過程,確保表達式僅可能早被求值。Haskell 為這種需求提供了這樣一個組合子: 1 seq :: a -> b -> b 正如其類型表示的那樣,這個表達式會像const函數一樣返回其第二個參數1。然而,對seq x y求值確總會先把x求值到 WHNF 的形式,然後才會繼續求值y。相對的,const函數就沒有必要先求值其參數到 WHNF。 每個 Haskell 程序員都應該知道怎麼用seq組合子,我們先來看一個具有代表性的例子:嚴格的左褶疊(Strict Left Fold)。看下面的求和 1 到 100 的代碼。我們用左褶疊,用累加參數(Accumulating Paramter)的方式求和: 1 foldl (+) 0 [1..100] 作為參考,在 Haskell Prelude 裡,foldl函數定義如下: 1 2 3 foldl :: (a -> b -> a) -> a -> [b] -> a foldl f a [] = a foldl f a (x:xs) = foldl f (f a x) xs 那麼上面例子的求值過程如下: 1 2 3 4 5 6 7 8 foldl (+) 0 [1..100] => foldl (+) 0 (1:[2..100]) => foldl (+) (0 + 1) [2..100] => foldl (+) (0 + 1) (2:[3..100]) => foldl (+) ((0 + 1) + 2) [3..100] => foldl (+) ((0 + 1) + 2) (3:[4..100]) => foldl (+) (((0 + 1) + 2) + 3) [4..100] => ... 如上所示,累加參數增長起來愈來愈多 – 空間洩漏。解決方法就是將累加參數保持在 WHNF,下面的修改過的foldl函數就能做到這一點: 1 2 3 foldl' :: (a -> b -> a) -> a -> [b] -> a foldl' f a [] = a foldl' f a (x:xs) = let a' = f a x in seq a' (foldl' f a' xs) 這個函數的定義可以在 Data.List 模塊裡找到。現在求值過程變成了這樣: 1 2 3 4 5 6 7 8 foldl' (+) 0 [1..100] => foldl' (+) 0 (1:[2..100]) => let a' = 0 + 1 in seq a' (foldl' (+) a' [2..100]) => let a' = 1 in seq a' (foldl' (+) a' [2..100]) => foldl' (+) 1 [2..100] => foldl' (+) 1 (2:[3..100]) => let a' = 1 + 2 in seq a' (foldl' (+) a' [3..100]) => let a' = 3 in seq a' (foldl' (+) a' [3..100]) 9 10 => foldl' (+) 3 [3..100] => ... 在求值的時候,可以看到表達式佔用的空間不再不斷增長下去了。用seq能確保累加參數總是先求值到 WHNF 然後才考慮剩下的元素。 憑經驗來看,foldl會導致空間洩漏,所以你應該用foldl'或者foldr。 順便一提,對於貪婪求值語言,你根本用不著寫上面這種代碼來求和1到100之間的數。因為貪婪求值會先把列表[1..100]規約到模範式,這樣子的空間效率佔用和我們上面低效的foldl版本一樣。要是想要做到高效率,那你必須把這個表達式寫成遞歸循環(Recursive Loop)才行。但得益於惰性求值,在 Haskell 裡,我們可以用通用的列表組合子2來「按需」對[1..100]計算。也就說明了惰性求值怎樣帶來更高的模塊化效果。 這個例子裡我們還要注意到另一個重要的概念。我上面演示的求值過程並非完全準確,如果我們這樣定義[n..m]: 1 enumFromTo n m = if n < m then n : enumFromTo (n+1) m else [] 那麼規約到 WHNF 其實是這樣的: 1 2 [1..100] => 1 : [(1+1)..100] 其中第一個參數是待求值表達式(1+1)而非2。在這裡這倒沒有多大關係,關鍵是你要非常小心才能精確追蹤惰性求值過程 – 它也許並不一定按你理想當然地來。真正的enumFromTo的源碼實現並不是這樣的。特別地,請留意[1..],它會構建一列不屬於 WHNF 的數。 事實上,我只能說,除非是對像上面這樣簡單的例子,要仔細追蹤惰性求值過程幾乎不可能。所以很難去分析 Haskell 的空間佔用情況。我的建議是只有在你的程序出現嚴重的空間洩漏時才去分析它,用性能分析工具來找到問題產生的源頭所在。一旦確認了問題源頭,就可以用 Space invariants和seq來確保相關表達式被規約城 WHNF,而無須管惰性求值具體是怎樣工作的。 這就是我今天要講的關於惰性求值和它空間佔用相關的內容了。其實還有另外一個有代表性的空間洩漏的例子,如下: 1 let small' = fst (small, large) in ... small' ... 即使fst函數會把large丟棄,表達式small'還是會保存一個到large的引用。你可能會希望在某個時候把small'規約到 WHNF,這樣large所佔的空間就可以被釋放掉了。 譯注: 1. 其實不太一樣,const的類型是a -> b -> a。這裡應該說seq的類型和flip const類似。 2. 這裡指foldl,foldl'和foldr這些函數。 (聲明:此文章的翻譯及發佈已經經過原文作者的許可。此譯文版權歸譯者所有,並在 CC BY-NC-SA 4.0 下發佈) Posted by Shou Ya Nov 24th, 2014  haskell  translation Tweet « Function Calling Syntax深淵 » http://log.lain.li/blog/how-lazy-evaluation-works-in-haskell/原文连接 Comments 翻譯:逆向狀態,又:惰性之力 MAR 4TH, 2015 原文 「Backwards State, or: The Power of Laziness」由 Antoine Latter 發佈於其個人Blogger上。特別地,對 Philip Wadler 及其著作的 The Essence of Functional Programming表示至高感謝。 近期我參加了一個關於 Haskell 中自動微分(Automatic Differentiaion)的討論,因為之我拜讀了 Jerzy Karczmarczuk 的論文「Lazy Time Reversal, and Automatic Differentiation」。這篇論文進一步引用了 Philip Wadler 的 The Essence of Functional Programming 來介紹逆向(Backward) State Monad,我覺得非常有趣,在此向大家講一下這種技術。 在此我期待讀者各位對 Haskell 的 State Monad 已有所了解,其實簡單來說 State Monad 就是一個函數,從上一個狀態映射到結果以及下一個狀態。 逆向 State Monad 和 State Monad 的區別就在於它和 State Monad 執行的順序恰好相反,也就是說,逆向 Monad 是從一個最終狀態執行到其最初狀態並產生一系列值的。 此文是一篇 文學 Haskell 文章,所以你可以把整個文件拷貝到一個 .lhs 文件中並用 Haskell 解釋器來跑之,譬如說用 GHCi。(譯者注:保留此段只為了完整性,本文並非用文學 Haskell 編寫,請讀者自行忽略此段。) 首先,我們要引入一些需要用到的樣板代碼: 1 2 3 4 5 6 {-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE MultiParamTypeClasses #-} {-# LANGUAGE RecursiveDo #-} import Data.List import Control.Monad.State 一個例子 先來做一個練習:假設給你一棵樹,你要做的是把樹的每個節點上的元素映射到整數上,這些整數從 0 開始並逐漸增加。如果有些元素出現了多次,那麼它們應該被映設到同樣的整數上。 用到 Control.Monad.State.Lazy 的解決方案就是,遍歷這棵數並用 State Monad 保存至今為止見過的所有元素作為狀態。也就是說,每個節點映射到其元素在此列表上的下標。這樣子第一個出現的元素會被映射到 0,第二個映射到 1,如此不斷進行下去。 但現在問題變了,如果我想把最後一個遇到的節點映射到 0,倒數第二個映射到 1,如此直到第一個節點,我應該怎麼做呢?對上面用 Control.Monad.State.Lazy 的解決方案我得改變多少才能滿足新的需求? 答案是,只要改一點點!我只要換成逆向 State Monad 就可以了,因為對之而言狀態流是反轉過來的。 修改過的解決方案看起來大概是這樣子的: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 data Tree a = Nil | Node a (Tree a) (Tree a) deriving (Show, Eq) type Table a = [a] numberTree :: Eq a => Tree a -> StateB (Table a) (Tree Int) numberTree Nil = return Nil numberTree (Node x t1 t2) = do num <- atomically $ numberNode x nt1 <- numberTree t1 nt2 <- numberTree t2 return (Node num nt1 nt2) where numberNode :: Eq a => a -> State (Table a) Int numberNode x = do table <- get (newTable, newPos) <- return (nNode x table) put newTable return newPos nNode:: (Eq a) => a -> Table a -> (Table a, Int) nNode x table = case elemIndex x table of Nothing -> (table ++ [x], length table) Just i -> (table, i) 相應的狀態求值調用如下: 1 2 numTree :: (Eq a) => Tree a -> Tree Int numTree t = evalStateB (numberTree t) [] 測試一下結果: 1 testTree = Node "Zero" (Node "One" (Node "Two" Nil Nil) (Node "One" (Node "Three" Nil Nil) Nil)) Nil 跑一下 numTree testTree 會生成這樣的樹: 1 Node 3 (Node 1 (Node 2 Nil Nil) (Node 1 (Node 0 Nil Nil) Nil)) Nil 正中吾需! 代碼幾乎和用 Control.Monad.State.Lazy 的原問題解決方法一模一樣,區別在於我們用了 evalStateB 取代我們熟悉的 evalState,用了一個神奇的函數 atomically,以及 StateBMonad。我下面會詳細講他們是何方神聖乃至於究竟是怎麼實現逆轉狀態的。 API 我們現在要有一個新的 Monad:StateB s,其中 s 為其存儲的狀態的類型。StateB s 是 MonadState s 的一個實例,所以裡所應當應該實現 get 和 put 函數。 當然還有這些: 1 2 3 runStateB :: StateB s a -> s -> (a, s) evalStateB :: StateB s a -> s -> a execStateB :: StateB s a -> s -> s 應該很熟悉吧,對應的就是 State Monad 裡的那些操作。技巧在於我們傳給它的狀態 s 是最終狀態而它返回的是初始狀態。回憶在上面的例子中,在我們遍歷樹的時候最後看到的元素被賦予第一個標籤(0),而第一個見到的元素被賦予最後的標籤。 在 Control.Monad.State.Class 中默認的 modify 函數實現如下: 1 2 3 4 modify :: MonadState s m => (s -> s) -> m () modify f = do s <- get put (f s) 而在 StateB Monad 中,這段代碼直接就得碰壁了,因為兩個 Monadic 的行為會相互循迴依賴,(>>=) 會把現在的結果向前傳遞,而在 StateB 中,運算結果的方向是調轉過來的傳遞的。也就是說,上面那段代碼會產生一個循迴引用:第一行得到更新過的狀態,而這個狀態卻是來自第二行放進去的。 要讓這樣的函數工作,我們要定義這個函數的 StateB 版本。 1 modifyB :: (s -> s) -> StateB s () 但如果你還想返回結果,你還會需要下面這位小朋友: 1 atomically :: State s a -> StateB s a atomically 會把正常 State 的動作轉換為 StateB 的動作,這樣你可以直接用現成的代碼。(或者你也可以用 mdo 語法) 實現 這裡的實現基於 Wadler 的論文。 StateB Monad 和 State Monad 幾乎一樣,每個產生 a 的動作都是一個類型為 \s -> (a, s) 的函數。區別在於 (>>=) 的實現。 讓我們開始定義! 1 2 3 4 5 newtype StateB s a = StateB { runStateB :: s -> (a,s) } instance Monad (StateB s) where return = StateB . unitS (StateB m) >>= f = StateB $ m `bindS` (runStateB . f) 因為封裝解封這個 newtype 的話太麻煩,所以他們只用在被導出的函數(如 return 和 (>>=))上用。剩下處理細節用的函數我都用 ‘S’ 做為其後綴了。 1 2 3 4 5 m `bindS` k = \s2 -> let (a, s0) = m s1 (b, s1) = k a s2 in (b, s0) unitS a = \s2 -> (a, s2) (譯者:我第一次看到上面這段代碼時興奮了一個晚上!短短三行就平直地描述並實現了狀態逆流的效果,非常簡潔而優美。) 正如君所見,傳進來的狀態(s2)被應用於 bindS 的右邊的參數(k)上,產生的狀態被 bindS左邊的參數(s1)消耗,並產生出最後的狀態 s0。就這樣就可以了嗎?嗯就這麼點!其他 API 實現如下: 1 2 execStateB m = snd . runStateB m 3 4 5 6 7 8 evalStateB m = fst . runStateB m modifyB = StateB . modify' where modify' f = \s -> ((), f s) atomically = StateB . runState 還可以把這些也寫了來玩: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 instance Functor (StateB s) where fmap f m = StateB $ mapS f (runStateB m) mapS f m = \s -> let (a, s') = m s in (f a, s') instance MonadState s (StateB s) where get = StateB get' where get' = \s -> (s,s) put = StateB . put' where put' s = const ((),s) instance MonadFix (StateB s) where mfix = StateB . mfixS . (runStateB .) mfixS f = \s2 -> let (a,s0) = (f b) s1 (b,s1) = (f a) s2 in (b,s0) 變形金剛(譯者:沒錯我故意的) 下面這些你要稍微注意一下,因為我沒測試過,不過看起來應該是工作的,這些風格基本和 Control.Monad.State.Lazy 的差不多。 1 2 3 4 5 6 7 8 9 10 11 newtype StateBT s m a = StateBT {runStateBT :: s -> m (a,s)} unitST a = \s -> return (a,s) m `bindST` k = \s2 -> mdo ~(a,s0) <- m s1 ~(b,s1) <- k a s2 return (b,s0) execStateBT :: Monad m => StateBT s m a -> s -> m s execStateBT m s = do ~(_,s') <- runStateBT m s return s' 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 evalStateBT :: Monad m => StateBT s m a -> s -> m a evalStateBT m s = do ~(a,_) <- runStateBT m s return a modifyBT :: Monad m => (s -> s) -> StateBT s m () modifyBT = StateBT . modify' where modify' f = \s -> return ((),f s) atomicallyT :: Monad m => State s a -> StateBT s m a atomicallyT m = StateBT $ \s-> return $ runState m s atomicallyTM :: Monad m => StateT s m a -> StateBT s m a atomicallyTM = StateBT . runStateT mapST f m = \s -> do ~(a,s') <- m s return (f a,s') liftST m = \s -> do a <- m return (a,s) mfixST f = \s2 -> mdo ~(a,s0) <- (f b) s1 ~(b,s1) <- (f a) s2 return (b,s0) instance Monad m => Functor (StateBT s m) where fmap f m = StateBT $ mapST f (runStateBT m) instance MonadFix m => Monad (StateBT s m) where return = StateBT . unitST (StateBT m) >>= f = StateBT $ m `bindST` (runStateBT . f) fail = StateBT . const . fail instance MonadTrans (StateBT s) where lift = StateBT . liftST instance MonadFix m => MonadState s (StateBT s m) where get = StateBT get' where get' = \s -> return (s,s) put = StateBT . put' where put' s = const $ return ((),s) instance MonadFix m => MonadFix (StateBT s m) where mfix = StateBT . mfixST . (runStateBT .) 譯後記 這篇文章第一次閱讀就給了我極大的震驚。我已知 Haskell 的惰性求值策略,而且也知道一些與之相關的優雅應用(譬如著名的 fib = 1 : 1 : zipWith (+) fib (tail fib)),不過讀到這篇文章時我還是大呼「神奇!」。此文雖然沒有在內容中著筆墨於惰性求值之中,卻在標題中直接強調了「The Power of Laziness」。從其他語言來的讀者可能會對上面 bindS 感到不可思議,覺得「怎麼可以直接這樣?」,是的,一般情況下當然不行,但是 Haskell 已裝備了強大的惰性求值,所以這樣寫也不是問題。 最後再次感謝 Wadler 提出的理論和 Latter 的這篇科普向(?)文章帶我們展現了依賴惰性求值實現的這個逆向 State Monad。 (聲明:此文章的翻譯及發佈已經經過原文作者的許可。此譯文版權歸譯者所有, 並在 CC BY-NC-SA 4.0 下發佈) Posted by Shou Ya Mar 4th, 2015  haskell  translation Tweet « 深淵誡之一 » http://log.lain.li/blog/backwards-state-or-the-power-of-laziness/原文连接 Comments

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 10 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档