[Haskell-cafe] About the lazy pattern

[Ryan Ingram]

Hi nemo.  I had a lot of trouble with that section of the tutorial as
well, and I believe that once you get it, a lot of Haskell becomes a
lot simpler.

The way I eventually figured it out is using this idealized execution
model for Haskell: you just work by rewriting the left side of a
function to its right side.  The only question is figuring out *which*
function to rewrite!

Here's a simpler example:

> f 0 = 0
> f x = x+1

> g (x:xs) = error "urk"
> g [] = 2
> const a b = a

> ex1 = const (f 1) (g [2,3])
> ex2 = f (const (g []) (g [1,2]))

Lets say you wanted to know the value of ex1; you just use rewriting

ex1
-- rewrite using ex1
= const (f 1) (g [2,3])
-- rewrite using const
= f 1
-- rewrite using f (second pattern)
= 1+1
-- rewrite using +
= 2

But lets say we picked a different order to rewrite...

ex1
-- rewrite using ex1
= const (f 1) (g [2,3])
-- rewrite using g
= const (f 1) (error "urk")
-- rewrite using error
computation stops

Of course this is bad, and it was obviously wrong to evaluate g first
(because const is lazy).  So one heuristic we always use is "rewrite
the leftmost application first" which avoids this problem.  But lets
try that rule on ex2!

ex2
-- rewrite using ex2
= f (const (g []) (g [1,2]))
-- rewrite using f
= ?

Unfortunately, now we don't know which pattern to match!  So we have
to pick a different thing to rewrite.  The next rule is that, if the
thing you want to rewrite has a pattern match, look at the argument
for the patterns being matched and rewrite them instead, using the
same "leftmost first" rule:

f (const (g []) (g [1,2]))
-- trying to pattern match f's first argument
-- rewrite using const
= f (g [])
-- still pattern matching
-- rewrite using g
= f 2
-- now we can match
-- rewrite using f (second pattern)
= 2+1
-- rewrite using +
= 3

So, back to the original question (I'm rewriting the arguments to
"client" and "server" for clarity)

> reqs = client init resps
> resps = server reqs
> client v (rsp:rsps) = v : client (next rsp) rsps
> server (rq:rqs) = process rq : server rqs

Lets say we are trying to figure out the value of "resps", to print
all the responses to the screen:

resps
-- rewrite using resps
= server reqs
-- pattern match in server
-- rewrite reqs
= server (client init resps)
-- pattern match in server
-- pattern match also in client
-- rewrite using resps
= server (client init (server reqs))
-- pattern match in server, client, then server
-- rewrite using reqs
= server (client init (server (client init resps)))

You see that we are in a loop now; we are stuck trying to pattern
match and we will never make any progress!

The "lazy pattern" says "trust me, this pattern will match, you can
call me on it later if it doesn't!"

> reqs = client init resps
> resps = server reqs
> client v (rsp:rsps) = v : client (next rsp) rsps
> server (rq:rqs) = process rq : server rqs

resps
-- rewrite resps
= server reqs
-- server wants to pattern match, rewrite reqs
= server (client init resps)
-- Now, the lazy pattern match says "this will match, wait until later"
-- rewrite using client!
= let (rsp:rsps) = resps
   in server (init : client (next rq) rqs)
-- rewrite using server
= let (rsp:rsps) = resps
   in process init : server (client (next rq) rqs)

We now have a list node, so we can print the first element and
continue (which requires us to know the code for "process" and "next",
but you get the idea, I hope!)

Now of course, you can lie to the pattern matcher:

> next x = x + 1
> init = 5

client init []
-- rewrite using client
= let (rsp0:rsps0) = []
   in init : client (next rsp0) rsps0
-- rewrite using init
= let (rsp0:rsps0) = []
   in 5 : client (next rsp0) rsps0

-- print 5 and continue to evaluate...
   let (rsp0:rsps0) = []
   in client (next rsp0) rsps0
-- rewrite using client
= let
    (rsp0:rsps0) = []
    (rsp1:rsps1) = rsps0
   in (next rsp0) : client (next rsp1) rsps1
