5

我正在阅读“A Gentle Introduction to 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被调用,产生一个调用clientargs 0 和resps. 因此resps现在不需要被调用......这又会reqs再次调用?这一切似乎都是无限的......如果有人能详细说明它是如何工作的,我将不胜感激!

4

4 回答 4

12

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

实际上,“需要”通常由模式匹配驱动。例如,列表表达式通常会被评估到我们可以区分函数应用之前[]和之前的点。(x:xs)(请注意,在~pattern 之前的 ' ' ,就像在 的定义中一样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...
于 2008-12-29T15:12:29.723 回答
11

理解这段代码需要两个技巧:

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

正如Jon已经说过的那样,减少以一种懒惰的方式工作(又名“按需调用”):take 2 naturals不会首先评估完整的自然集,而只是取第一个,并将其添加到take 1 (map '\n->n+1' naturals),这将减少为 [1,( 1+1) ] = [1,2]。

现在客户端服务器应用程序的结构是这样的(在我看来):

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

如果仔细观察,您会发现两者都是“从 y:ys 创建 x:xs 的一种方式”。所以我们可以均匀地称它们为wallacegromit

现在很容易理解是否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 不需要减少 list 参数的内容 - 如果它看到它是一个列表,那就足够了。在有关 Haskell的 wikibook 中有一个很好的主题(查找“惰性模式匹配”)。

于 2008-12-29T10:20:07.363 回答
4

自从我使用 Haskell 已经有一段时间了,但我很确定它是惰性评估的,这意味着它只计算它实际需要的东西。所以虽然 reqs 是无限递归的,因为take 10 reqs只需要返回列表的前 10 个元素,这就是实际计算的所有内容。

于 2008-12-29T08:57:07.780 回答
0

它看起来像很好的混淆。如果您仔细阅读,您会发现它很简单:

下一个?这是身份

服务器?它只是 map 过程,即 map '\n->n+1'

客户?如何写 0 的方式很晦涩:服务器客户端,例如 0 : map '\n->n+1' [0: map '\n->n+1' [0:...]]

于 2009-01-01T21:19:12.993 回答