惰性求值 #

-- 严格求值（其他语言）
-- 所有参数在函数调用前求值

-- 惰性求值（Haskell）
-- 参数只在需要时求值

-- 示例
const :: a -> b -> a
const x _ = x

-- 在严格语言中，const 5 (error "boom") 会报错
-- 在Haskell中，const 5 (error "boom") 返回 5

-- Thunk是未求值的表达式
-- 它是一个指向代码和环境的指针

-- 示例
x = 1 + 2  -- x是一个thunk，尚未求值

-- 当需要x的值时，thunk被求值
y = x + 1  -- 触发x的求值

-- 无限列表
ones :: [Int]
ones = 1 : ones  -- [1, 1, 1, 1, ...]

-- 使用
take 5 ones  -- [1, 1, 1, 1, 1]

-- 自然数
nats :: [Int]
nats = 0 : map (+1) nats  -- [0, 1, 2, 3, ...]

-- 使用
take 10 nats  -- [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

-- 斐波那契数列
fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

-- 使用
take 10 fibs  -- [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
fibs !! 10    -- 55

-- 埃拉托斯特尼筛法
primes :: [Int]
primes = sieve [2..]
  where
    sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

-- 使用
take 10 primes  -- [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

data Tree a = Node a (Tree a) (Tree a)

-- 无限二叉树
infiniteTree :: Tree Int
infiniteTree = go 1
  where
    go n = Node n (go (2 * n)) (go (2 * n + 1))

-- 使用
treeToList :: Int -> Tree a -> [a]
treeToList 0 _ = []
treeToList n (Node x left right) = 
    x : treeToList (n - 1) left ++ treeToList (n - 1) right

-- WHNF：表达式被求值到最外层构造器

-- WHNF示例
(1 + 2, 3 + 4)  -- WHNF，元组已构造
Just (1 + 2)    -- WHNF，Just已构造
\x -> 1 + 2     -- WHNF，lambda已构造

-- 非WHNF示例
1 + 2           -- 不是WHNF
[1 + 2, 3 + 4]  -- 不是WHNF（列表元素未求值）

-- seq :: a -> b -> b
-- 强制求值第一个参数到WHNF

-- 示例
seq (1 + 2) "done"  -- "done"，但1+2被求值

-- 使用seq避免空间泄漏
strictSum :: [Int] -> Int
strictSum = go 0
  where
    go acc [] = acc
    go acc (x:xs) = acc `seq` go (acc + x) xs

{-# LANGUAGE BangPatterns #-}

-- 使用!强制严格求值
strictSum :: [Int] -> Int
strictSum = go 0
  where
    go !acc [] = acc
    go !acc (x:xs) = go (acc + x) xs

-- 记录中的严格字段
data Person = Person
    { name :: !String
    , age  :: !Int
    }

import Control.DeepSeq

-- deepseq：完全求值
deepseq :: NFData a => a -> b -> b

-- 示例
forceSum :: [Int] -> Int
forceSum xs = sum xs `deepseq` sum xs

-- NFData实例
instance NFData Int where
    rnf x = x `seq` ()

-- 分离生成和处理
-- 生成器
generate :: [Int]
generate = [1..]

-- 处理器
process :: [Int] -> [Int]
process = take 10 . filter even . map (*2)

-- 组合
result = process generate  -- [4, 8, 12, 16, 20]

-- 处理无限数据
takeWhile (< 100) [n^2 | n <- [1..]]
-- [1, 4, 9, 16, 25, 36, 49, 64, 81]

-- 查找第一个满足条件的元素
find :: (a -> Bool) -> [a] -> Maybe a
find p = listToMaybe . filter p

-- 使用
find (> 100) [n^2 | n <- [1..]]
-- Just 121

-- 短路逻辑运算
False && undefined  -- False（不计算undefined）
True || undefined   -- True

-- 短路列表操作
take 0 undefined  -- []
null undefined    -- 错误！需要求值

-- 空间泄漏示例
badSum :: [Int] -> Int
badSum [] = 0
badSum (x:xs) = x + badSum xs

-- 问题：累积大量未求值的thunk
-- badSum [1..1000000] 会占用大量内存

-- 解决：使用严格求值
goodSum :: [Int] -> Int
goodSum = go 0
  where
    go !acc [] = acc
    go !acc (x:xs) = go (acc + x) xs

-- 惰性求值可能导致性能不可预测
-- 有时很快，有时很慢

-- 示例
lazyLength :: [a] -> Int
lazyLength = length

-- 如果列表元素很大，可能触发大量求值

-- foldl的空间问题
foldl (+) 0 [1..1000000]
-- 构建巨大的thunk：((((0 + 1) + 2) + 3) + ...)

-- 解决：使用foldl'
import Data.List (foldl')
foldl' (+) 0 [1..1000000]  -- 严格版本

-- 严格字段
data StrictPair = StrictPair !Int !Int

-- 所有字段严格
{-# LANGUAGE StrictData #-}
data Point = Point Double Double

-- 使用seq
strictMap :: (a -> b) -> [a] -> [b]
strictMap _ [] = []
strictMap f (x:xs) = 
    let y = f x
    in y `seq` (y : strictMap f xs)

-- 使用BangPatterns
strictMap' :: (a -> b) -> [a] -> [b]
strictMap' _ [] = []
strictMap' f (!x:xs) = f x : strictMap' f xs

import Control.Exception (evaluate)

-- 在IO中强制求值
main :: IO ()
main = do
    let x = 1 + 2
    evaluate x  -- 强制求值x
    print x

import Data.List (foldl')

-- 严格求和
sum' :: [Int] -> Int
sum' = foldl' (+) 0

-- 严格平均值
average :: [Int] -> Double
average xs = fromIntegral (sum' xs) / fromIntegral (length xs)

-- 惰性读取文件
processFile :: FilePath -> IO ()
processFile path = do
    contents <- readFile path  -- 惰性读取
    let result = process contents
    print result

-- 严格读取大文件
processLargeFile :: FilePath -> IO ()
processLargeFile path = do
    contents <- readFile path
    length contents `seq` print "File read"  -- 确保读取完成
    let result = process contents
    print result

-- 处理无限流
streamProcess :: [Int] -> [Int]
streamProcess = take 100 . filter even . map (*2)

-- 使用
streamProcess [1..]  -- [4, 8, 12, ..., 200]