类型级编程实战haskell-exercises中最烧脑的10道HList与Sigma练习题【免费下载链接】haskell-exercisesA little course to learn about some of the more obscure GHC extensions.项目地址: https://gitcode.com/gh_mirrors/has/haskell-exercises类型级编程Type-Level Programming是 Haskell 进阶路上最迷人的岔路口之一。当你已经熟悉 Monad 与 Monoid开始好奇 GHC 扩展究竟能做什么时haskell-exercises 就是为你准备的阶梯。这个开源练习集用 10 个章节带你依次解锁 GADTs、DataKinds、PolyKinds 等冷门扩展其中围绕 HList异构列表与 Sigma 类型依赖对的习题堪称全仓库最烧脑、也最能检验你对类型系统理解的部分。本文挑选其中最考验脑力的 10 道为你逐一点评思路与坑点。什么是 HList 与 Sigma 类型先搞懂两个核心概念在 Haskell 中普通列表要求所有元素类型一致。而HListHeterogeneous List异构列表允许一个列表同时容纳String、Int、Bool等不同类型并且把每个位置是什么类型这一信息直接编码进类型里——这就是类型级编程的典型玩法。Sigma 类型也叫依赖对Dependent Pair则来自依赖类型理论它把一个值和它的类型标签打包在一起。比如Sigma Strings可以装入任意长度的字符串列表同时把长度信息隐藏起来等待使用时再通过模式匹配揭开。这两类结构是 GADTs、DataKinds、PolyKinds 三大扩展的毕业考试下面这 10 道题就是最精华的部分。1. 从零手写一个 HListGADT 的第 6 题这是整个仓库第一道 HList 题位于01-GADTs/src/Exercises.hs的 SIX 部分。题目给出一个用 GADT 定义的 HListdata HList a where HNil :: HList () HCons :: head - HList tail - HList (head, tail)注意它用嵌套元组(head, tail)来编码类型列表且不包含任何存在类型——每个元素类型都暴露在类型参数中。例子的类型长这样HList (String, (Int, (Bool, ())))烧脑点在于它和你熟悉的data List a Nil | Cons a (List a)完全不同递归发生在了类型层面。写第一行代码前请先在纸上画出类型参数的递归树。2. 给 HList 写一个不用 Maybe 的 head紧随其后的 2a 题要求实现一个安全的 head 函数。秘诀是利用类型签名让 GHC 替你做穷尽性检查。如果你把参数类型写为HList (head, tail)那么模式匹配时 GHC 就知道HNil根本不可能出现——因为HNil的类型是HList ()与(head, tail)不匹配。于是你的 head 直接返回元素即可连Maybe都不用包。这道题是对类型即文档最直观的体验。3. 挑战把两个 HList 拼接起来第 2c 题是 HList 系列的第一个深坑。拼接HList a和HList b结果类型是什么直觉会说是HList c但c与a、b的关系是什么在没有类型族TypeFamilies的 GADT 章节里你几乎无法表达把 a 的尾部和 b 接上这个操作——这正是作者埋下的伏笔等你在第 6 章06-TypeFamilies/src/TypeFamilies.hs学到类型族后再回头想想能否用Append类型族解决。4. 把 HList 升级成异构树 HTree第 7 题给出了两个空类型Empty和Branch left centre right要求构建一棵异构树且所有类型变量都不能是存在类型。更难的是 7b写一个删除左子树的函数让 GHC 帮你完成大部分推导。当你试着故意写错实现时会发现类型检查器立刻报错——这正是把断言搬进类型的威力。5. 用 DataKinds 重写 HList类型层面的 List来到第 4 章04-DataKinds/src/Exercises.hs的第 5 题作者要求你用类型层面的List Type重写 HList。打开 DataKinds 后值构造子Nil、Cons被提升promote到类型层面于是data HList (types :: List Type) where -- HNil :: HList Nil -- HCons :: a - HList rest - HList (Cons a rest)相比元组嵌套版本这版类型可读性大增。5b 要求写一个Maybe 自由的 tail——和 head 同理通过模式匹配HCons分支让 GHC 自动排除HNil。5c 的 take 则又是一个想写却写不出来的经典难题因为它需要类型层面的数字运算。6. 用 Sigma 类型打包任意长度的字符串列表跳到第 8 章08-PolyKinds/src/Exercises.hs的第 5 题这里正式引入Sigma 类型。题目先给出一个定长字符串列表 GADTdata Strings (n :: Nat) where SNil :: Strings Z (:) :: String - Strings n - Strings (S n)然后用Sigma Strings把Strings n和它的长度单例SNat n一起打包把长度存在化example :: [Sigma Strings] example [ Sigma SZ SNil , Sigma (SS SZ) (hi : SNil) , Sigma (SS (SS SZ)) (hello : (world : SNil)) ]写Sigma的构造器定义时编译器会通过报错信息一步步引导你——这也是作者设计练习的独特风格。7. 用 PolyKinds 把 Sigma 泛化到任意 kind5b 题是最烧脑的一问为什么Sigma只能用于Nat能否让它对任何 kind的多态工作答案是打开 PolyKinds让Sigma的第一个参数变成f :: k - Type。一旦泛化成功你就拥有了一套通用的依赖对原语可以打包 Bool、Nat、自定义标签……这也是本章标题多态化的用意所在。8. 用 Sigma 类型描述网络通信协议第 6 题是 Sigma 的实战演练模拟一个客户端/服务端通信协议。定义data Label Client | Server再写一个按标签索引的 GADTCommunication (label :: Label)分别持有ClientData或ServerData。然后奇迹发生了——你可以用[Sigma Communication]把两种数据混在一个列表里最后通过模式匹配Sigma构造器取出标签、分拣数据serverLog :: [Sigma Communication] - [ServerData]这模拟了真实网络日志场景把类型安全地混存异构数据做到了极致。9. 用 Sigma 重写 Vector 的 filter还记得第 4 章里那个定长Vector n a吗filter 会改变长度导致类型对不上。5c 题的提示是把Vector a n的类型参数顺序对调然后用Sigma打包过滤结果——长度从编译期定死变成运行时动态但可验证。这是理解存在类型 单例组合拳的必修课。10. 挑战排行榜还有哪些隐藏 BOSS除了上述 8 道主线题HList 与 Sigma 家族还有几个隐藏 BOSS值得挑战TypeAlignedList第 1 章第 10 题让函数链f . g . h的类型对齐本质是函数版 HList。AlternatingList第 1 章第 8 题Bool 和 Int 交替出现的异构列表考验你对 GADT 类型参数的敏感度。StringAndIntList第 4 章第 3 题在类型层面统计 String 和 Int 的数量相当于带计数器的 HList。SmallerThan第 4 章第 9 题构造一个只能容纳小于 n的数的类型为类型安全的(!!)铺路。刷题路线从 GADTs 到 PolyKinds 的正确顺序这个仓库的章节顺序就是最佳刷题路线不要跳着看01-GADTs打好 HList、HTree、类型对齐列表的基础02-04 章FlexibleInstances、KindSignatures、DataKinds 依次解锁重写 HList06-TypeFamilies学会类型族回头解决 HList 拼接问题08-PolyKinds攻下 Sigma 类型完成类型级编程的毕业设计。每个练习目录都有独立的 cabal 文件例如01-GADTs/exercise01.cabal。运行方式很简单进入对应目录后执行cabal repl或stack repl即可交互式刷题也可以用ghcid -c cabal repl实现保存即检查。克隆仓库地址https://link.gitcode.com/i/10d7efcb957d950a7acb4045e30868fd。小结为什么这些题值得烧脑HList 和 Sigma 看起来抽象却是把运行时错误转化为编译期错误的关键思维训练。当你完成第 8 章后会发现自己已经能看懂很多依赖类型库的源码也更能体会那句话——类型级编程不是炫技而是把断言写进类型里。如果你在刷题时卡住参考答案就藏在各章src/Exercises.hs的 answers 分支中。祝刷题愉快【免费下载链接】haskell-exercisesA little course to learn about some of the more obscure GHC extensions.项目地址: https://gitcode.com/gh_mirrors/has/haskell-exercises创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 类型级编程实战：haskell-exercises中最烧脑的10道HList与Sigma练习题
类型级编程实战haskell-exercises中最烧脑的10道HList与Sigma练习题【免费下载链接】haskell-exercisesA little course to learn about some of the more obscure GHC extensions.项目地址: https://gitcode.com/gh_mirrors/has/haskell-exercises类型级编程Type-Level Programming是 Haskell 进阶路上最迷人的岔路口之一。当你已经熟悉 Monad 与 Monoid开始好奇 GHC 扩展究竟能做什么时haskell-exercises 就是为你准备的阶梯。这个开源练习集用 10 个章节带你依次解锁 GADTs、DataKinds、PolyKinds 等冷门扩展其中围绕 HList异构列表与 Sigma 类型依赖对的习题堪称全仓库最烧脑、也最能检验你对类型系统理解的部分。本文挑选其中最考验脑力的 10 道为你逐一点评思路与坑点。什么是 HList 与 Sigma 类型先搞懂两个核心概念在 Haskell 中普通列表要求所有元素类型一致。而HListHeterogeneous List异构列表允许一个列表同时容纳String、Int、Bool等不同类型并且把每个位置是什么类型这一信息直接编码进类型里——这就是类型级编程的典型玩法。Sigma 类型也叫依赖对Dependent Pair则来自依赖类型理论它把一个值和它的类型标签打包在一起。比如Sigma Strings可以装入任意长度的字符串列表同时把长度信息隐藏起来等待使用时再通过模式匹配揭开。这两类结构是 GADTs、DataKinds、PolyKinds 三大扩展的毕业考试下面这 10 道题就是最精华的部分。1. 从零手写一个 HListGADT 的第 6 题这是整个仓库第一道 HList 题位于01-GADTs/src/Exercises.hs的 SIX 部分。题目给出一个用 GADT 定义的 HListdata HList a where HNil :: HList () HCons :: head - HList tail - HList (head, tail)注意它用嵌套元组(head, tail)来编码类型列表且不包含任何存在类型——每个元素类型都暴露在类型参数中。例子的类型长这样HList (String, (Int, (Bool, ())))烧脑点在于它和你熟悉的data List a Nil | Cons a (List a)完全不同递归发生在了类型层面。写第一行代码前请先在纸上画出类型参数的递归树。2. 给 HList 写一个不用 Maybe 的 head紧随其后的 2a 题要求实现一个安全的 head 函数。秘诀是利用类型签名让 GHC 替你做穷尽性检查。如果你把参数类型写为HList (head, tail)那么模式匹配时 GHC 就知道HNil根本不可能出现——因为HNil的类型是HList ()与(head, tail)不匹配。于是你的 head 直接返回元素即可连Maybe都不用包。这道题是对类型即文档最直观的体验。3. 挑战把两个 HList 拼接起来第 2c 题是 HList 系列的第一个深坑。拼接HList a和HList b结果类型是什么直觉会说是HList c但c与a、b的关系是什么在没有类型族TypeFamilies的 GADT 章节里你几乎无法表达把 a 的尾部和 b 接上这个操作——这正是作者埋下的伏笔等你在第 6 章06-TypeFamilies/src/TypeFamilies.hs学到类型族后再回头想想能否用Append类型族解决。4. 把 HList 升级成异构树 HTree第 7 题给出了两个空类型Empty和Branch left centre right要求构建一棵异构树且所有类型变量都不能是存在类型。更难的是 7b写一个删除左子树的函数让 GHC 帮你完成大部分推导。当你试着故意写错实现时会发现类型检查器立刻报错——这正是把断言搬进类型的威力。5. 用 DataKinds 重写 HList类型层面的 List来到第 4 章04-DataKinds/src/Exercises.hs的第 5 题作者要求你用类型层面的List Type重写 HList。打开 DataKinds 后值构造子Nil、Cons被提升promote到类型层面于是data HList (types :: List Type) where -- HNil :: HList Nil -- HCons :: a - HList rest - HList (Cons a rest)相比元组嵌套版本这版类型可读性大增。5b 要求写一个Maybe 自由的 tail——和 head 同理通过模式匹配HCons分支让 GHC 自动排除HNil。5c 的 take 则又是一个想写却写不出来的经典难题因为它需要类型层面的数字运算。6. 用 Sigma 类型打包任意长度的字符串列表跳到第 8 章08-PolyKinds/src/Exercises.hs的第 5 题这里正式引入Sigma 类型。题目先给出一个定长字符串列表 GADTdata Strings (n :: Nat) where SNil :: Strings Z (:) :: String - Strings n - Strings (S n)然后用Sigma Strings把Strings n和它的长度单例SNat n一起打包把长度存在化example :: [Sigma Strings] example [ Sigma SZ SNil , Sigma (SS SZ) (hi : SNil) , Sigma (SS (SS SZ)) (hello : (world : SNil)) ]写Sigma的构造器定义时编译器会通过报错信息一步步引导你——这也是作者设计练习的独特风格。7. 用 PolyKinds 把 Sigma 泛化到任意 kind5b 题是最烧脑的一问为什么Sigma只能用于Nat能否让它对任何 kind的多态工作答案是打开 PolyKinds让Sigma的第一个参数变成f :: k - Type。一旦泛化成功你就拥有了一套通用的依赖对原语可以打包 Bool、Nat、自定义标签……这也是本章标题多态化的用意所在。8. 用 Sigma 类型描述网络通信协议第 6 题是 Sigma 的实战演练模拟一个客户端/服务端通信协议。定义data Label Client | Server再写一个按标签索引的 GADTCommunication (label :: Label)分别持有ClientData或ServerData。然后奇迹发生了——你可以用[Sigma Communication]把两种数据混在一个列表里最后通过模式匹配Sigma构造器取出标签、分拣数据serverLog :: [Sigma Communication] - [ServerData]这模拟了真实网络日志场景把类型安全地混存异构数据做到了极致。9. 用 Sigma 重写 Vector 的 filter还记得第 4 章里那个定长Vector n a吗filter 会改变长度导致类型对不上。5c 题的提示是把Vector a n的类型参数顺序对调然后用Sigma打包过滤结果——长度从编译期定死变成运行时动态但可验证。这是理解存在类型 单例组合拳的必修课。10. 挑战排行榜还有哪些隐藏 BOSS除了上述 8 道主线题HList 与 Sigma 家族还有几个隐藏 BOSS值得挑战TypeAlignedList第 1 章第 10 题让函数链f . g . h的类型对齐本质是函数版 HList。AlternatingList第 1 章第 8 题Bool 和 Int 交替出现的异构列表考验你对 GADT 类型参数的敏感度。StringAndIntList第 4 章第 3 题在类型层面统计 String 和 Int 的数量相当于带计数器的 HList。SmallerThan第 4 章第 9 题构造一个只能容纳小于 n的数的类型为类型安全的(!!)铺路。刷题路线从 GADTs 到 PolyKinds 的正确顺序这个仓库的章节顺序就是最佳刷题路线不要跳着看01-GADTs打好 HList、HTree、类型对齐列表的基础02-04 章FlexibleInstances、KindSignatures、DataKinds 依次解锁重写 HList06-TypeFamilies学会类型族回头解决 HList 拼接问题08-PolyKinds攻下 Sigma 类型完成类型级编程的毕业设计。每个练习目录都有独立的 cabal 文件例如01-GADTs/exercise01.cabal。运行方式很简单进入对应目录后执行cabal repl或stack repl即可交互式刷题也可以用ghcid -c cabal repl实现保存即检查。克隆仓库地址https://link.gitcode.com/i/10d7efcb957d950a7acb4045e30868fd。小结为什么这些题值得烧脑HList 和 Sigma 看起来抽象却是把运行时错误转化为编译期错误的关键思维训练。当你完成第 8 章后会发现自己已经能看懂很多依赖类型库的源码也更能体会那句话——类型级编程不是炫技而是把断言写进类型里。如果你在刷题时卡住参考答案就藏在各章src/Exercises.hs的 answers 分支中。祝刷题愉快【免费下载链接】haskell-exercisesA little course to learn about some of the more obscure GHC extensions.项目地址: https://gitcode.com/gh_mirrors/has/haskell-exercises创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考