结构归纳 haskell

Question

我想知道如何在结构归纳中显示列表 xs ，或者归纳如何在其中工作：

map f (map g xs) = map (\x -> f(g x)) xs

用这个函数定义

  map :: ( a -> b ) -> [ a ] -> [ b ]

  map _ [] = []

  map f ( x : xs ) = f x : map f xs

是不是像数学归纳法？

提前致谢

Answer 1

结构归纳法是归纳法数学概念的概括。数学归纳法特别适用于自然数，并将情况分为两种情况：数字为零的情况，以及它比任何其他数字大 1 的情况。具体来说，这个对应的是Peano definition of natural numbers，可以写成Haskell如下。

data Nat = Zero | Succ Nat

因此，对该数据类型的归纳证明分为两种情况，一种用于每种类型构造函数。第一个说“假设我们有一个Zero；证明它”。第二个说“假设我们有一个Succ n，其中n的工作已经完成；现在证明它”。

现在您想通过列表归纳地证明一些事情。列表类型可以写成（模语法糖）为

data [a] = [] | a : [a]

准确地说，这对应于以下（无魔法）定义

data List a = Nil | Cons a (List a)

尽管我会使用第一个，因为在 Haskell 中使用它更简洁一些。 [a] 上的结构归纳证明应分为两种情况：

假设列表为空。证明命题。
假设列表是非空的，并且我们想要证明的任何东西对于尾部都是正确的。证明整个列表的陈述。

所以让我们将其应用到 map。这是您的 map 函数。

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x : xs) = f x : map f xs

而我们要证明的是，准确地写成：

Let f :: b -> c and g :: a -> b be arbitrary functions. Then prove that, for any list xs :: [a], we have
map f (map g xs) = map (\y -> f (g y)) xs 

让我们开始吧。有两种情况。首先，假设 xs 为空，即 xs == []。然后，直接从上面的函数定义，我们知道 map g xs == map g [] == [] 和 f 相同，所以我们有以下等价关系

map f (map g [])
map f []
[]
map (\y -> f (g y)) []

这些推导中的每一个都来自 map 的定义，因为我们完全理解 map 对空列表的作用（即，它什么都不做，并且功能没有区别）。这样第一个案例就完成了。

现在，归纳步骤。假设我们有一个列表 (x : xs)，并假设 xs 的陈述是正确的。所以我们假设

map f (map g xs) == map (\y -> f (g y)) xs

我们想证明

map f (map g (x : xs)) == map (\y -> f (g y)) (x : xs)

那么让我们一步一步来。

map f (map g (x : xs))
map f (g x : map g xs)           -- By the function definition
f (g x) : map f (map g xs)       -- By the function definition
f (g x) : map (\y -> f (g y)) xs -- By induction hypothesis
map (\y -> f (g y)) (x : xs)     -- By the function definition

因此，该声明成立。

通过结构归纳，该陈述适用于 []，并且假设该陈述适用于 xs，它也适用于 x : xs。因此，我们可以得出结论，它适用于所有有限列表。

结构归纳法不强大到足以证明它适用于无限列表。 Haskell 的 [a] 类型（实际上 Haskell 通常）是归纳法和共归纳法的奇怪组合，这使得对此的正式数学证明有点尴尬。严格按照归纳定义，类型 [a] 应该不会有任何无限的情况，所以我们不必为了这个证明的目的而担心它们。

结构归纳 haskell

Structural induction haskell

haskell

induction

map-function