-- rewrite using next
= let
    (rsp0:rsps0) = []
    (rsp1:rsps1) = rsps0
   in rsp0+1 : client (next rsp1) rsps1
-- + wants to "pattern match" on its first argument
-- rewrite using rsp0
computation stops, pattern match failure, (rsp0:rsps0) does not match []

For this reason, many people (myself included) consider it bad style
to use lazy/irrefutable pattern matches on data types with more than
one constructure.  But they are very handy on types with a single
constructor, like pairs:

> weird ~(x,y) = (1,x)
> crazy = weird crazy

crazy
-- rewrite crazy
= weird crazy
-- rewrite weird
= let (x0,y0) = crazy
   in (1, x0)
-- We really want to know what x0 is now.
-- But it is the result of a pattern match inside a let; so we need to evaluate
-- the right hand side of the binding to see if the patterns match.
-- So, rewrite crazy to attempt to pattern match...
= let (x0, y0) = weird crazy
   in (1, x0)
-- Then, rewrite weird
= let
    (x1, y1) = crazy
    (x0, y0) = (1, x1)
   in (1, x0)
-- rewrite x0
= let
    (x1, y1) = crazy
    (x0, y0) = (1, x1)
   in (1, 1)
-- garbage collect
= (1,1)

I hope this helps!

  -- ryan


2009/5/27 张旭 <stircrazynemo at hotmail.com>:
> Hi, I am really new to haskell. I am reading "A gentle instruction to
> haskell" now. And I just cannot understand the chapter below. Is there
> anybody who can gives me some hints about why the pattern matching for
> "client" is so early? How does the pattern matching works here?
>
> Thank you so much for answering my questions!
>
> Sincerely,
> nemo
>
> 4.4  Lazy Patterns
>
> There is one other kind of pattern allowed in Haskell. It is called a lazy
> pattern, and has the form ~pat. Lazy patterns are irrefutable: matching a
> value v against ~pat always succeeds, regardless of pat. Operationally
> speaking, if an identifier in pat is later "used" on the right-hand-side, it
> will be bound to that portion of the value that would result if v were to
> successfully match pat, and _|_ otherwise.
>
> Lazy patterns are useful in contexts where infinite data structures are
> being defined recursively. For example, infinite lists are an excellent
> vehicle for writing simulation programs, and in this context the infinite
> lists are often called streams. Consider the simple case of simulating the
> interactions between a server process server and a client process client,
> where client sends a sequence of requests to server, and server replies to
> each request with some kind of response. This situation is shown pictorially
> in Figure 2. (Note that client also takes an initial message as argument.)
>
> Figure 2
>
> Using streams to simulate the message sequences, the Haskell code
> corresponding to this diagram is:
>
> reqs                     = client init resps
> resps                    = server reqs
>
> These recursive equations are a direct lexical transliteration of the
> diagram.
>
> Let us further assume that the structure of the server and client look
> something like this:
>
> client init (resp:resps) = init : client (next resp) resps
> server      (req:reqs)   = process req : server reqs
>
> where we assume that next is a function that, given a response from the
> server, determines the next request, and process is a function that
> processes a request from the client, returning an appropriate response.
>
> Unfortunately, this program has a serious problem: it will not produce any
> output! The problem is that client, as used in the recursive setting of reqs
> and resps, attempts a match on the response list before it has submitted its
> first request! In other words, the pattern matching is being done "too
> early." One way to fix this is to redefine client as follows:
>
> client init resps         = init : client (next (head resps)) (tail resps)
>
> Although workable, this solution does not read as well as that given
> earlier. A better solution is to use a lazy pattern:
>
> client init ~(resp:resps) = init : client (next resp) resps
>
> Because lazy pat terns are irrefutable, the match will immediately succeed,
> allowing the initial request to be "submitted", in turn allowing the first
> response to be generated; the engine is now "primed", and the recursion
> takes care of the rest.
>
>
> ________________________________
> 使用新一代 Windows Live Messenger 轻松交流和共享！ 立刻下载！
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>