时髦的哈斯克尔懒惰列表隐式递归 [英] Funky haskell lazy list implicit recursion

问题描述

在Haskell中，由于懒惰，你可以创建无限列表：

  Prelude>让g = 4：g 
前奏> G ！！ 0 
 4 
前奏> 10 g 
 [4,4,4,4,4,4,4,4,4,4,4] 
  

现在，当我尝试构建这样的列表时，到底发生了什么？

让f = f！ 10：f
前奏> F ！！ 0
中断。
前奏> 10 f
[中断。
前奏>

Interrupted。 s是我击中CTRL + C等待几秒钟后。它似乎陷入了一个无限循环，但为什么会出现这种情况？

---

对非Haskellers的解释：

：运算符是 prepend ：

 前奏> 4：[1，2，3] 
 [4,1,2,3] 
  

这一行：

  Prelude>让g = 4：g 
  

表示let g 是通过将 4 加入列表 g 而构建的列表。当你要求第一个元素时，返回4，因为它已经在那里。当你询问第二个元素时，它会查找4之后的元素。该元素将成为我们刚刚计算出的列表 g 的第一个元素，所以返回 4 。下一个元素是 g 的第二个元素，我们再次计算出来等等...

!! 只是索引到一个列表中，所以这意味着从 g获得索引 0 的元素：

  Prelude> G ！！ 0 
 4 
  

但是当我这样做时：

  Prelude>让f = f！ 10：f 
  

由于要计算 f 你需要第11个元素，它还不存在？我希望有一个例外，但不是无限循环...

解决方案

在这种情况下，图片可能会显示一千首先，请记住cons（（：）列表构造函数）是如何工作的。这是一对两件事：一个元素和一个对列表尾部的引用（这是另一个cons，或者 [] ）。

正如你应该知道的那样，当你说 [1，2，3] 时，它只是（1： （2：（3：[]）））或 1：2：3：[] 。如果您将每个反作用对形象化为两个插槽的框，则此表达式如下所示：

 ────┬──┐ ┌──────┐┐──────┐┐────┐
│1│─┼─>│2│─┼─>│3│§┼─> │[]│
└───┴──┘└───┴──┘└───┴──┘└────┘
  

一个循环

当您说 g = 4时：g ，你并没有真正构建一个无限列表，你正在构建一个循环列表： g 被定义为










$ p $ ┌───────────
│┌──────┐│
└>│4│─┼─┘
└───┴──┘


这其实与懒惰没有关系，参考：例如，哟你可以使用像'＃1 =（4。＃1＃）（其中＃1）这样的语法在（紧急）Common Lisp中做同样的事情就像 g ）。

无论你说 g ！ 0 或 g !! 1000000000000 ， g 永远不会增长：（!!）放置的次数与你告诉它的次数一样多，直到它耗尽自身并返回元素 4 。

两个循环

当您说 f =（f !! 10）：f 时，会发生同样的情况 - 除了现在，元素槽包含与 4 不同的表达式：

  ┌──────────┐
│┌───┬──┐│
└>│╷│─┼─┘
└─┼─┴─ ─┘
│
│┌───────────┐
└>│（f !! 10）│
└───── ──────┘
  

至关重要的是，这个子表达式也引用回到 f ，就像尾巴一样：

 ┌─ ─────────┐
│┌───┬──┐│
┌┴>│╷│─ ┼─┘
│└─┼─┴──┘
││
││┌───────────┐
│└└││ （f !! 10）│
│└──┼────────┘
└─────────┘
  

所以，当你要求 f !! n ，（!!）将首先围绕顶部循环 n 次运行，然后返回元素，就像它为 g 所做的那样。然而，并不是转义循环，而是重复输入它，并重复循环：循环10次循环，然后在循环中循环10次底部和背部。

In Haskell, you can build infinite lists due to laziness:

Prelude> let g = 4 : g
Prelude> g !! 0
4
Prelude> take 10 g
[4,4,4,4,4,4,4,4,4,4]

Now, what exactly goes on when I try to construct a list like this?

Prelude> let f = f !! 10 : f
Prelude> f !! 0
Interrupted.
Prelude> take 10 f
[Interrupted.
Prelude>

The Interrupted.s are me hitting CTRL+C after waiting a few seconds. It seems to go into an infinite loop, but why is that the case?

---

Explanation for non-Haskellers:

The : operator is prepend:

Prelude> 4 : [1, 2, 3]
[4,1,2,3]

This line:

Prelude> let g = 4 : g

says "let g be the list constructed by prepending 4 into the list g". When you ask for the first element, 4 is returned, as it's already there. When you ask for the second element, it looks for the element after 4. That element would be the first element of the list g, which we just calculated (4), so 4 is returned. The next element is the second element of g, which we again just calculated, etc...

!! is just indexing into a list, so this means get the element at index 0 from g:

Prelude> g !! 0
4

But when I do this:

Prelude> let f = f !! 10 : f

something breaks, because to compute the first element of f you need the 11th element, which doesn't exist yet? I would expect an exception, though, not an infinite loop...

解决方案

In this case, a picture may tell a thousand words.

First, remember how cons (the (:) list constructor) works. It's a pair of two things: an element, and a reference to a list tail (which is either another cons, or []).

As you should know, when you say [1, 2, 3], it's just a shortcut for (1:(2:(3:[]))) or 1:2:3:[]. If you visualize each cons pair as a box with two slots, this expression look like:

┌───┬──┐  ┌───┬──┐  ┌───┬──┐  ┌────┐
│ 1 │ ─┼─>│ 2 │ ─┼─>│ 3 │ ─┼─>│ [] │
└───┴──┘  └───┴──┘  └───┴──┘  └────┘

One loop

When you say g = 4 : g, you're not really building an "infinite" list, you're building a circular list: g is defined as a cons whose tail reference simply points back to g itself:

┌──────────┐
│ ┌───┬──┐ │
└>│ 4 │ ─┼─┘
  └───┴──┘

This actually has nothing to do with laziness, and everything with self-reference: for example, you can do the same thing in (eager) Common Lisp using syntax like '#1=(4 . #1#) (where the #1 is like g).

Whether you say g !! 0, or g !! 1000000000000, g never grows: (!!) simply runs around the loop in-place, for as many times as you told it to, until it exhausts itself and returns the element, 4.

Two loops

When you say f = (f !! 10) : f, the same thing happens—except now, the element slot contains a different expression than 4:

┌──────────┐
│ ┌───┬──┐ │
└>│ ╷ │ ─┼─┘
  └─┼─┴──┘
    │
    │ ┌───────────┐
    └>│ (f !! 10) │
      └───────────┘

Crucially, this sub-expression also refers back to f, just like the tail does:

 ┌──────────┐
 │ ┌───┬──┐ │
┌┴>│ ╷ │ ─┼─┘
│  └─┼─┴──┘
│    │
│    │ ┌───────────┐
│    └>│ (f !! 10) │
│      └──┼────────┘
└─────────┘

So, when you ask for f !! n, (!!) will first run around the top loop n times, then return the element, as it did for g. However, instead of escaping the loop, (f !! 10) just re-enters it, and the process repeats itself: looping 10 times around the top, then once around the bottom, and back.

这篇关于时髦的哈斯克尔懒惰列表隐式递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！