To take this a step further, if what you really want is the syntax sugar for do-notation (and I understand that, I love sweet, sweet syntactical sugar), you are probably implementing a Writer monad over some monoid.<br><br>
Here&#39;s two data structures that can encode this type;<br><br>data Replacer1 k a = Replacer1 (k -&gt; Maybe k) a<br>
data Replacer2 k a = Replacer2 [(k,k)] a<br><br>instance Monad Replacer1 where<br>    return x = Replacer1 (\_ -&gt; Nothing) x<br>    Replacer1 ka a &gt;&gt;= f = result where<br>        Replacer1 kb b = f a<br>
        result = Replacer1 (\x -&gt; ka x `mplus` kb x) b<br><br>(!&gt;) :: Eq k =&gt; k -&gt; k -&gt; Replacer1 k ()<br>x !&gt; y = Replacer1 (\k -&gt; if k == x then Just y else Nothing) ()<br><br>replace1 :: Replacer1 k () -&gt; [k] -&gt; [k]    -- look ma, no Eq requirement!<br>
replace1 (Replacer k ()) = map (\x -&gt; fromMaybe x $ k x) -- from Data.Maybe<br><br>table1 :: Replacer1 Char ()<br>table1 = do<br>    &#39;a&#39; !&gt; &#39;b&#39;<br>    &#39;A&#39; !&gt; &#39;B&#39;<br><br>test = replace1 table1 &quot;All I want&quot;<br>
<br>-- Exercise: what changes if we switch ka and kb in the result of (&gt;&gt;=)?  When does it matter?<br>

<br>-- Exercises for you to implement:<br>instance Monad Replacer2 k where<br>replacer :: Eq k =&gt; Replacer2 k -&gt; [k] -&gt; [k]<br>($&gt;) :: k -&gt; k -&gt; Replacer2 k<br><br>-- Exercise: Lets make use of the fact that we&#39;re a monad!<br>
--<br>-- What if the operator !&gt; had a different type?<br>-- (!&gt;) :: Eq k =&gt; k -&gt; k -&gt; Replacer k Integer<br>-- which returns the count of replacements done.<br>--<br>-- table3 = do<br>--     count &lt;- &#39;a&#39; !&gt; &#39;b&#39;<br>
--     when (count &gt; 3) (&#39;A&#39; !&gt; &#39;B&#39;)<br>--     return ()<br>--<br>-- Do any of the data structures I&#39;ve given work?  Why or why not?<br>-- Can you come up with a way to implement this?<br><br>  -- ryan<br>
<br><div class="gmail_quote">On Sat, Jul 28, 2012 at 10:07 AM, Steffen Schuldenzucker <span dir="ltr">&lt;<a href="mailto:sschuldenzucker@uni-bonn.de" target="_blank">sschuldenzucker@uni-bonn.de</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
On 07/28/2012 03:35 PM, Thiago Negri wrote:<br>
&gt; [...]<div class="im"><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
As Monads are used for sequencing, first thing I did was to define the<br>
following data type:<br>
<br>
data TableDefinition a = Match a a (TableDefinition a) | Restart<br>
</blockquote>
<br></div>
So TableDefinition a is like [(a, a)].<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
[...]<br>
</blockquote><div class="im">
&gt;<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
So, to create a replacement table:<br>
<br>
table&#39; :: TableDefinition Char<br>
table&#39; =<br>
         Match &#39;a&#39; &#39;b&#39;<br>
         (Match &#39;A&#39; &#39;B&#39;<br>
          Restart)<br>
<br>
It look like a Monad (for me), as I can sequence any number of<br>
replacement values:<br>
<br>
table&#39;&#39; :: TableDefinition Char<br>
table&#39;&#39; = Match &#39;a&#39; &#39;c&#39;<br>
          (Match &#39;c&#39; &#39;a&#39;<br>
          (Match &#39;b&#39; &#39;e&#39;<br>
          (Match &#39;e&#39; &#39;b&#39;<br>
           Restart)))<br>
</blockquote>
<br></div>
Yes, but monads aren&#39;t just about sequencing. I like to see a monad as a generalized computation (e.g. nondeterministic, involving IO, involving state etc). Therefore, you should ask yourself if TableDefinition can be seen as some kind of abstract &quot;computation&quot;. In particular, can you &quot;execute&quot; a computation and &quot;extract&quot; its result? as in<br>

<br>
  do<br>
    r &lt;- Match &#39;a&#39; &#39;c&#39; Restart<br>
    if r == &#39;y&#39; then Restart else Match 2 3 (Match 3 4 Restart)<br>
<br>
Doesn&#39;t immediately make sense to me. In particular think about the different possible result types of a TableDefinition computation.<br>
<br>
If all you want is sequencing, you might be looking for a Monoid instance instead, corresponding to the Monoid instance of [b], where b=(a,a) here.<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
 [...]<br>
</blockquote><div class="im">
&gt;<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
I&#39;d like to define the same data structure as:<br>
<br>
newTable :: TableDefinition Char<br>
newTable = do<br>
         &#39;a&#39; :&gt;  &#39;b&#39;<br>
         &#39;A&#39; :&gt;  &#39;B&#39;<br>
<br>
But I can&#39;t figure a way to define a Monad instance for that. :(<br>
</blockquote>
<br></div>
The desugaring of the example looks like this:<br>
<br>
  (&#39;a&#39; :&gt; &#39;b&#39;) &gt;&gt; (&#39;A&#39; :&gt; &#39;B&#39;)<br>
<br>
Only (&gt;&gt;) is used, but not (&gt;&gt;=) (i.e. results are always discarded). If this is the only case that makes sense, you&#39;re probably looking for a Monoid instead (see above)<span class="HOEnZb"><font color="#888888"><br>

<br>
-- Steffen</font></span><div class="HOEnZb"><div class="h5"><br>
<br>
______________________________<u></u>_________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/<u></u>mailman/listinfo/haskell-cafe</a><br>
</div></div></blockquote></div><br>