Lazy computation 在實際應用中有什麼妙用？

01-26

一些現代語言內置了 lazy computation 的 mechanism，比如 F# 的
let identifier = lazy ( expr )
和 Scala 的
lazy val identifier = expr
然而不像 higher-order functions 和 currying，實際應用中常常不會注意到它的存在，有哪些對於其的妙用的例子？

Prime Generator

primes = sieve [2..] sieve (p : xs) = p : sieve [x | x & 0]

這運行的很慢，看看就好。。。

要更快的版本可以看

https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

Circular Syntax

data Exp = Var Name -- Variable | Lam Name Exp -- Abstraction | App Exp Exp -- Application deriving (Show)


app :: Exp -&> Exp -&> Exp

app = App 
lam :: (Exp -&> Exp) -&> Exp

lam f = Lam n body

  where

    body = f (Var n)

    n    = prime (maxBV body)
type Name = Integer

bot :: Name

prime :: Name -&> Name

(?) :: Name -&> Name -&> Name
bot   = 0

prime = succ

(?)   = max

maxBV :: Exp -&> Name maxBV (Var _) = bot maxBV (App f a) = maxBV f ? maxBV a maxBV (Lam n _) = n

http://www.cse.chalmers.se/~emax/documents/axelsson2013using.pdf

用這東西，我們就可以把Higher-order abstract syntax 轉化成一階的（不含函數的數據結構），這樣才能輸出

另外私貨時間：幻想中的Haskell - Compiling Combinator - The Dairy of Marisa - 知乎專欄我找到的另一種解法

Universe

data U x = U [x] x [x]


right (U a b (c:cs)) = U (b:a) c cs

left  (U (a:as) b c) = U as a (b:c)
instance Functor U where

    fmap f (U a b c) = U (map f a) (f b) (map f c)
class Functor w =&> Comonad w where

    (=&>&>)    :: w a -&> (w a -&> b) -&> w b

    coreturn :: w a -&> a

    cojoin     :: w a -&> w (w a)

    x =&>&> f = fmap f (cojoin x)
instance Comonad U where

    cojoin a = U (tail $ iterate left a) a (tail $ iterate right a)

    coreturn (U _ b _) = b
rule (U (a:_) b (c:_)) = not (a  b  not c || (a==b))

shift i u = iterate (if i&<0 then left else right) u !! abs i toList i j u = take (j-i) $ half $ shift i u where half (U _ b c) = b : c main = let u = U (repeat False) True (repeat False) in putStr $ unlines $ take 20 $ map (map (x -&> if x then "#" else " ") . toList (-20) 20) $ iterate (=&>&> rule) u

其中，U代表的是一個世界，x是這個世界的『原點』的狀態，x左邊的兩個無窮列表就是原點左邊右邊的狀態，left/right就是左移/右移原點

世界組成comonad：世界的世界，The World（ @迪奧布蘭度），在這，x就是原本的整個universe，x左邊的就是無數個左移構成的平行世界。left就是移動到左邊的平行世界（@法尼瓦倫泰）。在main中，我們把世界無限加速（ @普奇），取頭20個瞬間的世界，然後列印出來。。。

不好意思，中二了會，我擦擦淚繼續，天殺的普奇，竟然XX了XX（防劇透）

Avoiding Memory Leak

還有個有點玄學（其實只是結論反直覺了，跟著看一遍挺科學的）的玩法：當你thunk太多消耗內存的時候，解決方法是引入更多的laziness！An insufficiently lazy map : Inside 736-131

沒什麼是一個thunk不能解決的，如果有就來兩個 - 琪露諾

基本上就是以前你有length個thunk，因為列表的結構（spine）是strict的，現在就變成只有1個：整個列表就是個thunk，於是就沒事了

舉一個circular programming的簡單例子：遍歷二叉樹。

題目描述

題目要求很簡單：

用一趟遍歷（包括但不限於遞歸），實現將二叉樹中所有結點的值全部改為該二叉樹中所有結點值的最小值。

傳統的方法是先用一趟遍歷獲取最小值，再用一趟遍歷將所有node的值改為這個最小值。我們這次要求完成目標，in just one pass。

