Most of the issue here is related to subtle evaluation and pattern-matching features in Haskell that have no analog in Wolfram Language (WL). The ~
operator has no real equivalent within WL. Nevertheless, the issues can be approximated in WL and such approximation will indeed make judicious use of Hold
attributes to induce lazy evaluation semantics.
The crux of the matter is that the linked set of function definitions are mutually recursive. The order in which those recursions are resolved are critically important to avoid runaway calculation. A pattern like (resp:resps)
as it appears in client
requires the matched argument to be evaluated down to the depth of the first list cell ("cons") prior to evaluating the body of client
. But the cons cell in question is produced within the body of client
itself. So we get into an infinite regress trying to produce the result.
By changing the pattern to ~resp:resps
, the pattern-matching process becomes non-strict and notionally moves the problematic argument cons evaluation over into the body of client
after the first result cons cell has been generated.
Details
The question concerns the use of the lazy pattern ~(resp:resps)
in the definition of client
in the following Haskell code (which has been simplified from the tutorial linked in the question):
-- Haskell code
reqs = client 0 (server reqs)
client init ~(resp:resps) = init : client resp resps
server (req:reqs) = req+1 : server reqs
take 10 reqs
-- returns: [0,1,2,3,4,5,6,7,8,9]
This main thing to note is that the function reqs
is not only self-recursive, but it also links the functions client
and server
together into a mutually recursive dependency. Furthermore, the return values of all of these functions are infinite in length. This setup is useful when used in a non-strict ("lazy evaluating") language like Haskell. If we naively translate this into WL, we get:
(* does not work! *)
ClearAll[reqs, client, server]
reqs[] := client[0, server[reqs[]]]
client[init_, {resp_, resps___}] := Prepend[init, client[resp, resps]]
server[{req_, reqs___}] := Prepend[req+1, server[{reqs}]]
Take[10, reqs[]]
(* $RecursionLimit::reclim2: Recursion depth of 1024 exceeded during evaluation of server[reqs[]]. *)
WL has no analog to the systemic lazy evaluation present in Haskell. So any emulation of it is going to be messy. But let us try anyway. There is a definition of some lazy operators at the bottom of this post, notably lazy
. We can use these operators to define infinite self-recursive functions and control the depth of strict evaluation. For example:
primes[n_:1] := lazy[Prime[n], primes[n+1]]
primes[] // take[10] // Normal
(* {2, 3, 5, 7, 11, 13, 17, 19, 23, 29} *)
We will now use them to adjust the naive example to have lazy evaluation behaviour:
ClearAll[reqs, client, server]
SetAttributes[{client, server}, HoldAll]
reqs[] := client[0, server[reqs[]]]
client[init_, resps_] := lazy[init, lazy[first[resps], rest[resps]]]
server[reqs_] := lazy[first[reqs]+1, server[rest[reqs]]]
While these definitions do not match Haskell's thunk-based evaluation process exactly, it is close enough for our purposes. It gives the same answer:
reqs[] // take[10] // Normal
(* {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} *)
We are now into a position to discuss the original questions.
Why is there are problem matching "too early"?
In Haskell, most expressions are evaluated non-strictly. But in the case the pattern-matching, some patterns are partially evaluated in strict fashion before evaluating the function body. (resp:resps)
is one such pattern. In order to match this pattern, the expression being matched must be evaluated enough to know that it is a non-empty list. That entails evaluating to reach the first cons cell but the elements themselves can remain unevaluated.
In order to obtain the first element, we must evaluate the client
expression enough to obtain that element. That means we must evaluate the expression init : client...
, where :
is the constructor functions of the first list cell (cons). But... we have just said that the pattern (resp:resps)
must be evaluated before we get to the :
function. That drives a call to server
which then calls back to reqs
which is back to client
... and we are stuck in an infinite evaluation cycle.
The Haskell operator ~
converts a strict pattern into a non-strict one. Operationally, it internally changes the definition of client
from this:
-- Haskell code
client init (resp:resps) = init : client resp resps
to this:
-- Haskell code
client init resps = init : client (head resps) (tail resps)
Note how the destructuring of the input list resps
is now done in the body of the definition instead of proactively in the argument pattern-matching stage.
Also note we had quietly performed this code transformation when we wrote our WL emulation of the Haskell example. This is because WL lacks any similar sort of rewriting operator so we had to do it manually. But we can still demonstrate the problem in our code if we change the working definition of client
from:
client[init_, resps_] := lazy[init, lazy[first[resps], rest[resps]]]
to the broken version:
client[init_, resps_] /; first[resps] != Null :=
lazy[init, lazy[first[resps], rest[resps]]]
By introducing a pattern condition on the argument resps
, we have forced its evaluation prior to the evaluation of the body. It is now "too soon":
reqs[] // take[10] // Normal
(* $RecursionLimit::reclim2: Recursion depth of 1024 exceeded during evaluation of first[server[reqs[]]]!=Null. *)
Again, the details of both the pattern and body evaluations in the WL code differ in considerable detail from the Haskell analogs, but they are close enough to demonstrate the principles under which the issue occurs.
Is Haskell's ~
equivalent to Hold
?
Sort of. Not really. They both share the attribute that they indicate that an expression is not to be evaluated right away. But Haskell's ~
operator also performs a logical code transformation on the containing definition to enable certain classes of partial lazy evaluation unique to Haskell. In WL, evaluation is generally all or nothing. If we wish to emulate partial resolution of deferred evaluations, we will have to write it ourselves. Consider, for example, the discussion in How do I evaluate only one step of an expression?.
Appendix - Lazy Operator Definitions
The following lazy-evaluation functions are extremely limited in scope, not to mention horribly inefficient. Nevertheless, they will suffice for the purposes of this response.
ClearAll[lazy, first, rest, take]
SetAttributes[lazy, HoldAll]
lazy[x_] := lazy[Nothing, x]
first[lazy[f_, _]] := f
rest[lazy[_, r_]] := r
take[n_][l_] :=
lazy[If[n <= 0, Nothing, first[l]], If[n <= 0, lazy[], take[n-1][rest[l]]]]
Normal[l_lazy] ^:=
Module[{ll = l, f}, NestWhileList[(f=first[ll];ll=rest[ll];f)&, Null, # =!= Nothing&]][[2;;-1]]
Bonus Quiz
The ability to predict the output of the following (slightly evil) Haskell example demonstrates that the first steps have been taken off the path of procedural thinking and into Haskell's non-strict world of pattern-matching and equational reasoning:
-- Haskell code
notimperative x =
let (a,b) = (x+1,c+1)
(c,d) = (d+1,a+1)
in (a,b,c,d)
notimperative 0
Spoiler
no, i'm not giving it away that easily :)
Uncompress["1:eJxTTMoPCuZkYGDQMNQx0THWMdIEACG4A0A=", HoldAllComplete]