相互递归 - 有人可以帮助解释这段代码是如何工作的吗？

Question

我正在阅读"对Haskell的一个温和的介绍",并且在早期它使用了这个例子,它在GHC中运行良好,在我的大脑中可怕:

initial                 = 0
next resp               = resp
process req             = req+1

reqs                    = client initial resps
resps                   = server reqs

server          (req:reqs)   = process req : server reqs
client initial ~(resp:resps) = initial : client (next resp) resps

和调用代码:
take 10 reqs

我是如何看到它的,被reqs称为,client使用args 0和0 进行调用resps.因此resps现在不需要被调用......反过来reqs再次调用？这一切似乎都是无限的......如果有人能够详细说明它是如何运作的,我会非常感激!

Answer 1

我发现通常手动计算小Haskell程序的行为是值得的.评估规则非常简单.要记住的关键是Haskell 是非严格的(也就是懒惰的):只在需要时才计算表达式.懒惰是看似无限定义可以产生有用结果的原因.在这种情况下,使用take手段我们只需要无限列表的前10个元素reqs:它们都是我们"需要"的.

实际上,"需要"通常由模式匹配驱动.例如,通常会对列表表达式进行评估,直到我们可以在功能应用之间[]和(x:xs)之前进行区分.(注意,在~模式之前的' ',如在定义中client,使其变得懒惰(或无可辩驳):在整个表达式被强制之前,惰性模式不会强制其参数.)

记住这take是:

take 0 _      = []
take n (x:xs) = x : take (n-1) xs

评估take 10 reqs看起来像:

take 10 reqs 
      -- definition of reqs
    = take 10 (client initial resps)
      -- definition of client [Note: the pattern match is lazy]
    = take 10 (initial : (\ resp:resps' -> client (next resp) resps') 
                             resps)
      -- definition of take
    = initial : take 9 ((\ resp:resps' -> client (next resp) resps') 
                            resps)
      -- definition of initial
    = 0 : take 9 ((\ resp:resps' -> client (next resp) resps') 
                      resps)
      -- definition of resps
    = 0 : take 9 ((\ resp:resps' -> client (next resp) resps') 
                      (server reqs))
      -- definition of reqs
    = 0 : take 9 ((\ resp:resps' -> client (next resp) resps') 
                      (server (client initial resps)))
      -- definition of client
    = 0 : take 9 ((\ resp:resps' -> client (next resp) resps') 
                      (server (initial : {- elided... -}))
      -- definition of server
    = 0 : take 9 ((\ resp:resps' -> client (next resp) resps') 
                      (process initial : server {-...-}))
      -- beta reduction 
    = 0 : take 9 (client (next (process initial)) (server {-...-})
      -- definition of client 
    = 0 : take 9 (next (process initial) : {-...-})
      -- definition of take 
    = 0 : next (process initial) : take 8 {-...-}
      -- definition of next 
    = 0 : process initial : take 8 {-...-}
      -- definition of process 
    = 0 : initial+1 : take 8 {-...-}
      -- definition of initial 
    = 0 : 1 : take 8 {-...-}
      -- and so on...

Answer 2

理解此代码需要两项技能:

• 区分'定义',它可以是无限的(如自然数字集合:) naturals = (1 : map '\n->n+1' naturals,或处理请求列表)和'减少',这是将实际数据映射到这些定义的过程
• 看到这个客户端 - 服务器应用程序的结构:它只是一对与彼此交谈的进程:'客户端 - 服务器'是一个坏名字,真的:它应该被称为'wallace-gromit'或'foo-bar',或者谈论哲学家或其他什么,但它是对称的:两党是同龄人.

正如乔恩已经说过的那样,还原是以一种懒惰的方式运作(又称"按需要呼唤"):take 2 naturals不会首先评估完整的自然组合,而只是选择第一组,并将其前置take 1 (map '\n->n+1' naturals),这将减少到[1,( 1 + 1)] = [1,2].

现在客户端服务器应用程序的结构就是这个(我的眼睛):

• server是一种使用该process函数从请求列表中创建响应列表的方法
• client 是一种基于响应创建请求的方法,并将该请求的响应附加到响应列表.

如果仔细观察,你会发现两者都是"从y:ys创建x:xs的方法".因此,我们可以均匀地给他们打电话wallace和gromit.

现在很容易理解是否client仅使用响应列表调用:

someresponses = wallace 0 [1,8,9]    -- would reduce to 0,1,8,9
tworesponses  = take 2 someresponses -- [0,1]

gromit我们可以说,如果答案不是字面上知道的,而是由我们产生的

gromitsfirstgrunt = 0
otherresponses = wallace gromitsfirstgrunt (gromit otherresponses)
twootherresponses = take 2 otherresponses -- reduces to [0, take 1 (wallace (gromit ( (next 0):...) )]
                                          -- reduces to [0, take 1 (wallace (gromit ( 0:... ) )  ) ]
                                          -- reduces to [0, take 1 (wallace (1: gromit (...)  )  ) ]
                                          -- reduces to [0, take 1 (1 : wallace (gromit (...)  ) ) ]
                                          -- reduces to [0, 1 ]

其中一个同行需要"开始"讨论,因此提供的初始值wallace.

还要注意〜模式之前的〜gromit:这告诉Haskell列表参数的内容不需要减少 - 如果它看到它是一个列表,那就足够了.在Haskell上的wikibook中有一个很好的主题(寻找"懒惰模式匹配").