为什么将此递归映射函数仅应用于列表中的最后两个元素? [英] Why is this recursive map function only being applied to the last two elements in the list?

问题描述

这是给出的问题:下表中的前8个元素是什么?

This is the problem given: What are the first 8 elements in the following list?

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

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

但是我认为答案应该是[0,10,1,11,1,11,2,12].以下步骤说明了原因:

But in my opinion the answer should be [0,10,1,11,1,11,2,12]. The following steps show why:

1)我们得到了; list [0,10]，因此在第一次应用该函数后，我们有了列表[0,10,1, 11] 2)现在我们有了列表[0,10,1,11]，因此再次应用该函数后，结果列表应为[0,10,1,11,1,11,2,12]

1) We are given ;list [0,10] so after applying the function the first time we have the list [0,10,1, 11] 2) Now we have a list [0,10,1,11] so after applying the function again the resulting list should be [0,10,1,11,1,11,2,12]

显然不是这样.谁能解释为什么?

Apparently that is not the case. Can anyone explain why?

推荐答案

在深入探讨mystery的定义之前，让我们看一下map遵守的定律之一:

Before diving into the definition of mystery, let's take a look at one of the laws map obeys:

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

此法的非正式证明很容易遵循:

A rather informal proof of this law is easy to follow:

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开始 ，其余元素以递归方式定义.

You don't start with a finite list [0, 10]; you start with an infinite list that begins with 0 and 10, with the remaining elements defined recursively.

从某种意义上说，列表没有封闭的形式，但这没关系；懒惰意味着您仅在需要时将map应用于mystery才能获得请求的项目.例如，head mystery和head (tail mystery)都不需要评估对map的调用，并且head (tail (tail mystery))只需要将(+1)映射到head mystery，而不是整个无限列表.

In some sense, there is no closed form for the list, but that doesn't matter; laziness means that you only apply map to mystery as needed to get requested items. For example, neither head mystery nor head (tail mystery) ever need to evaluate the call to map, and head (tail (tail mystery)) only needs to map (+1) to the head mystery, not the entire infinite list.

懒惰模糊了列表与计算列表的算法之间的区别.

Laziness blurs the distinction between the list and the algorithm to compute the list.

这篇关于为什么将此递归映射函数仅应用于列表中的最后两个元素?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！