定義二叉樹的結構為（Haskell表示）：

data Tree = Leaf Int | Branch Int Tree Tree

樣例輸入輸出

[Input] Branch 7 (Branch 4 (Leaf 5) (Leaf 3)) (Leaf (-99)) [Output] Branch (-99) (Branch (-99) (Leaf (-99)) (Leaf (-99))) (Leaf (-99)) [Input] Branch (-2) (Branch 7 (Leaf 3) (Leaf 5)) (Branch 2 (Leaf 4) (Branch 8 (Leaf 9) (Leaf 6))) [Output] Branch (-2) (Branch (-2) (Leaf (-2)) (Leaf (-2))) (Branch (-2) (Leaf (-2)) (Branch (-2) (Leaf (-2)) (Leaf (-2))))

解答

repMin" (Leaf n, r) = (n, Leaf r) repMin" (Branch v a b, r) = (min v $ min min1 min2, Branch r a" b") where (min1, a") = repMin" (a, r) (min2, b") = repMin" (b, r)

repMin t = newTree where (min, newTree) = repMin" (t, min)

repMin函數的神奇之處在於把一個返回值當成了傳入函數的參數，這種input和output相互依賴的程序能夠跑通的關鍵就在於lazy evaluation。拿個樣例自己試一下整個遞歸過程，會很有助於理解。

參考資料：

Circular programming

https://techo.io/topic/38/

黑科技，可持久化平攤 O(1) push/pop 的雙端隊列

可持久化。。平攤？

如果平攤的話，我對 X 進行操作 foo 是一個比較慢的操作，那麼我不停地對 X 進行操作 foo 豈不是破壞了平攤的性質了？

Okasaki: No.

完全可以讓你對 X 兩次操作得到的結果中，有部分是共享的 thunk，這樣只要在一邊對這個 thunk 求值，另一邊的 thunk 也就變成一個值了。

這個數據結構俗稱 Data.Sequence，文檔在此： http://hackage.haskell.org/package/containers-0.5.8.1/docs/Data-Sequence.html。還支持 split index 等操作哦

其中用到的技巧在 Chris Okasaki 的 Purely Functional Data Structures 有描述

這裡有個簡化的版本，它只是一個單向的隊列，也是用到類似的技巧：http://www.well-typed.com/blog/2016/01/efficient-queues/

可惜我完全理解不了這個數據結構黑科技。說點我懂的吧。

一個比給二叉樹標號實際點的工作：一次遍歷完成彙編操作。

彙編里可能會出現這種狀況：

something jmp Label ; ----------+ mov blah, blah ; mov blah, blah ; ; Label: ; &<----------------+ something

我們要提前知道 Label 所指向的位置，但是我們還沒看到過 Label 呢。怎麼辦呢？

我們把所有標籤指向的位置存成一個 Map。彙編的過程中，jmp 指令從 Map 中讀取標籤對應的位置，遇到標記就把標記和對應位置存在 Map 里。

assemblerHelper :: Map String Int -&> String -- The input -&> ([Instruction], Map String Int)

然後高能的部分來了。不是要那個 Map 嘛，我們把它傳回去就行了

assembler :: String -&> [Instruction] assembler input = let (inss, table) = assemblerHelper table input in inss

只要一個標籤的位置本身不會影響到 jmp 指令的生成（比如標籤是指令的編號而不是位元組數），這樣就做完了

因為我們其實走到 jmp 那裡的時候，在生成的 Instruction 裡面留下了一個坑，等遍歷完的時候再去看那個 Instruction 的時候，其實坑早就填上了——就在 Map 裡面呢

Haskell non-strict求值, 各種惰性求值的用法可能所有的用法都談不上"妙"

來個老生常談的例子:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

看過SICP ch3.5的大概不會覺得陌生

更樸素的例子, 把列表裡的tuple第二個值取出來加1

kv = [("a",1),("b",2),("c",3),("d",4),("e",5),("f",6)] map ((+1) . snd) kv

這裡面涉及兩個操作一個是解構(Destructuring), 然後是操作解構出來的值

惰性求值在這裡免去了解構後的中間值([1,2,3,4,5,6])

用半吊子javascript來比喻說就是用underscore里pluck拿出一個數組然後each,

當然有comprehension的話都是不是事

但是因為惰性求值這裡的代碼更加模塊化可組合性更好, 解構和操作分別是兩個函數, 兩個函數是獨立的, 函數更多的話還是可以用(.)組合起來, 代碼不會糾結在一起, 例如這種:

for(a in a_collection): if condA condB condC condD #....

condA condB condC condD 可能是各種糾結的代碼

-- 這是個理想的代碼 XD 看 @連城的評論 filter (predD . predC . predB .predA) collection

-- 實際要compose predicate 看這裡: http://stackoverflow.com/a/841931

這種就比較順眼

還有alpha-beta搜索, 就是搜索時候的剪枝, 惰性都挺好用的

我不多說了, 大家快去看Why Functional Programming Matters 吧!

還有經典的

How to replace failure by a list of successes - a method for exception handling, backtracking, and pattern matching in lazy functional languages

補個實際的例子:

Haskell的redis客戶端Hedis利用Lazy來做 Automatic Optimal Pipelining:

Automatic Optimal Pipelining of Redis Commands

我沒用 lazy 特性寫過實際生產代碼，所以舉個我知道的比較簡單的例子：動態規劃。

用動態規劃求解問題通常策略是先要想好一個數據結構，然後把要用到的子問題映射到這個數據結構上。在 strict evaluation 情況下我們必須依次求解這些子問題然後把結果存到數據結構里，不能出現求解某個問題的時候其子問題還沒有求解的情況。

但是用 lazy evaluation 的時候就不用考慮這個問題。因為 lazy evaluation 在調用函數的時候不立即對函數的實參求值，而是返回一個 thunk，在以後需要用到這個 thunk 的值的時候才會對它求值，所以，我們可以直接創建一個數據結構，裡面所有的數據都初始化成 thunk，然後直接取子問題對應的數據，讓 lazy 特性去幫我們求值。

舉個具體的例子，比如你要算最長公共子序列問題（LCS），然後你寫了一個函數 solve(i, j)，i 和 j 分別代表兩個字元串中的某個位置，還有一個二維數組 mem。你就可以這樣初始化這個二維數組：

mem[i][j] = solve(i, j)

這個數組初始化完以后里面全都是 thunk，solve 函數實際上一個都沒有調用。然後你決定把 mem[m][n] 的值列印出來，這時候程序就知道你需要 solve(m, n) 的值了，就會幫你求這個 thunk 的值，solve(m, n) 求值過程中又回去訪問 mem 數組裡面的其它三個值 mem[m-1][n-1]，mem[m][n-1]，和 mem[m-1][n]，所以又會反過來調用 solve(m-1, n-1), solve(m, n-1), solve(m-1, n)。最後子問題都解完了，結果就出來了，如果有哪個子問題的值沒有用到，那麼它將還是以 thunk 的形式存在，不會浪費計算資源（不過在 LCS 問題里所有子問題都是會用到的）。

具體可以看下這篇文章：Lazy Dynamic Programming

其實Scala的lazy關鍵字是很常用的（非常常見），比如：在有些資源沒有必要一開始就載入的情況下就會聲明為lazy的，在用到時再去初始化；比如：同一份code可能需要按role初始化不同類型實例的時候也會聲明為lazy （如Akka Cluster 按role需要啟動不同的Actor時），在某種程度上Scala的lazy是來Fix val關鍵字（因為是final）的立即求值特點的。

不過Lazy computation 在Scala里不止是lazy關鍵字，更重要的是call-by-name (記得翻譯為：傳名函數)

def pair(x: =&> Int):(Int, Int) = (x, x)

（註：class構造函數參數不可以是non-strict, 所以要lazy必須傳函數() =&> ???）

那麼就來說說傳名函數的實際應用吧！

常見的一種情況就是Infinite Stream無窮數據流（或叫Generator）了，而很多東西都可以視為無窮數據流，比如資料庫查詢分頁操作，為其定義一個getMore操作（比如前端瀑布流）：

def getData(s:Int, l:Int) = Option(s"sql...skip=$s limit=$l") def getMore(skip: Int, limit: Int) = Stream.unfold(skip){ s =&> Some(getData(s, limit), s+limit) } println(Stream.getMore(0,10).take(3).toList) //&>&>&> List(Some(sql...skip=0 limit=10), Some(sql...skip=10 limit=10), Some(sql...skip=20 limit=10))

Stream的unfold方法定義為：

S -&> (A, S) //A為前一個值，S為下一個值：自增數列可表示為(s -&>(s, s+1))(0)

其次就是其本意推遲計算了，比如：把所有的網路請求都延遲到最後返回值時計算，比如：將多個計算函數分配到不同的線程中去執行，實現這些依靠non-strict則會很簡單

不管是用mechanism 還是通過() =&> ??? 去模擬non-strict，lazy computation 在Scala中是很普遍的，也是必須的，甚至與higher-order functions一樣常見

謝邀

用夏梓耀的另外一個問題來回答這個問題

如何評價 Trampoline (Stackless Scala) ? - 你如何評價 X

沒有 lazy evaluation ，上面這個問題就是一個偽命題。

先盜個貼，彈個床。原文在這

Rich Dougherty』s blog: Tail calls, @tailrec and trampolines

簡單來說，如果不跳彈床，stack上限會到頂，爆贊，不，爆棧。

彈床通過惰性求值把一個函數傳回調用，最多也就4級棧。

一級： trampoline 入棧 even(9999)

二級：even(9999) 裡面來個閉包 () =&> odd(n - 1)

這時候 even（9999）直接出棧返回 Call(() =&> odd(n - 1))

一級：trampoline（trampoline（Call(() =&> odd(n - 1))

二級：trampoline（Call(() =&> odd(n - 1)）

三級：odd(n - 1)

四級：來個 () =&> even(n - 1)

然後就沒有了然後，這四級棧，出出入入地就跑完了，你說沒有惰性求值，這爆棧多累啊不是？

寫個基本定義

sealed trait Bounce[A] case class Done[A](result: A) extends Bounce[A] case class Call[A](thunk: () =&> Bounce[A]) extends Bounce[A]

def trampoline[A](bounce: Bounce[A]): A = bounce match { case Call(thunk) =&> trampoline(thunk()) case Done(x) =&> x }

彈床寫法

def even(n: Int): Bounce[Boolean] = { if (n == 0) Done(true) else Call(() =&> odd(n - 1)) } def odd(n: Int): Bounce[Boolean] = { if (n == 0) Done(false) else Call(() =&> even(n - 1)) }

trampoline(even(9999))

對比一下不彈床的寫法，用的的棧自己算算

def even_reg(n: Int): Boolean = { if (n == 0) true else odd_reg(n - 1) } def odd_reg(n: Int): Boolean = { if (n == 0) false else even_reg(n - 1) } even_reg(9999)

構建線段樹的時候不用用null來表示沒有子節點

一個用處就是可以用來定義操作符

操作符跟函數還是有區別的，操作符不只是函數的語法糖。操作符是可以短路的，而函數一般不會。操作符其實更像是for,while,if,goto這樣的語法控制結構，而不是更像是函數。一門語言缺少一些內置函數並不會限制它的表達能力，但是缺少一些特定的操作符，就會限制其表達能力了。
當能夠用函數調用的語法實現短路操作時，你就獲得了「自定義語法結構」的力量。要麼就是用宏，要麼就要惰性求值（lazy evaluation），這兩個，一個是lisp，一個是haskell

如果理解編程語言中「操作符」（operator）的概念？ - C++

比如說，要是有 lazy computation的話

這個就很好解決了說個logging的性能問題，一般我們寫log 用... 來自韋恩卑鄙

@王韋恩卑鄙

舉個實際場景 ...在做ORM最後生成SQL的時候，可以利用lazy computation的特性.

Spark broadcast variable

如果把類的一部分成員聲明為lazy，那麼在廣播的時候就可以減少序列化、網路通訊的開銷。對於比較大的數據來說，這種方式效果很明顯。

可以很好的進行優化

請參考eigen和mxnet中使用的mshadow