时间戳

首页 > 解决方案 > 为什么这个递归映射函数只应用于列表中的最后两个元素？

list - 为什么这个递归映射函数只应用于列表中的最后两个元素？

问题描述

这是给出的问题：以下列表中的前 8 个元素是什么？

mystery = 0 : 10 : (map(+1)mystery)

答案是[0,10,1,11,2,12,3,13...]

但在我看来，答案应该是[0,10,1,11,1,11,2,12]。以下步骤说明了原因：

1) 我们得到 ;list[0,10]所以在第一次应用函数之后我们有列表 [ 0,10,1, 11] 2) 现在我们有一个列表 [0,10,1,11]所以在再次应用函数之后结果列表应该是[0,10,1,11,1,11,2,12]

显然情况并非如此。谁能解释为什么？

标签： listhaskelllazy-evaluationmap-functionlazy-sequences

解决方案

在深入了解 的定义之前mystery，让我们看一下map遵循的其中一条定律：

map f (map g xs) == map (f . g) xs

该定律的一个相当非正式的证明很容易理解：

map f (map g [x1, x2, ..., xn]) == map f [g x1, g x2, ..., g xn]
                                == [f (g x1), f (g x2), ..., f (g xn)]
                                == [(f.g) x1, (f.g) x2, ..., (f.g) xn]
                                == map (f.g) [x1, x2, ..., xn]

考虑到这一点，让我们mystery逐步扩展：

mystery == 0 : 10 : map (+1) mystery
        -- by definition of mystery
        == 0 : 10 : map (+1) (0 : 10 : map (+1) mystery)
        -- by definition of map and the fact that  0 + 1 == 1
        == 0 : 10 : 1 : map (+1) (10 : map (+1) mystery)
        -- by definition of map and the fact that 10 + 1 == 11
        == 0 : 10 : 1 : 11 : map (+1) (map (+1) mystery)
        -- using the law above, and the fact that (+1) . (+1) == (+2)
        == 0 : 10 : 1 : 11 : map (+2) mystery
        == 0 : 10 : 1 : 11 : map (+2) (0 : 10 : map (+1) mystery)
        == 0 : 10 : 1 : 11 : 2 : map (+2) (10 : map (+1) mystery)
        == 0 : 10 : 1 : 11 : 2 : 12 : map (+2) (map (+1) mystery)
        == 0 : 10 : 1 : 11 : 2 : 12 : map (+3) mystery
        -- etc

您不是从有限列表开始的[0, 10]；您从一个以 0 和 10 开头的无限列表开始，其余元素以递归方式定义。

从某种意义上说，列表没有封闭形式，但这没关系；懒惰意味着您仅根据需要申请map以mystery获取请求的项目。例如，既不需要head mystery也head (tail mystery)永远不需要评估对 的调用map，head (tail (tail mystery))只需要映射(+1)到head mystery，而不是整个无限列表。

懒惰模糊了列表和计算列表的算法之间的区别。

推荐阅读