<div dir="ltr"><span style="font-size:12.8px">"But with memoization I can detect the diversion by putting a marker in the memo table."</span><br><div><span style="font-size:12.8px"><br></span></div><div><span style="font-size:12.8px">I'm not sure I entirely understand your problem, but it seems when you make a recursive call to a node you've already visited, you want to return false. Like you said, you have to "mark" this in some way. One way do to this is to just add a parameter to the recursive call which notes the nodes you've just visited. There's a number of ways to do this, in the ST Monad an mutable bit array would work nicely but if you're not in ST a map which you check and add elements to should do the job fine. Just make this check the first part of an "and" statement, if it's already there you short circuit and return false.</span></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Dec 13, 2016 at 5:26 PM, Edward Z. Yang <span dir="ltr"><<a href="mailto:ezyang@mit.edu" target="_blank">ezyang@mit.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hello Michael,<br>
<br>
I've been looking for an elegant, functional implementation of DFA<br>
minimization and I have not found it.  If you discover a way to do<br>
it please share.<br>
<br>
However, I have seen some papers which might be relevant to the<br>
problem (although not necessarily good for writing a Haskell<br>
implementation).<br>
<br>
The CoCaml paper <<a href="https://www.cs.cornell.edu/~kozen/papers/cocaml.pdf" rel="noreferrer" target="_blank">https://www.cs.cornell.edu/~<wbr>kozen/papers/cocaml.pdf</a>><br>
discusses how to write recursive functions on infinite objects, which<br>
would ordinarily not terminate, but in their language are instead<br>
treated as a set of recursive equations and solved by some extralinguistic<br>
constraint solver.  This is similar in spirit to your desire to "detect<br>
diversion" when you loop around the memotable.<br>
<br>
The Datafun paper <<a href="https://people.mpi-sws.org/~neelk/datafun.pdf" rel="noreferrer" target="_blank">https://people.mpi-sws.org/~<wbr>neelk/datafun.pdf</a>><br>
recently reminded me that Datalog-style programming is all about<br>
fixpoints.  I wonder if DFA minimization can be done in a Datalog-like<br>
language.<br>
<br>
I have no idea if these are actually relevant, and would be interested<br>
to hear if they are.<br>
<br>
Edward<br>
<br>
Excerpts from Michael George's message of 2016-12-10 11:50:03 -0500:<br>
<div class="HOEnZb"><div class="h5">> I've come across a slight variant of memoization and I'm curious if<br>
> either there is a better way to think about (I have yet to reach Haskell<br>
> Enlightement), or if it's been thought about before.<br>
><br>
> I'm writing a program that does DFA minimization, as described here:<br>
> <a href="https://www.tutorialspoint.com/automata_theory/dfa_minimization.htm" rel="noreferrer" target="_blank">https://www.tutorialspoint.<wbr>com/automata_theory/dfa_<wbr>minimization.htm</a>.<br>
><br>
> For me, the simplest way to understand the algorithm is we form an<br>
> equivalence relation, where two states are different if either one is<br>
> final and the other isn't, or if there are transitions from them to<br>
> states that are different.<br>
><br>
> different a b = isFinal a && not (isFinal b) || isFinal b && not<br>
> (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.<br>
>   The standard algorithm builds a table, starting with the assumption<br>
> that all states are the same, and iteratively applying this definition<br>
> until it converges.<br>
><br>
> I'm thinking of that algorithm as a memoized version of the<br>
> 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<br>
> b && not (isFinal a) || exists chars (\c -> different'' (step a c) (step<br>
> b c))<br>
><br>
> for the same reason; it diverges.  But with memoization I can detect the<br>
> diversion by putting a marker in the memo table.  If the computation<br>
> makes a recursive call on an input that is started but not computed,<br>
> 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<br>
> (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<br>
> denotational semantics is rusty (maybe it's the least fixed point of f<br>
> that is greater than g or something, but that's not it).  I suspect that<br>
> there needs to be a nice relationship between f and g for<br>
> memoFixWithDefault f g to be sensible.  I also suspect that there's a<br>
> cute 3-line implementation like all the other implementations of memoize<br>
> out there, but I don't see it.  I also suspect that depth-first search<br>
> has a cute implementation using this combinator.<br>
><br>
> So I was wondering if other people had thoughts or references before I<br>
> 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-<wbr>bin/mailman/listinfo/haskell-<wbr>cafe</a><br>
Only members subscribed via the mailman list are allowed to post.</div></div></blockquote></div><br></div>