Posted on November 24, 2014

Lambda 醬想遲些再去打掃房間～

foldl (+) 0 [1..10^8]

## 基礎：圖規約

### 表達式，圖，和 Redex

square x = x*x

square (1+2)

square (1+2)
=> (1+2)*(1+2)

(1+2)*(1+2)
=> 3*(1+2)
=> 3*3
=> 9

### 模範式和弱首模範式

ones = 1 : ones

### 求值順序，惰性求值

(&&) :: Bool -> Bool -> Bool
True  && x = x
False && x = False

('H' == 'i') && ('a' == 'm')

### 文字表示法

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

('H' == 'i') && ('a' == 'm')
=> False && ('a' == 'm')
=> False

## 時間和空間

### 空間

((((0 + 1) + 2) + 3) + 4)

enumFromTo 1 1000

seq :: a -> b -> b

foldl (+) 0 [1..100]

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f a []     = a
foldl f a (x:xs) = foldl f (f a x) xs

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]
=> ...

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)

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])
=> foldl' (+) 3 [3..100]
=> ...

enumFromTo n m = if n < m then n : enumFromTo (n+1) m else []

[1..100]
=> 1 : [(1+1)..100]

let small' = fst (small, large) in ... small' ...

1. 其實不太一樣，const的類型是a -> b -> a。這裡應該說seq的類型和flip const類似。
2. 這裡指foldlfoldl'foldr這些函數。

（聲明：此文章的翻譯及發佈已經經過原文作者的許可。此譯文版權歸譯者所有，並在 CC BY-NC-SA 4.0 下發佈）