<div dir="ltr">Hi Michael:<div><br></div><div>This is an interesting question, and I think you might indeed be able to "hack" into the recursive calls if you are willing to be explicit with your fixed-point calculation. Note that you'll have to *do* the work of keeping track of "visited" nodes, so to speak; there's no free lunch. But the construction of the table in a monadic form can be incorporated using what's known as "monadic memoization mixins." See this paper by Brown and Cook for details:</div><div><br></div><div>    <a href="https://www.cs.utexas.edu/users/wcook/Drafts/2009/sblp09-memo-mixins.pdf">https://www.cs.utexas.edu/users/wcook/Drafts/2009/sblp09-memo-mixins.pdf</a></div><div><br></div><div>The idea is to detour through a memo-routine before each recursive call to do the bookkeeping necessary. The underlying monad keeps track of the data you are memoizing.</div><div><br></div><div>However, before diving into memo-mixins, you might want to just implement the algorithm keeping track of a "visited" table in the monadic style, just to appreciate what the mixins will buy you. For fun, I coded your minimize example in idiomatic Haskell here:</div><div><br></div><div>     <a href="https://gist.github.com/LeventErkok/615afe9a0e24249daedab3c623241275">https://gist.github.com/LeventErkok/615afe9a0e24249daedab3c623241275</a></div><div><br></div><div>Enjoy,</div><div><br></div><div>-Levent.</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Dec 10, 2016 at 8:50 AM, Michael George <span dir="ltr"><<a href="mailto:mdgeorge@cs.cornell.edu" target="_blank">mdgeorge@cs.cornell.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">I've come across a slight variant of memoization and I'm curious if either there is a better way to think about (I have yet to reach Haskell Enlightement), or if it's been thought about before.<br>
<br>
I'm writing a program that does DFA minimization, as described here: <a href="https://www.tutorialspoint.com/automata_theory/dfa_minimization.htm" rel="noreferrer" target="_blank">https://www.tutorialspoint.com<wbr>/automata_theory/dfa_minimizat<wbr>ion.htm</a>.<br>
<br>
For me, the simplest way to understand the algorithm is we form an equivalence relation, where two states are different if either one is final and the other isn't, or if there are transitions from them to states that are different.<br>
<br>
different a b = isFinal a && not (isFinal b) || isFinal b && not (isFinal a) || exists chars (\c -> different (step a c) (step b c))<br>
<br>
This definition diverges; it never decides that two states are the same.  The standard algorithm builds a table, starting with the assumption that all states are the same, and iteratively applying this definition until it converges.<br>
<br>
I'm thinking of that algorithm as a memoized version of the implementation of different above.  But it's not quite:<br>
<br>
different = memoFix2 different' where<br>
   different' different'' a b = isFinal a && not (isFinal b) || isFinal b && not (isFinal a) || exists chars (\c -> different'' (step a c) (step b c))<br>
<br>
for the same reason; it diverges.  But with memoization I can detect the diversion by putting a marker in the memo table.  If the computation makes a recursive call on an input that is started but not computed, then (in this case) I want to return false.<br>
<br>
In general, I think what I want is<br>
<br>
memoFixWithDefault :: (a -> b) -> ((a->b) -> (a -> b)) -> (a -> b)<br>
<br>
Where (memoFixWithDefault default f) is like (memoFix f) except that if (memoFix f a) would loop, then (memoFixWithDefault default f a) = default a.<br>
<br>
<br>
I suspect there's a nice denotational way of describing this, but my denotational semantics is rusty (maybe it's the least fixed point of f that is greater than g or something, but that's not it).  I suspect that there needs to be a nice relationship between f and g for memoFixWithDefault f g to be sensible.  I also suspect that there's a cute 3-line implementation like all the other implementations of memoize out there, but I don't see it.  I also suspect that depth-first search has a cute implementation using this combinator.<br>
<br>
So I was wondering if other people had thoughts or references before I went off and thought about it.<br>
<br>
Thanks!<br>
<br>
-M<br>
______________________________<wbr>_________________<br>
Haskell-Cafe mailing list<br>
To (un)subscribe, modify options or view archives go to:<br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bi<wbr>n/mailman/listinfo/haskell-caf<wbr>e</a><br>
Only members subscribed via the mailman list are allowed to post.</blockquote></div><br></div>