I actually suspect that your &quot;<span class="Apple-style-span" style="border-collapse: collapse; ">supremum&quot; and &quot;</span><span class="Apple-style-span" style="border-collapse: collapse; ">infimum&quot; functions are the problem here -- they look like they might be accumulating thunks and blowing your stack. But beyond this, they&#39;re also o(n) for what could be effectively an o(log n) operation at the least, if you used ordered sets.</span><div>
<span class="Apple-style-span" style="border-collapse: collapse;"><br class="webkit-block-placeholder"></span></div><div><span class="Apple-style-span" style="border-collapse: collapse;">I&#39;d start improving performance here with some profiling, and then some strictness annotations, and then go from there.</span></div>
<div><span class="Apple-style-span" style="border-collapse: collapse;"><br class="webkit-block-placeholder"></span></div><div><span class="Apple-style-span" style="border-collapse: collapse;">See&nbsp;<a href="http://www.haskell.org/haskellwiki/Performance">http://www.haskell.org/haskellwiki/Performance</a> for a whole bunch of good tips.</span></div>
<div><span class="Apple-style-span" style="border-collapse: collapse;"><br class="webkit-block-placeholder"></span></div><div><span class="Apple-style-span" style="border-collapse: collapse;">--Sterl<br></span><br><div class="gmail_quote">
On Mon, May 5, 2008 at 11:57 AM, Kirill Kuvaldin &lt;<a href="mailto:kirill.kuvaldin@gmail.com">kirill.kuvaldin@gmail.com</a>&gt; wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
Hello,<br>
<br>
I wrote a program in haskell that works with lattice finite automata<br>
(the generalization of notion of finite state automata). Let me post<br>
the source code as it is not that long...<br>
<br>
The problem is that my algorithm that computes the run (see function<br>
fun) of an automaton on the given word is not very optimal and takes a<br>
loooong time as the input word gets larger... (e.g. try this one &quot;run<br>
m3 &quot;11101101110001010101&quot; &quot;)<br>
<br>
Due to the nature of every haskell function being a referentially<br>
transparent, I think I could have speeded up<br>
its performance using memoization.<br>
<br>
I&#39;ve read the page on haskell wiki<br>
(<a href="http://www.haskell.org/haskellwiki/Memoization" target="_blank">http://www.haskell.org/haskellwiki/Memoization</a>) but it didn&#39;t help me<br>
because it looks I have to modify the actual function source code to<br>
make use of memoized values.<br>
What I&#39;m looking for is a kind of a general solution (say, silver<br>
bullet :) ) so that I will be able to use my function like<br>
<br>
&gt; new_run = memoize run<br>
<br>
and the results of the &quot;new_run&quot; get automatically memoized. Probably<br>
it makes sense to memoize deltaext func as well.<br>
<br>
Is that possible to do that in Haskell??<br>
<br>
Thanks a lot!<br>
Kirill<br>
<br>
<br>
======= SOURCE CODE =====<br>
<br>
-- data type for lattice<br>
data Lattice l = Lattice<br>
 &nbsp; &nbsp; &nbsp;[l] &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;-- set of lattice elements<br>
 &nbsp; &nbsp; &nbsp;(l -&gt; l -&gt; l) &nbsp; &nbsp;-- supremum operation<br>
 &nbsp; &nbsp; &nbsp;(l -&gt; l -&gt; l) &nbsp; &nbsp;-- infimum operation<br>
<br>
-- returns the lowest lattice element<br>
lattice0 (Lattice l s i) = l !! 0<br>
-- returns the greatest lattice element<br>
lattice1 (Lattice l s i) = l !! ((length l)-1)<br>
<br>
-- supremum of 2 lattice elements<br>
sup (Lattice l s i) x y = s x y<br>
-- infimum of 2 lattice elements<br>
inf (Lattice l s i) x y = i x y<br>
<br>
<br>
supremum (Lattice l sup inf) [] = lattice0 (Lattice l sup inf)<br>
supremum (Lattice l sup inf) (x:xs) = sup x (supremum (Lattice l sup inf) xs)<br>
<br>
infimum (Lattice l sup inf) [] = lattice1 (Lattice l sup inf)<br>
infimum (Lattice l sup inf) (x:xs) = inf x (infimum (Lattice l sup inf) xs)<br>
inf3 (Lattice l s i) x y z = infimum (Lattice l s i) [x,y,z]<br>
<br>
--- data type for Lattice Automata (LA)<br>
data LA l state sym = LA<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (Lattice l) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;-- lattice<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [state] &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;-- set of states<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [sym] &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;-- alphabet<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (state -&gt; sym -&gt; state -&gt; l) &nbsp; -- fuzzy transition function<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (state -&gt; l) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; -- fuzzy initial state<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (state -&gt; l) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; -- fuzzy final state<br>
<br>
--- extended transition function<br>
deltaext :: (Eq state) =&gt; (LA l state sym) -&gt; state -&gt; [sym] -&gt; state -&gt; l<br>
deltaext (LA l states chars delta sigma0 sigma1) x [] y =<br>
 &nbsp; &nbsp; &nbsp; &nbsp;if x == y then (lattice1 l) else (lattice0 l)<br>
deltaext la@(LA l states chars delta sigma0 sigma1) x (a:w) y =<br>
 &nbsp; &nbsp; &nbsp; &nbsp;supremum l<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [ inf l<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (delta x a z)<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (deltaext la z w y)<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; | z &lt;- states]<br>
<br>
-- runs the Lattice Automaton on the given word<br>
run la@(LA l states chars delta sigma0 sigma1) w =<br>
 &nbsp; supremum l<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[ inf3 l<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (sigma0 x)<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (deltaext la x w y)<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (sigma1 y) | x &lt;- states, y &lt;- states]<br>
<br>
---<br>
--- examples<br>
---<br>
<br>
l3 = Lattice [0.0, 0.5, 1.0] max min where<br>
 &nbsp; max x y = if x &gt; y then x else y<br>
 &nbsp; min x y = if x &lt; y then x else y<br>
<br>
m3 = LA l3 [&#39;a&#39;, &#39;b&#39;] [&#39;0&#39;, &#39;1&#39;] delta sigma0 sigma1 where<br>
 &nbsp; &nbsp;delta &#39;a&#39; &#39;0&#39; &#39;a&#39; = 1<br>
 &nbsp; &nbsp;delta &#39;a&#39; &#39;0&#39; &#39;b&#39; = 0.5<br>
 &nbsp; &nbsp;delta &#39;b&#39; &#39;0&#39; &#39;a&#39; = 0.5<br>
 &nbsp; &nbsp;delta &#39;b&#39; &#39;0&#39; &#39;b&#39; = 1<br>
 &nbsp; &nbsp;delta &#39;a&#39; &#39;1&#39; &#39;a&#39; = 0<br>
 &nbsp; &nbsp;delta &#39;a&#39; &#39;1&#39; &#39;b&#39; = 1<br>
 &nbsp; &nbsp;delta &#39;b&#39; &#39;1&#39; &#39;a&#39; = 1<br>
 &nbsp; &nbsp;delta &#39;b&#39; &#39;1&#39; &#39;b&#39; = 1<br>
 &nbsp; &nbsp;sigma0 &#39;a&#39; = 1<br>
 &nbsp; &nbsp;sigma0 &#39;b&#39; = 0.5<br>
 &nbsp; &nbsp;sigma1 &#39;a&#39; = 0.5<br>
 &nbsp; &nbsp;sigma1 &#39;b&#39; = 1<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
</blockquote></div><br></div>