StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POWadler, "Monads for Functional Programming," Section 2.8
text
Body
copied!<p><strong>Edit II:</strong> Ah, okay: I wasn't understanding how <em>a</em> and <em>b</em> were being bound in the definition of <em>eval</em>! Now I do. If anyone's interested, this is a diagram tracking <em>a</em> and <em>b</em>. I'm a pretty big fan of diagrams. Drawing arrows really improved my Haskell, I swear.</p> <p><a href="http://www.youshare.com/Guest/f00c68df1dd44c7b.pdf.html" rel="nofollow noreferrer">A Diagram of an eval call (PDF)</a></p> <p>Sometimes I feel really dense.</p> <hr> <p>In section 2.8 of Wadler's "<a href="http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/baastad.pdf" rel="nofollow noreferrer">Monads for Functional Programming</a>," he introduces state into a simple evaluation function. The original (non-monadic) function tracks state using a series of let expressions, and is easy to follow:</p> <pre><code>data Term = Con Int | Div Term Term deriving (Eq, Show) type M a = State -> (a, State) type State = Int eval' :: Term -> M Int eval' (Con a) x = (a, x) eval' (Div t u) x = let (a, y) = eval' t x in let (b, z) = eval' u y in (a `div` b, z + 1) </code></pre> <p>The definitions of <em>unit</em> and <em>bind</em> for the monadic evaluator are similarly straightforward:</p> <pre><code>unit :: a -> M a unit a = \x -> (a, x) (>>=) :: M a -> (a -> M b) -> M b m >>= k = \x -> let (a, y) = m x in let (b, z) = k a y in (b, z) </code></pre> <p>Here, (>>=) accepts a monadic value <em>m</em> :: <em>M a</em>, a function <em>k</em> :: <em>a</em> -> <em>M b</em>, and outputs a monadic value <em>M b</em>. The value of <em>m</em> is dependent on the value substituted for <em>x</em> in the lambda expression.</p> <p>Wadler then introduces the function <em>tick</em>:</p> <pre><code>tick :: M () tick = \x -> ((), x + 1) </code></pre> <p>Again, straightforward. What <em>isn't</em> straightforward, however, is how to chain these functions together to produce an evaluation function that returns the number of division operators performed. Specifically, I don't understand:</p> <p><strong>(1)</strong> How <em>tick</em> is implemented. For instance, the following is a valid function call:</p> <pre><code>(tick >>= \() -> unit (div 4 2)) 0 ~> (2, 1) </code></pre> <p>However, I can't evaluate it correctly by hand (indicating that I misunderstand something). In particular: (a) The result of evaluating <em>tick</em> at 0 is ((), 0), so How does the lambda expression accept ()? (b) If <em>a</em> is the first element of the pair returned by calling <em>tick</em> at 0, how does <em>unit</em> get evaluated?</p> <p><strong>(2)</strong> How to combine <em>tick</em> and <em>unit</em> to track the number of division operators performed. While the non-monadic evaluator is not problematic, the use of <em>bind</em> is confusing me here.</p> <p><strong>Edit:</strong> Thanks, everybody. I think my misunderstanding was the role of the lambda expression, '() -> unit (div 4 2)'. If I understanding it correctly,</p> <pre><code>(tick >>= (\() -> unit (div m n)) x </code></pre> <p>expands to</p> <pre><code>(\x -> let (a, y) = tick x in let (b, z) = (\() -> unit (div m n) a y) in (b, z)) x </code></pre> <p>When 'a' is applied to '() -> unit (div m n) a y', no 'practical result' is yielded. The same effect could be achieved by binding <em>any</em> variable with a lambda operator, and substituting a value for it. The versatility of <em>bind</em>, in this case, is that <em>any</em> value <em>M a</em> can be passed to it. As noted, a value <em>M a</em> represents a computation, for instance, 'eval.' Hence:</p> <pre><code>eval (Con a) = unit a eval (Div t u) = eval t >>= (\a -> eval u >>= (\b -> tick >>= (\c -> unit (a `div` b)))) </code></pre> <p>If I understand correctly, 'eval t' is substituted for <em>m</em> and the remainder of the expression, the function</p> <pre><code>'(\a -> eval u >>= (\b -> tick >>= (\c -> unit (a `div` b))))' </code></pre> <p>is substituted for <em>k</em>. The result of evaluating 'eval t' is bound to (a, y), and the result of evaluating <em>k</em> is bound to (b, z). I have a ways to go, but this clears it up somewhat. Thanks.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload