函数式与逻辑编程

默认只展示每周独有的知识重点；节奏、考核、Tutorial 和避坑信息按需展开。

1. 1

   Introduction to Functional Programming & Haskell

   ### 🔀 核心知识点：函数式编程与 Haskell 入门 本周介绍函数式编程范式和 Haskell 语言。FP 的核心思想 — 用数学函数的方式思考编程。课程使用 exercism.io 平台练习。 - **核心概念**: Imperative vs Functional paradigm, Haskell installation (GHCup, Stack), GHCi REPL, basic types (Int, Bool, Char, String), function definition syntax, pattern matching basics, exercism.io setup ⏰ **本周节奏**: 难度 ⭐⭐⭐ | 预计投入 9h（Lecture 2h + Tutorial 1h + Practical 1h + 自学 3h + exercism 2h） 🎯 **考试关联**: Lab Exam 会考 Haskell 编程，从本周开始练习 exercism 题目 🧪 **Practical**: 在 exercism.io 完成 Haskell track 的前 3-5 道入门题（Hello World, Leap, Bob） 📌 **作业关联**: Assignments 都用 Haskell 实现，本周打牢基础 ⚠️ **易错点**: Haskell 缩进敏感（类似 Python）；函数应用不用括号 `f x` 不是 `f(x)`；类型推断可能导致新手困惑

   Imperative vs Functional paradigmHaskell installation (GHCupStack)GHCi REPLbasic types (Int
2. 2

   Types, Type Classes & Polymorphism

   ### 📐 核心知识点：类型系统与多态 本周深入 Haskell 的类型系统 — FP 语言最强大的武器。强类型 + 类型推断让编译器在运行前就能发现大量错误。 - **核心概念**: Type annotations (::), basic types, function types (a -> b), type variables (polymorphism), type classes (Eq, Ord, Show, Num), class constraints, deriving, type vs newtype vs data ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 10h（Lecture 2h + Tutorial 1h + Practical 1h + 自学 4h + exercism 2h）🔥 概念密集 🎯 **考试关联**: Type signature 的读写和 type class 的理解是 Lab Exam 核心内容 🧪 **Practical**: exercism 题目（Accumulate, Nucleotide Count）；手动推导函数类型签名 📌 **作业关联**: Assignment 1 需要正确编写类型签名 ⚠️ **易错点**: `[Char]` 和 `String` 是同一个类型；type class 不是 OOP 的 class（是约束，不是继承）

   Type annotations (::)basic typesfunction types (a -> b)type variables (polymorphism)type classes (Eq
3. 3

   Lists, Recursion & Higher-Order Functions

   ### 🔄 核心知识点：列表、递归与高阶函数 本周学习 FP 的三大核心技术：列表处理、递归和高阶函数。在 Haskell 中，递归取代了循环。 - **核心概念**: List syntax and operations (: cons, ++ append), list comprehensions, recursion (base case + recursive case), tail recursion, map/filter/foldr/foldl, function composition (.), lambda expressions (\x -> ...) ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 10h（Lecture 2h + Tutorial 1h + Practical 1h + 自学 4h + exercism 2h） 🎯 **考试关联**: foldr/foldl 的行为差异和递归函数编写是 Lab Exam 必考 🧪 **Practical**: exercism (Matrix, Anagram, ETL)；实现自定义 map 和 filter 用 foldr 📌 **作业关联**: Assignment 1 大量使用 list 处理和高阶函数 ⚠️ **易错点**: foldl 在 Haskell 中有空间泄漏问题（用 foldl' 代替）；无限列表 + 非 lazy 消费 = 永不终止

   List syntax and operations (: cons++ append)list comprehensionsrecursion (base case + recursive case)tail recursion
4. 4

   Algebraic Data Types & Pattern Matching

   ### 🧩 核心知识点：代数数据类型与模式匹配 本周学习 Haskell 的自定义类型 — ADT（Algebraic Data Types）。Sum types + Product types 是表达复杂数据的强大工具。 - **核心概念**: data keyword, Sum types (Either, Maybe), Product types (tuples, records), pattern matching (case expressions, guards), recursive data types (自定义 Tree, List), Maybe/Either for error handling ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 10h（Lecture 2h + Tutorial 1h + Practical 1h + 自学 4h + Assignment 1 2h） 🎯 **考试关联**: ADT 的定义和 pattern matching 是 Lab Exam 高频考点 🧪 **Practical**: 定义二叉树 ADT，实现 insert/search/traversal；exercism (Binary Search Tree) 📌 **作业关联**: Assignment 1 发布 — 需要定义和使用自定义 ADTs ⚠️ **易错点**: Pattern matching 的顺序很重要（先匹配的先执行）；忘记处理 Nothing 导致 partial function

   data keywordSum types (EitherMaybe)Product types (tuplesrecords)
5. 5

   IO, Monads & Side Effects

   ### 🌀 核心知识点：IO、Monad 与副作用 本周是 Haskell 最抽象也最精华的部分 — Monad。理解 Monad 是掌握 Haskell 的分水岭。 - **核心概念**: Pure functions vs side effects, IO Monad (IO a), do notation, >>= (bind) operator, return, Functor → Applicative → Monad hierarchy, Maybe Monad, Either Monad, monad laws ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐⭐ | 预计投入 12h（Lecture 2h + Tutorial 1h + Practical 1h + 自学 5h + Assignment 1 3h）🔥 课程最难周之一 🎯 **考试关联**: Monad 的概念和 do notation 的翻译（desugaring）是 Exam 核心 🧪 **Practical**: 编写 IO 程序（读写文件、用户输入）；用 Maybe Monad 链式处理可能失败的操作 📌 **作业关联**: Assignment 1 截止临近 ⚠️ **易错点**: Monad 不是 "包装盒" — 是一种计算上下文的抽象；do notation 只是语法糖（>>=的语法糖）；IO a 不是 "不纯"，是 "描述副作用的纯值"

   Pure functions vs side effectsIO Monad (IO a)do notation>>= (bind) operatorreturn
6. 6

   Lazy Evaluation & Infinite Data Structures

   ### ♾️ 核心知识点：惰性求值与无限数据结构 本周学习 Haskell 的求值策略 — Lazy Evaluation。这是 Haskell 与其他语言最根本的区别之一。 - **核心概念**: Lazy evaluation vs strict evaluation, thunks, call-by-need vs call-by-value, infinite lists ([1..], iterate, repeat), take/takeWhile with infinite lists, strictness annotations (!), seq, space leaks ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 10h（Lecture 2h + Tutorial 1h + Practical 1h + 自学 4h + 复习 2h） 🎯 **考试关联**: Lazy evaluation 的求值顺序 trace 是 Exam 常见题型 🧪 **Practical**: 用无限列表实现 Fibonacci 序列、Sieve of Eratosthenes；分析 thunk 累积 📌 **作业关联**: 理解 laziness 避免 Assignment 中的空间泄漏 ⚠️ **易错点**: foldl 在大列表上 thunk 累积导致 stack overflow（用 foldl'）；Debug lazy evaluation 非常困难

   Lazy evaluation vs strict evaluationthunkscall-by-need vs call-by-valueinfinite lists ([1..]iterate
7. 7

   Introduction to Logic Programming (Prolog)

   ### 🧮 核心知识点：逻辑编程入门（Prolog） 本周从 FP 转向 LP（Logic Programming）。Prolog 用逻辑推理而非命令式步骤来解决问题。 - **核心概念**: Declarative programming paradigm, Prolog syntax (facts, rules, queries), unification, backtracking, SWI-Prolog setup, simple queries and knowledge bases, comparison: Haskell vs Prolog ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 10h（Lecture 2h + Tutorial 1h + Practical 1h + 自学 4h + Prolog 入门 2h）🔥 范式切换 🎯 **考试关联**: Prolog 的 unification 和 backtracking 机制是 Exam 必考 🧪 **Practical**: 在 SWI-Prolog 中编写 family relationship 知识库和查询 📌 **作业关联**: Assignment 2 通常需要 Prolog 编程 ⚠️ **易错点**: Prolog 变量大写开头（不是小写）；unification 不是赋值 — X = 3 是声明 X 与 3 统一；backtracking 可能导致意外多个解

   Declarative programming paradigmProlog syntax (factsrulesqueries)unification
8. 8

   Prolog: Lists, Recursion & Search

   ### 🔍 核心知识点：Prolog 列表、递归与搜索 本周深入 Prolog 编程技巧。列表处理和递归在 Prolog 中与 Haskell 有相似也有不同。 - **核心概念**: Prolog lists ([H|T] pattern), append/member/length predicates, recursive Prolog programs, accumulator pattern, Prolog search strategy (DFS with backtracking), cut (!), negation as failure (\+) ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 10h（Lecture 2h + Tutorial 1h + Practical 1h + 自学 4h + Assignment 2 2h） 🎯 **考试关联**: Prolog 列表递归和 cut 的行为是 Exam 高频考点 🧪 **Practical**: 实现 Prolog 版的 reverse、sort、permutation；练习用 cut 控制搜索 📌 **作业关联**: Assignment 2 发布 — Prolog 编程任务 ⚠️ **易错点**: Cut (!) 不当使用会 "剪断" 正确答案；\+ 不是逻辑否定而是 "无法证明"；Prolog 对变量的 scope 规则与 Haskell 不同

   Prolog lists ([H|T] pattern)append/member/length predicatesrecursive Prolog programsaccumulator patternProlog search strategy (DFS with backtracking)
9. 9

   Computational Models & Lambda Calculus

   ### 📐 核心知识点：计算模型与 Lambda 演算 本周进入课程的理论核心 — 计算模型。Lambda Calculus 是函数式编程的数学基础。 - **核心概念**: Lambda calculus (λ-expressions, α-conversion, β-reduction), Church encoding (numbers, booleans), fixed-point combinators (Y combinator), Turing completeness, Church-Turing thesis, computation models comparison ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐⭐ | 预计投入 12h（Lecture 2h + Tutorial 1h + Practical 1h + 自学 5h + 理论推导 3h）🔥 理论高压周 🎯 **考试关联**: β-reduction 的手动执行和 Church encoding 是 Exam 高频考点 🧪 **Practical**: 手动执行 λ-expression 的 β-reduction；用 Church numerals 实现加法和乘法 📌 **作业关联**: Assignment 2 进行中 ⚠️ **易错点**: β-reduction 中变量捕获问题（需要 α-conversion 重命名）；Y combinator 在 strict 语言中会无限循环

   Lambda calculus (λ-expressionsα-conversionβ-reduction)Church encoding (numbersbooleans)
10. 10

    Type Theory & Formal Verification

    ### 📋 核心知识点：类型理论与形式化验证 本周探索类型系统的理论基础。类型不只是编程工具，更是数学证明的手段。 - **核心概念**: Curry-Howard correspondence (types ↔ propositions, programs ↔ proofs), dependent types (概念), type safety and soundness, Hindley-Milner type inference, parametric polymorphism vs ad-hoc polymorphism ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐⭐ | 预计投入 11h（Lecture 2h + Tutorial 1h + Practical 1h + 自学 5h + Assignment 2 冲刺 2h）🔥 高压周 🎯 **考试关联**: Curry-Howard 对应和类型推断算法是 Exam 考点 🧪 **Practical**: 用 Haskell 类型系统 "证明" 简单命题；手动执行类型推断 📌 **作业关联**: Assignment 2 截止临近 ⚠️ **易错点**: Curry-Howard 是概念对应不是直接翻译；Hindley-Milner 只能推断 rank-1 types

    Curry-Howard correspondence (types ↔ propositionsprograms ↔ proofs)dependent types (概念)type safety and soundnessHindley-Milner type inference
11. 11

    Language Comparison & Semantics

    ### ⚖️ 核心知识点：语言比较与语义学 本周对比不同编程范式的优劣：函数式 vs 逻辑式 vs 命令式。讨论可扩展性、可验证性和效率的权衡。 - **核心概念**: Extensibility vs verifiability vs efficiency tradeoffs, operational semantics (big-step, small-step), denotational semantics (概念), referential transparency, side-effect management across paradigms, multi-paradigm languages (Scala, OCaml, Rust) ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 10h（Lecture 2h + Tutorial 1h + Practical 1h + 自学 4h + 复习 2h） 🎯 **考试关联**: 语言范式对比和 semantics 概念是 Exam 常考论述题 🧪 **Practical**: 用 Haskell、Prolog 和 Python 实现同一个问题，对比代码风格和可读性 📌 **作业关联**: 所有 assignments 已截止 ⚠️ **易错点**: 没有 "最好的" 范式 — 每种范式有其最擅长的问题域；referential transparency 不代表 "没有副作用"，而是 "可替换性"

    Extensibility vs verifiability vs efficiency tradeoffsoperational semantics (big-stepsmall-step)denotational semantics (概念)referential transparency
12. 12

    Advanced Topics & Exam Preparation

    ### 📝 核心知识点：高级话题与考试准备 最后一周覆盖现代 FP 在工业界的应用，并系统复习全课程内容。 - **核心概念**: FP in industry (Haskell at Facebook/Meta, Erlang/Elixir, Scala at data companies), property-based testing (QuickCheck), effect systems, comprehensive review: Haskell core + Prolog core + Lambda Calculus + Type Theory ⏰ **本周节奏**: 难度 ⭐⭐⭐ | 预计投入 12h（Lecture 2h + Tutorial 1h + Practical 1h + Lab Exam 准备 8h）📝 复习周 🎯 **考试关联**: Lab Exam 需要在限定时间内用 Haskell/Prolog 编程。重点复习：递归函数编写、ADT 定义和 pattern matching、Monad 使用、Prolog unification 和 backtracking、Lambda Calculus β-reduction 🧪 **Practical**: 模拟 Lab Exam 环境练习，限时完成 Haskell/Prolog 编程题 📌 **作业关联**: Lab Exam 是最终评估的重要组成 ⚠️ **易错点**: Lab Exam 时间紧张 — 先做有把握的题；Haskell 编译错误信息有时很难读，提前熟悉常见错误模式

    FP in industry (Haskell at Facebook/MetaErlang/ElixirScala at data companies)property-based testing (QuickCheck)effect systems