Haskell 99 题学习路线

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 aSingle/Multiple
P12解码游程编码replicateconcatMap
P13直接实现游程编码不用中间子列表,边遍历边计数★★
P14复制每个元素concatMapreplicate
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按子列表长度排序 / 按出现频率排序sortOngroup . sortcomparing★★
阶段要点

P26 是经典回溯题,用 list comprehension 写比 C++ 的 for 循环嵌套清爽太多。P23-P25 涉及随机性,Haskell 的纯函数随机数(State monad)跟命令式语言完全不同,这一关是思维转换节点。如果卡住,可以暂时跳过 P23-P25 先往后走,回来再看。

第四阶段:数论(P29-P45)

这个阶段跟 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 开始的高斯整数部分对数学兴趣浓厚者值得深入。

第五阶段:逻辑与编码(P46-P53)

覆盖 LYAH:Ch7(模块)、Ch11(Functors/Applicative/Monoids)

题号题目核心语法推荐
P46逻辑表达式真值表递归布尔运算★★
P47通用逻辑门电路模拟、组合逻辑★★★
P48n 元布尔函数真值表高阶函数、列表推导★★
P49格雷码递归构造、位运算★★
P50霍夫曼编码树构建、优先队列★★★
P51纠错码编码/解码算法★★★★
P52合取范式Formula ADT、递归转换★★★
P53归结原理自动定理证明★★★★
阶段要点

P49 (格雷码) 和 P50 (霍夫曼编码) 是经典的编码/压缩算法,用 Haskell 的表达力写出来非常清爽。P52-P53 涉及命题逻辑和自动定理证明的初步知识,适合对形式逻辑感兴趣的读者。

第六阶段:二叉树(P54-P69)

覆盖 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 的布局问题则极好地训练了递归思考能力。

第七阶段:多路树(P70-P73)

覆盖 LYAH:Ch8(自定义类型)

题号题目核心语法推荐
P70从节点字符串构造树字符串解析、递归★★
P71树的内部路径长度递归遍历、路径累加★★
P72树的后序遍历后序递归★★
P73树的 S 表达式表示括号表示法、递归序列化★★★
阶段要点

多路树(Multiway Tree)是每个节点可以有任意多个子节点的树。P70 的字符串解析和 P73 的 S 表达式是实践中常见的序列化场景。

第八阶段:Monad(P74-P79)

覆盖 LYAH:Ch12-13(Monad)

题号题目核心语法推荐
P74不用 do 记法的 IO monad>>= / >>、纯函数式 IO★★★
P75Maybe monadMaybe 链式操作★★
P76Either monadEither 错误处理★★
P77List monad非确定性计算★★
P78Collatz 猜想递归终止性★★
P79后缀表达式栈计算、fold★★★
阶段要点

这一阶段是 Haskell 从 “好用的函数式语言” 到 “理解其核心抽象” 的跨越。P74 强制你不用 do 语法,直接操作 >>=,这是理解 IO 内部机制的必经之路。P77 的 List monad 是八皇后等回溯问题的语法糖基础。

第九阶段:图(P80-P89)

难度开始爬升,需要额外的数据结构知识。

题号题目核心语法推荐
P80图的表示转换ADT 设计★★
P81两点间所有路径DFS、回溯★★★
P82包含指定顶点的环DFS + 路径记录★★★
P83构造生成树图搜索★★★
P84构造最小生成树(Prim)优先队列、贪心★★★
P85图同构判断组合搜索★★★★★
P86图着色贪心 + 回溯★★★
P87深度优先遍历状态标记、递归★★
P88连通分量DFS 遍历★★
P89二分图判断BFS 染色★★
阶段要点

图的部分整体可以对大多数学习者放最后做,因为需要很多额外的数据结构知识。P85(图同构)是 NP-hard 问题,纯粹学术挑战,可以跳过。

第十阶段:综合难题(P90-P99)

难度最高,涵盖算法和工程实践。

题号题目核心语法推荐
P90n 皇后问题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.* 模块,每个模块里有 myLastmyButLast 这样的函数骨架。

学习节奏

哪些可以跳过

总结

阶段题号范围对应 LYAH核心收获
列表基础P01-P10Ch1-5递归、模式匹配、Maybe
列表变换P11-P20Ch4-7自定义类型、take/drop 组合
组合与随机P21-P28Ch5-7回溯、惰性列表、State monad
数论P29-P45数学惰性筛法、数论基础
逻辑与编码P46-P53Ch7布尔逻辑、编码算法、定理证明
二叉树P54-P69Ch8自定义 ADT、树遍历、布局
多路树P70-P73Ch8多路树、序列化
MonadP74-P79Ch12-13monad 深入理解
P80-P89进阶图算法、DFS/BFS
综合P90-P99进阶回溯、list monad、大工程

文件索引

本系列的所有题目文件均在当前目录下,以 pNN.md 命名: