<div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On 11 September 2018 at 21:50, Rodrigo Stevaux <span dir="ltr"><<a href="mailto:roehst@gmail.com" target="_blank">roehst@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">It is easy to read an environment in applicative style, ie:<br>
<br>
type Env = [(String, Int)]<br>
data Term = Add Term Term | Number Int | Var String deriving Show<br>
eval :: Term -> Env -> Int<br>
eval (Add a b) = (+) <$> eval a <*> eval b<br>
eval (Var name) = fetch name<br>
eval (Number i) = pure i<br>
<br>
fetch :: String -> Env -> Int<br>
fetch name = fromJust . lookup name<br>
<br>
But can the eval function change the Env being passed, as to implement<br>
a "let" operation, without using monads? I tried I lot but ultimately<br>
I resorted to (>>=) in the function monad:<br>
<br>
bind f k = \r -> k (f r) r<br></blockquote><div><br></div><div>I think what you mean is something like: can we extend <span style="font-family:monospace,monospace">Term</span> with a let binding expression and implement <span style="font-family:monospace,monospace">eval</span> using applicative interface without <span style="font-family:monospace,monospace">(>>=)</span>?</div><div><br></div><div>I think we can, and it's a bit awkward, but possible, because of the Reader monad.</div><div><br></div><div>A trivial way of introducing let that does not manifest the issues you point out is</div><div><br></div><span style="font-family:monospace,monospace">data Term = Add Term Term | Number Int | Var String | Let String Int Term</span><div><span style="font-family:monospace,monospace"><br></span></div><div><span style="font-family:arial,helvetica,sans-serif">You can then implement the case for <span style="font-family:monospace,monospace">eval</span> with</span></div><div><span style="font-family:monospace,monospace"><br></span></div><div><span style="font-family:monospace,monospace">eval (Let s v t) = eval t . update s v<br></span></div><div><span style="font-family:monospace,monospace"><br></span></div><div><span style="font-family:arial,helvetica,sans-serif">where the function <span style="font-family:monospace,monospace">update</span> simply updates a value in the associative list. A simple implementation is:</span></div><div><span style="font-family:monospace,monospace"><br>update :: Ord a => a -> b -> [(a, b)] -> [(a, b)]<br>update s v = nubBy eqFst . insertBy cmpFst (s, v)<br>  where<br>    eqFst  x y = (==)    (fst x) (fst y)<br>    cmpFst x y = compare (fst x) (fst y)<br></span></div><div><span style="font-family:monospace,monospace"><br></span></div><div><span style="font-family:arial,helvetica,sans-serif">Of course, this does not need the monad interface, but it does not really need the applicative interface to evaluate the term either (except indirectly in <span style="font-family:monospace,monospace">eval t</span>).</span></div><div><span style="font-family:monospace,monospace"><br></span></div><div><span style="font-family:arial,helvetica,sans-serif">Perhaps a more interesting alternative is:</span></div><div><span style="font-family:monospace,monospace"><br></span></div><div><span style="font-family:monospace,monospace">data Term = ... | LetT String Term Term</span></div><div><span style="font-family:monospace,monospace"><br></span></div><div><span style="font-family:arial,helvetica,sans-serif">where the other cases in <span style="font-family:monospace,monospace">Term</span> remain the same. Now you need to <span style="font-family:monospace,monospace">eval</span> the first term to change the environment, which is, I guess, what you wanted?</span></div><div><span style="font-family:monospace,monospace"><br></span></div><div><span style="font-family:arial,helvetica,sans-serif">You can do this combining composition with applicative:</span></div><div><span style="font-family:monospace,monospace"><br></span></div><div><span style="font-family:monospace,monospace">eval (LetT s t1 t2) = eval t2 . (update' <*> pure s <*> eval t1)</span></div><div><span style="font-family:monospace,monospace">  where</span></div><div><span style="font-family:monospace,monospace">    update' :: Env -> String -> Int -> Env<br>    update' e s v = update s v e<br><br></span></div><div><span style="font-family:arial,helvetica,sans-serif">And a test (which is equivalent to<span style="font-family:monospace,monospace"> let b = a + 8 in b + 1</span>):</span></div><div><span style="font-family:monospace,monospace"><br></span></div><div><span style="font-family:monospace,monospace">*Main> eval (LetT "b" (Add (Number 8) (Var "a")) (Add (Number 1) (Var "b"))) [("a", 7)]</span></div><div><span style="font-family:monospace,monospace">16</span></div><div><br><span style="font-family:monospace,monospace"></span></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
I do not think so, because in applicative style each operand can have<br>
an effect (reading the environment) but can not affect other operands<br>
(including the next ones), i.e., there is no notion of sequencing in<br>
applicatives<br>
Is this reasoning right?<br></blockquote><div><br></div><div>As Tom pointed out, not 100%, not generally, I think. This seems to be specific to the reader monad.</div><div><br></div><div>All the best,</div><div><br></div><div>Ivan</div></div><br></div></div></div></div></div></div></div></div></div></div></div>