Ninety-Nine Haskell Problems 是 Haskell 社区经典的 99 道练习题,源自 Prolog 99 题的 Haskell 移植版。每个题目都有一个函数骨架,你只需要实现它,然后跑预置测试验证。
这套题的独特价值在于:难度梯度设计得好,从最基础的列表递归一路做到图同构、Huffman 编码、数独求解。把 LYAH 学到的语法点串成实战能力。
覆盖 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 模块的理解有质的提升。
覆盖 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 的标准组合套路,对刷题帮助直接。
覆盖 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 先往后走,回来再看。
这个阶段跟 LYAH 关系不大,但跟数学底子关系很大。
| 题号 | 题目 | 核心语法 | 推荐 |
|---|---|---|---|
| P29 | 斐波那契数列 | 递归、矩阵快速幂 | ★ |
| P30 | 矩阵快速幂求斐波那契 | 矩阵运算、性能优化 | ★★ |
| P31 | 判断素数 | all、因数枚举 | ★★ |
| P32 | 最大公约数 | 欧几里得算法 | ★ |
| P33 | 互质判断 | gcd 应用 | ★ |
| P34 | 欧拉函数 φ(n) | 数学推导 | ★★ |
| P35 | 质因数分解 | 递归遍历 | ★★ |
| P36 | 质因数分解(含重数) | group、map | ★★ |
| P37 | 欧拉乘积公式求 φ(n) | 质因数分解 + 乘积 | ★★ |
| P38 | 高 totient 数 | 筛法思想 | ★★★ |
| P39 | 区间内素数列表 | 素数筛 | ★★ |
| P40 | 无限素数列表 | 惰性筛法 | ★★ |
| P41 | 哥德巴赫猜想验证 | 素数组合 | ★ |
| P42 | 哥德巴赫猜想列表 | 列表推导 | ★ |
| P43 | 模逆元 | 扩展欧几里得 | ★★★ |
| P44 | 高斯整数整除 | 数论扩展 | ★★★ |
| P45 | 高斯素数 | 平方和定理 | ★★★ |
P40 的埃拉托色尼筛在 Haskell 里有非常优雅的写法:primes = 2 : filter (isPrime primes) [3..]。这题跟你平时在 C++ 里写的 bitset 筛法完全不同——Haskell 用无限惰性列表表达筛法,是理解惰性求值优势的绝佳例子。P43 开始的高斯整数部分对数学兴趣浓厚者值得深入。
覆盖 LYAH:Ch7(模块)、Ch11(Functors/Applicative/Monoids)
| 题号 | 题目 | 核心语法 | 推荐 |
|---|---|---|---|
| P46 | 逻辑表达式真值表 | 递归布尔运算 | ★★ |
| P47 | 通用逻辑门 | 电路模拟、组合逻辑 | ★★★ |
| P48 | n 元布尔函数真值表 | 高阶函数、列表推导 | ★★ |
| P49 | 格雷码 | 递归构造、位运算 | ★★ |
| P50 | 霍夫曼编码 | 树构建、优先队列 | ★★★ |
| P51 | 纠错码 | 编码/解码算法 | ★★★★ |
| P52 | 合取范式 | Formula ADT、递归转换 | ★★★ |
| P53 | 归结原理 | 自动定理证明 | ★★★★ |
P49 (格雷码) 和 P50 (霍夫曼编码) 是经典的编码/压缩算法,用 Haskell 的表达力写出来非常清爽。P52-P53 涉及命题逻辑和自动定理证明的初步知识,适合对形式逻辑感兴趣的读者。
覆盖 LYAH:Ch8(自定义类型)
| 题号 | 题目 | 核心语法 | 推荐 |
|---|---|---|---|
| P54 | 二叉树定义 | ADT Tree a | ★ |
| P55 | 构造完全平衡二叉树 | 递归构造 | ★ |
| P56 | 对称二叉树 | 镜像递归判断 | ★★ |
| P57 | 二叉搜索树(BST) | 插入、构造 | ★★ |
| P58 | 对称且完全平衡的二叉树 | 组合条件 | ★★★ |
| P59 | 构造高度平衡二叉树 | AVL 前身 | ★★★ |
| P60 | 给定节点数的高度平衡二叉树 | 搜索 + 构造 | ★★★ |
| P61 | 收集二叉树的叶子节点 | 递归遍历 | ★★ |
| P62 | 收集二叉树指定层的节点 | 层序遍历 | ★★ |
| P63 | 构造完全二叉树 | 数组下标映射 | ★★★ |
| P64 | 二叉树布局:中序排列 | 中序遍历分配坐标 | ★★★ |
| P65 | 二叉树布局:层级等距 | 层间距恒定 | ★★★ |
| P66 | 二叉树布局:紧凑排列 | 宽度最小化 | ★★★ |
| P67 | 二叉树的字符串表示 | 序列化 / 反序列化 | ★★ |
| P68 | 二叉树的中序和前序序列 | 树重建 (经典面试题) | ★★ |
| P69 | 二叉树的点串表示 | dotstring 编解码 | ★★ |
P57 的平衡树构造问题在 Haskell 里可以一行的 list comprehension 写出来,这也是 Haskell 数据处理最优雅的地方。P68 是经典的 “已知前序和中序,重建二叉树”,面试高频题。P64-P66 的布局问题则极好地训练了递归思考能力。
覆盖 LYAH:Ch8(自定义类型)
| 题号 | 题目 | 核心语法 | 推荐 |
|---|---|---|---|
| P70 | 从节点字符串构造树 | 字符串解析、递归 | ★★ |
| P71 | 树的内部路径长度 | 递归遍历、路径累加 | ★★ |
| P72 | 树的后序遍历 | 后序递归 | ★★ |
| P73 | 树的 S 表达式表示 | 括号表示法、递归序列化 | ★★★ |
多路树(Multiway Tree)是每个节点可以有任意多个子节点的树。P70 的字符串解析和 P73 的 S 表达式是实践中常见的序列化场景。
覆盖 LYAH:Ch12-13(Monad)
| 题号 | 题目 | 核心语法 | 推荐 |
|---|---|---|---|
| P74 | 不用 do 记法的 IO monad | >>= / >>、纯函数式 IO | ★★★ |
| P75 | Maybe monad | Maybe 链式操作 | ★★ |
| P76 | Either monad | Either 错误处理 | ★★ |
| P77 | List monad | 非确定性计算 | ★★ |
| P78 | Collatz 猜想 | 递归终止性 | ★★ |
| P79 | 后缀表达式 | 栈计算、fold | ★★★ |
这一阶段是 Haskell 从 “好用的函数式语言” 到 “理解其核心抽象” 的跨越。P74 强制你不用 do 语法,直接操作 >>=,这是理解 IO 内部机制的必经之路。P77 的 List monad 是八皇后等回溯问题的语法糖基础。
难度开始爬升,需要额外的数据结构知识。
| 题号 | 题目 | 核心语法 | 推荐 |
|---|---|---|---|
| P80 | 图的表示转换 | ADT 设计 | ★★ |
| P81 | 两点间所有路径 | DFS、回溯 | ★★★ |
| P82 | 包含指定顶点的环 | DFS + 路径记录 | ★★★ |
| P83 | 构造生成树 | 图搜索 | ★★★ |
| P84 | 构造最小生成树(Prim) | 优先队列、贪心 | ★★★ |
| P85 | 图同构判断 | 组合搜索 | ★★★★★ |
| P86 | 图着色 | 贪心 + 回溯 | ★★★ |
| P87 | 深度优先遍历 | 状态标记、递归 | ★★ |
| P88 | 连通分量 | DFS 遍历 | ★★ |
| P89 | 二分图判断 | BFS 染色 | ★★ |
图的部分整体可以对大多数学习者放最后做,因为需要很多额外的数据结构知识。P85(图同构)是 NP-hard 问题,纯粹学术挑战,可以跳过。
难度最高,涵盖算法和工程实践。
| 题号 | 题目 | 核心语法 | 推荐 |
|---|---|---|---|
| P90 | n 皇后问题 | list monad、回溯 | ★★★ |
| P91 | 骑士巡游 | Warnsdorff 规则、回溯 | ★★★ |
| P92 | 优雅树标记 | 组合搜索 | ★★★★ |
| P93 | 算术谜题 | 运算符排列、求值 | ★★★★ |
| P94 | 正则图 | 图构造、同构检测 | ★★★★ |
| P95 | 英文数字单词 | 递归、映射 | ★★ |
| P96 | 语法检查 | 递归下降解析 | ★★ |
| P97 | 数独求解 | 约束传播 + 回溯 | ★★★ |
| P98 | 数织游戏(Nonograms) | 行约束推理 | ★★★★ |
| P99 | 填字游戏 | 约束搜索、回溯 | ★★★★ |
P90(八皇后)和 P97(数独)是两种经典的回溯问题。用 Haskell 的 do-notation(list monad)可以不到 10 行写完八皇后,这大概是 Haskell 最令人震撼的表达力展示。P98-P99 是真正的大工程,需要良好的算法设计和模块化能力。
1cabal install ninetynine
安装后得到 Problems.* 模块,每个模块里有 myLast、myButLast 这样的函数骨架。
take/drop/group 组合RandomGen 和 State monad,初学者杀手| 阶段 | 题号范围 | 对应 LYAH | 核心收获 |
|---|---|---|---|
| 列表基础 | P01-P10 | Ch1-5 | 递归、模式匹配、Maybe |
| 列表变换 | P11-P20 | Ch4-7 | 自定义类型、take/drop 组合 |
| 组合与随机 | P21-P28 | Ch5-7 | 回溯、惰性列表、State monad |
| 数论 | P29-P45 | 数学 | 惰性筛法、数论基础 |
| 逻辑与编码 | P46-P53 | Ch7 | 布尔逻辑、编码算法、定理证明 |
| 二叉树 | P54-P69 | Ch8 | 自定义 ADT、树遍历、布局 |
| 多路树 | P70-P73 | Ch8 | 多路树、序列化 |
| Monad | P74-P79 | Ch12-13 | monad 深入理解 |
| 图 | P80-P89 | 进阶 | 图算法、DFS/BFS |
| 综合 | P90-P99 | 进阶 | 回溯、list monad、大工程 |
本系列的所有题目文件均在当前目录下,以 pNN.md 命名: