Mutual recursion -- can someone help explain how this code works?

Question

I'm reading through "A Gentle Introduction to Haskell," and early on it uses this example, which works fine in GHC and horribly in my brain:

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

And the calling code:
take 10 reqs

How I'm seeing it, is reqs is called, yielding a call to client with args 0 and resps. Thus wouldn't resps now need to be called... which in turn calls reqs again? It all seems so infinite... if someone could detail how it's actually working, I'd be most appreciative!

Answer 1

I find that it's usually worthwhile to work out the behavior of small Haskell programs by hand. The evaluation rules are quite simple. The key thing to remember is that Haskell is non-strict (aka lazy): expressions are evaluated only when needed. Laziness is the reason seemingly infinite definitions can yield useful results. In this case, using take means we will only need the first 10 elements of the infinite list reqs: they are all we "need".

In practical terms, "need" is generally driven by pattern matches. E.g., a list expression will generally be evaluated up to the point where we can distinguish between [] and (x:xs) before function application. (Note that a '~' preceding a pattern , as in the definition of client, makes it lazy (or irrefutable): a lazy pattern won't force its argument until the whole expression is forced.)

Remembering that take is:

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

The evaluation of take 10 reqs looks like:

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

Understanding this code requires two skills:

• distinguishing between 'definition', which may be infinite (like the set of natural numbers: naturals = (1 : map '\n->n+1' naturals), or the list of processed requests) and 'reduction', which is the process of mapping actual data to these definitions
• seeing the structure of this client-server application: it's just a pair of processes talking to eachother: 'client-server' is a bad name, really: it should have been called 'wallace-gromit' or 'foo-bar', or talking philosophers or whatever, but it's symmetrical: the two parties are peers.

As Jon already stated, reduction works in a lazy way (aka 'call by need'): take 2 naturals would not first evaluate the complete set of naturals, but just take the first one, and prepend that to take 1 (map '\n->n+1' naturals), which would reduce to [1,(1+1) ] = [1,2].

Now the structure of the client server app is this (to my eye):

• server is a way to create a list of responses out of a list of requests by using the process function
• client is a way to create a request based on a response, and append the response of that request to the list of responses.

If you look closely, you see that both are 'a way to create x:xs out of y:ys'. So we could evenly call them wallace and gromit.

Now it would be easy to understand if client would be called with just a list of responses:

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

If the responses are not literally known, but produced by gromit, we can say

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 ]

One of both peers needs to 'start' the discussion, hence the initial value provided to wallace.

Also note the ~ before the pattern of gromit: this tells Haskell that the contents of the list argument don't need to be reduced - if it sees it's a list, that's enough. There's a nice topic on that in a wikibook on Haskell (look for "Lazy Pattern Matching).