Ninety-Nine Haskell Problems 是 Haskell 社区经典的 99 道练习题，源自 Prolog 99 题的 Haskell 移植版。每个题目都有一个函数骨架，你只需要实现它，然后跑预置测试验证。
这套题的独特价值在于：难度梯度设计得好，从最基础的列表递归一路做到图同构、Huffman 编码、数独求解。把 LYAH 学到的语法点串成实战能力。
学习阶段划分
第一阶段：列表基础（P01-P10）
覆盖 LYAH：Ch1-5
| 题号 | 题目 | 核心语法 | 推荐 |
|---|---|---|---|
| P01 | 取列表最后一个元素 | 递归基条件、Maybe | ★ |
| P02 | 取列表倒数第二个元素 | 多条件递归 | ★ |
| P03 | 取列表第 k 个元素 | 下标计数 | ★ |
| P04 | 求列表长度 | 尾递归、fold | ★ |
| P05 | 反转列表 | 递归 + ++ vs 尾递归优化 | ★ |
| P06 | 判断回文 | ==、列表比较 | ★ |
| P07 | 展平嵌套列表 | 自定义 ADT、递归遍历 | ★ |
| P08 | 去除连续重复元素 | Eq 约束、guard | ★ |
| P09 | 将连续重复元素打包成子列表 | group 的手动实现 | ★★ |
| P10 | 游程编码 (run-length encoding) | 结合 P09、tuple | ★★ |
P01-P06 是热身，闭着眼也要能写出来。P07 让你第一次接触自定义 data 类型（NestedList），为后面树和图打基础。P08-P10 是 group 的三种变体，理解它们对第 7 章 Data.List 模块的理解有质的提升。
第二阶段：编码与列表变换（P11-P20）
覆盖 LYAH：Ch4-7
| 题号 | 题目 | 核心语法 | 推荐 |
|---|---|---|---|
| P11 | 改进的游程编码 | 自定义 data Encoding a，Single/Multiple | ★ |
| P12 | 解码游程编码 | replicate、concatMap | ★ |
| P13 | 直接实现游程编码 | 不用中间子列表，边遍历边计数 | ★★ |
| P14 | 复制每个元素 | concatMap、replicate | ★ |
| P15 | 每个元素重复 N 次 | concatMap | ★ |
| P16 | 每隔 N 个删除一个元素 | zip + 取模计数 | ★★ |
| P17 | 在 N 处切分列表 | splitAt | ★ |
| P18 | 提取子列表 [i, k] | take/drop 组合 | ★★ |
| P19 | 旋转列表 N 位 | 正负数旋转、splitAt | ★★ |
| P20 | 删除第 k 个元素，返回 (元素, 剩余列表) | splitAt 组合 | ★ |
P11-P12 教你用自定义代数数据类型（Encoding）表达业务语义——这是 Haskell 最核心的思维方式。P16-P20 在练 take/drop/splitAt/zip 的标准组合套路，对刷题帮助直接。
第三阶段：组合与随机（P21-P28）
覆盖 LYAH：Ch5-7
| 题号 | 题目 | 核心语法 | 推荐 |
|---|---|---|---|
| P21 | 在指定位置插入元素 | splitAt | ★ |
| P22 | 生成整数范围 | enumFromTo 或递归 | ★ |
| P23 | 从列表随机选 N 个元素 | RandomGen、ST monad | ★★★ |
| P24 | 从 1..M 中随机选 N 个不同数 | P23 的应用 | ★★ |
| P25 | 随机排列列表 | Fisher-Yates 洗牌 | ★★★ |
| P26 | 生成所有 N 选 K 的组合 | 递归、list comprehension | ★★★ |
| P27 | 互斥分组 | 组合 + 回溯 | ★★★ |
| P28 | 按子列表长度排序 / 按出现频率排序 | sortOn、group . sort、comparing | ★★ |
P26 是经典回溯题，用 list comprehension 写比 C++ 的 for 循环嵌套清爽太多。P23-P25 涉及随机性，Haskell 的纯函数随机数（State monad）跟命令式语言完全不同，这一关是思维转换节点。如果卡住，可以暂时跳过 P23-P25 先往后走，回来再看。
第四阶段：数论（P29-P45）
这个阶段跟 LYAH 关系不大，但跟数学底子关系很大。
| 核心题 | 说明 | 推荐 |
|---|---|---|
| P29 | 欧拉函数 φ(n) | ★ |
| P30 | 判断素数 | ★★ |
| P31 | 互质判断、gcd | ★ |
| P32-P33 | 质因数分解 | ★★ |
| P34 | 改进版 φ(n)（用质因数） | ★★ |
| P35-P36 | 高 totient 数 | ★★★ |
| P37-P39 | 素数生成（埃拉托色尼筛 + 流式无限列表） | ★★★ |
| P40-P41 | 哥德巴赫猜想验证 | ★ |
| P42-P43 | 乘法逆元、高斯整数 | ★★★ |
| P44-P45 | 命题逻辑、真值表、合取范式 | ★★★ |
P37 的埃拉托色尼筛在 Haskell 里有非常优雅的写法：primes = 2 : filter (isPrime primes) [3..]。这题跟你平时在 C++ 里写的 bitset 筛法完全不同——Haskell 用无限惰性列表表达筛法，是理解惰性求值优势的绝佳例子。P44-P45 涉及命题逻辑和自动定理证明，适合对形式逻辑感兴趣的做。
第五阶段：树（P54-P69）
覆盖 LYAH：Ch8（自定义类型）
| 核心题 | 说明 | 推荐 |
|---|---|---|
| P54-P55 | 完全平衡二叉树、对称树 | ★ |
| P56 | 从列表构造 BST | ★★ |
| P57-P58 | 高度平衡树（AVL 前身） | ★★★ |
| P59-P60 | 树的叶子/内部节点/按层遍历 | ★★ |
| P61-P62 | 完全二叉树、布局算法 | ★★★ |
| P63-P66 | 树 ↔ 字符串序列化 | ★★ |
| P67-P68 | 树的 dotstring 表示、前序/中序 → 树重建 | ★★ |
P57 的平衡树构造问题在 Haskell 里可以一行的 list comprehension 写出来，这也是 Haskell 数据处理最优雅的地方。P68 是经典的 “已知前序和中序，重建二叉树”，面试高频题。
第六阶段：图与难题（P80-P99）
难度最高，需要大量背景知识。
| 核心题 | 说明 | 推荐 |
|---|---|---|
| P80-P81 | 图的不同表示（邻接表/边列表） | ★★ |
| P82-P83 | 两点间所有路径、所有环 | ★★★ |
| P84 | 最小生成树（Prim） | ★★★ |
| P85 | 图同构判断 | ★★★★★ |
| P86 | 图着色 | ★★★ |
| P87-P88 | 二分图判断、连通分量 | ★★ |
| P90-P91 | 八皇后问题、骑士巡游（回溯） | ★★★ |
| P92-P93 | 数位谜题（arithmetic puzzle） | ★★★ |
| P94-P95 | 正则图生成、全词/标识符 | ★★ |
| P96 | 数独求解 | ★★★ |
P90（八皇后）和 P96（数独）是两种经典的回溯问题。用 Haskell 的 do-notation（list monad）可以不到 10 行写完八皇后，这大概是 Haskell 最令人震撼的表达力展示。图的部分整体可以放最后做，因为需要很多额外的数据结构知识。
实操建议
环境搭建
1cabal install ninetynine
安装后得到 Problems.* 模块，每个模块里有 myLast、myButLast 这样的函数骨架。
学习节奏
- 刚学完 LYAH Ch1-5：做 P01-P10，边做边巩固递归和模式匹配
- 学到 LYAH Ch7：做 P11-P20 + P28，练习
take/drop/group组合 - 学到 LYAH Ch8：做 P54-P69，树和自定义类型
- 想要挑战：P90 八皇后（掌握 list monad 后有惊喜）、P37 无限素数流（体验惰性求值）
哪些可以跳过
- P23-P25（随机性）：涉及
RandomGen和 State monad，初学者杀手 - P42-P45（数论扩展）：除非对数学感兴趣
- P85（图同构）：NP-hard 问题，纯粹学术挑战
总结
| 阶段 | 题号范围 | 对应 LYAH | 核心收获 |
|---|---|---|---|
| 列表基础 | P01-P10 | Ch1-5 | 递归、模式匹配、Maybe |
| 列表变换 | P11-P20 | Ch4-7 | 自定义类型、take/drop 组合 |
| 组合 | P21-P28 | Ch5-7 | 回溯、惰性列表、State monad |
| 数论 | P29-P45 | 数学 | 惰性筛法、命题逻辑 |
| 树 | P54-P69 | Ch8 | 自定义 ADT、树遍历 |
| 图 | P80-P99 | 进阶 | 回溯、list monad、图算法 |