X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?a=blobdiff_plain;ds=inline;f=exercises%2F_assignment8.mdwn;fp=exercises%2F_assignment8.mdwn;h=1c7fdfaf02252e0d721d32acd9de6a507667096e;hb=183aeafe5566607c8768b7c978907a15b6c29c4c;hp=0000000000000000000000000000000000000000;hpb=910830a353b8074d890aa989488e31f1d0888e6f;p=lambda.git diff --git a/exercises/_assignment8.mdwn b/exercises/_assignment8.mdwn new file mode 100644 index 00000000..1c7fdfaf --- /dev/null +++ b/exercises/_assignment8.mdwn @@ -0,0 +1,84 @@ + +Binding more than one variable at a time +---------------------------------------- + +It requires some cleverness to use the link monad to bind more than +one variable at a time. Whereas in the standard Reader monad a single +environment can record any number of variable assignments, because +Jacobson's monad only tracks a single dependency, binding more than +one pronoun requires layering the monad. (Jacobson provides some +special combinators, but we can make do with the ingredients already +defined.) + +Let's take the following sentence as our target, with the obvious +binding relationships: + +
+ John believes Mary said he thinks she's cute. + | | | | + | |---------|---------| + | | + |-----------------------| ++ +It will be convenient to +have a counterpart to the lift operation that combines a monadic +functor with a non-monadic argument: + +
+ let g f v = ap (unit f) v;; + let g2 u a = ap u (unit a);; ++ +As a first step, we'll bind "she" by "Mary": + +
+believes (z said (g2 (g thinks (g cute she)) she) mary) john + +~~> believes (said (thinks (cute mary) he) mary) john ++ +As usual, there is a trail of *g*'s leading from the pronoun up to the +*z*. Next, we build a trail from the other pronoun ("he") to its +binder ("John"). + +
+believes + said + thinks (cute she) he + Mary + John + +believes + z said + (g2 ((g thinks) (g cute she))) he + Mary + John + +z believes + (g2 (g (z said) + (g (g2 ((g thinks) (g cute she))) + he)) + Mary) + John ++ +In the first interation, we build a chain of *g*'s and *g2*'s from the +pronoun to be bound ("she") out to the level of the first argument of +*said*. + +In the second iteration, we treat the entire structure as ordinary +functions and arguments, without "seeing" the monadic region. Once +again, we build a chain of *g*'s and *g2*'s from the currently +targeted pronoun ("he") out to the level of the first argument of +*believes*. (The new *g*'s and *g2*'s are the three leftmost). + +
+z believes (g2 (g (z said) (g (g2 ((g thinks) (g cute she))) he)) mary) john + +~~> believes (said (thinks (cute mary) john) mary) john ++ +Obviously, we can repeat this strategy for any configuration of pronouns +and binders. +