哈斯克尔斐波那契解释 [英] Haskell Fibonacci Explanation

问题描述

我知道这个问题之前已经被问过了， ，但没有一个答案解决了我用可视化结果的问题。

代码是使用 zipWith 的规范代码。 code $
$ b $ $ p $ fibs = 0：1：zipWith（+）fibs（tail fibs）


$ b
$ b

zipWith 直接将两个列表拉到一起

尾部抓取除第一个元素列表

Haskell将'to-be'计算数据引用为 thunks 。

从我的理解中，它首先添加了 [0,1，< thunk>] 和 [ 1，< code>使用 zipWith（+）给出 [1，< thunk>] 。所以，现在你有

pre $ fibs = 0：1：1：zipWith（+）fibs（尾纤）


很多Google Googled的参考文件已经将上面的行可视化为$ b $ （+）[1,1，< thunk>]（[1，< thunk>]）。


我的问题是这样的：



为什么上面一行中的 fibs 组件仅与 [1,1，< ; thunk>] 而不是 [0,1,1，< thunk>] ？

不应该包含整个列表加上< thunk> ？

解决方案

这个中间步骤是错误的，因为 zipWith 一对物品：

  fibs = 0：1：1：zipWith（+）fibs（尾纤）
  

回想一下zipWith在一般情况下的作用：

  zipWith f（x：xs）（y：ys）=（fxy）：zipWith f xs ys 
  

如果直接应用该定义，您可以获得以下扩展：

  fibs = 0：1：zipWith +）fibs（tail fibs）＃fibs = [0,1，...] 
 = 0：1：zipWith（+）[0,1，...]（tail [0,1，.. 。]）＃tail fibs = [1，...] 
 = 0：1：zipWith（+）[0,1，...] [1，...]＃应用zipWith 
 = 0：1：（0 + 1：zipWith（+）[1,0 + 1，...] [0 + 1，...]）
 = 0：1：1：zipWith（+ [1,1，...] [1，...]＃应用zipWith 
 = 0：1：1：（1 + 1：zipWith（+）[1,1 + 1，...] [1 + 1，...]）
 = 0：1：1：2：zipW ith（+）[1,2，...] [2，...]＃应用zipWith 
 = 0：1：1：2：（1 + 2：zipWith（+）[2,1+ 2，...] [1 + 2，...]）
 = 0：1：1：2：3：zipWith（+）[2,3 ...] [3，...] ＃apply zipWith 
：
  

I am quite new to Haskell and I'm trying to wrap my head around how the lazy expression of Fibonacci sequences work.

I know this has been asked before, but none of the answers have addressed an issue I'm having with visualising the result.

The code is the canonical one using zipWith

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

I understand the following:

1. zipWith literally zips two lists together
2. tail grabs all but the first element of a list
3. Haskell references 'to-be' computed data as thunks.

From my understanding, it first adds [0,1,<thunk>] and [1,<thunk>] using zipWith (+) to give [1,<thunk>]. So now you have

fibs = 0 : 1 : 1 : zipWith (+) fibs (tail fibs)

A lot of references I've Googled have then proceeded to "visualise" the line above as

fibs = 0 : 1 : 1 : zipWith (+) [1,1,<thunk>] ([1,<thunk>]).

My question is this:

Why is the fibs component in the line above only corresponding to [1,1,<thunk>] instead of [0,1,1,<thunk>]?

Shouldn't fibs contain the entire list plus <thunk>?

解决方案

This intermediate step is wrong because zipWith has already processed the first pair of items:

fibs = 0 : 1 : 1 : zipWith (+) fibs (tail fibs)

Recall what zipWith does in the general case:

zipWith f (x:xs) (y:ys) = (f x y) : zipWith f xs ys

If you apply the definition directly you get this expansion:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)                # fibs=[0,1,...]
     = 0 : 1 : zipWith (+) [0,1,...] (tail [0,1,...])      # tail fibs=[1,...]
     = 0 : 1 : zipWith (+) [0,1,...] [1,...]               # apply zipWith
     = 0 : 1 : (0+1 : zipWith (+) [1,0+1,...] [0+1,...])   
     = 0 : 1 : 1 : zipWith (+) [1,1,...] [1,...]           # apply zipWith
     = 0 : 1 : 1 : (1+1 : zipWith (+) [1,1+1,...] [1+1,...])
     = 0 : 1 : 1 : 2 : zipWith (+) [1,2,...] [2,...]       # apply zipWith
     = 0 : 1 : 1 : 2 : (1+2 : zipWith (+) [2,1+2,...] [1+2,...])
     = 0 : 1 : 1 : 2 : 3 : zipWith (+) [2,3...] [3,...]    # apply zipWith
     :

这篇关于哈斯克尔斐波那契解释的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！