理论题
题干
traverse 是 Haskell 语言的一个重要函数。其类型为：
(a -> f b) -> t a -> f (t b)
示例：
traverse (\a -> if a > 0 then Just a else Nothing) [1, 2, 3, 4]
上例可以得到 Just [1, 2, 3, 4]。
问题：
- 将上例中的
[1, 2, 3, 4]变成[-1, 2, 3, 4]会得到什么？ - 根据类型信息，将函数应用到
a后得到的应该是t (f b)。请说明你的疑问，并给出猜测。 提示：traverse要求在类型t上定义“某个操作”。请说明该操作的作用，并推断当t = List时其实现。用自然语言描述即可。 traverse (\i -> [0..i]) [0, 1, 2, 3]会得到什么？- 本题预设
t是一个满足某个约束的类型。请分析本题语境，猜测t需要满足的约束。 提示：本题把将a -> f b应用到t a上看成应用到内部a上。
材料和解释
abft都是类型变量（即不是某个特定的类型，而是一系列可行的类型）。其中，tf可以看成接收类型而给出类型的类型，可以视为某种“上下文”类型，即它为内部类型赋予了额外的信息。例如，[Int]为整型添加了数组这一上下文，使得它可以表示多个整型，换句话说表示了“类型为整型的可能性”这样一个类型。- 从语义上讲，
traverse作用在于，假如对于某一个被上下文t包裹的a进行操作导致产生了新的上下文f，其可以将上下文f提到外部，并保留内部t的结构。 - 示例表达式该使得
traverse的类型实例化（用具体类型取代）到了(Int -> Maybe Int) -> [Int] -> Maybe [Int]。 type Maybe a = Just a | Nothing。Maybe表示“可能不存在”，List（通常也表示为[]）表示“多种可能”。- 在某种约束下，上下文类型
f允许以下函数的存在：f (a -> b) -> f a -> f b。- 显然，函数可以被推广到任意元数。
Maybe和List都是符合条件的f。其中：- 在
Maybe上的该函数的语义为：如果被包裹在上下文中的函数或值有任意一个不存在，则结果不存在。 List上的该函数的语义为：被包裹在上下文中的函数（们）和值（们）进行组合并应用。
- 柯里化：任何函数都是一元函数。多元函数到等价一元函数的转换被称为“柯里化”。柯里化步骤如下：消费一个元，并给出一个消费剩下元而后给出结果的函数。
f(a,b) = a + b柯里化后可以读成“给定某个a，可以得到一个函数，这个函数是：给定一个b，得到a + b”。注意，第二个函数给出的结果中的a是被第一个函数的参数“约束”了的。这种“越级现象”称为“函数闭包”。柯里化是基于函数闭包的。- 在
Haskell中，a -> b -> c就可以视为接收任意类型a的变量，再接收任意类型b的变量，最后给出任意类型c的变量的“二元函数”。显然，->符号是右结合的，也就是说，它等价于a -> (b -> c)，而不是(a -> b) -> c。
Haskell中的 lambda 表达式\a -> c表示接收a作为参数，给出c。