I actually suspect that your "<span class="Apple-style-span" style="border-collapse: collapse; ">supremum" and "</span><span class="Apple-style-span" style="border-collapse: collapse; ">infimum" functions are the problem here -- they look like they might be accumulating thunks and blowing your stack. But beyond this, they'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'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 <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 <<a href="mailto:kirill.kuvaldin@gmail.com">kirill.kuvaldin@gmail.com</a>> 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 "run<br>
m3 "11101101110001010101" ")<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'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'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'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>
> new_run = memoize run<br>
<br>
and the results of the "new_run" 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>
[l] -- set of lattice elements<br>
(l -> l -> l) -- supremum operation<br>
(l -> l -> l) -- 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>
(Lattice l) -- lattice<br>
[state] -- set of states<br>
[sym] -- alphabet<br>
(state -> sym -> state -> l) -- fuzzy transition function<br>
(state -> l) -- fuzzy initial state<br>
(state -> l) -- fuzzy final state<br>
<br>
--- extended transition function<br>
deltaext :: (Eq state) => (LA l state sym) -> state -> [sym] -> state -> l<br>
deltaext (LA l states chars delta sigma0 sigma1) x [] y =<br>
if x == y then (lattice1 l) else (lattice0 l)<br>
deltaext la@(LA l states chars delta sigma0 sigma1) x (a:w) y =<br>
supremum l<br>
[ inf l<br>
(delta x a z)<br>
(deltaext la z w y)<br>
| z <- states]<br>
<br>
-- runs the Lattice Automaton on the given word<br>
run la@(LA l states chars delta sigma0 sigma1) w =<br>
supremum l<br>
[ inf3 l<br>
(sigma0 x)<br>
(deltaext la x w y)<br>
(sigma1 y) | x <- states, y <- states]<br>
<br>
---<br>
--- examples<br>
---<br>
<br>
l3 = Lattice [0.0, 0.5, 1.0] max min where<br>
max x y = if x > y then x else y<br>
min x y = if x < y then x else y<br>
<br>
m3 = LA l3 ['a', 'b'] ['0', '1'] delta sigma0 sigma1 where<br>
delta 'a' '0' 'a' = 1<br>
delta 'a' '0' 'b' = 0.5<br>
delta 'b' '0' 'a' = 0.5<br>
delta 'b' '0' 'b' = 1<br>
delta 'a' '1' 'a' = 0<br>
delta 'a' '1' 'b' = 1<br>
delta 'b' '1' 'a' = 1<br>
delta 'b' '1' 'b' = 1<br>
sigma0 'a' = 1<br>
sigma0 'b' = 0.5<br>
sigma1 'a' = 0.5<br>
sigma1 'b' = 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>