[Haskell] Problems with using the memo-function
Tom Hofte
hofte at natlab.research.philips.com
Tue Nov 30 03:20:51 EST 2004
Dear all,
I have a problem when I use the memo-function to implement a dynamic programming algorithm to traverse a graph.
I use the memo-function in the code below:
dynamicPropagationUpAlg cname graph = let
mh n = memo h n
h n = let
annotsuccs = (nub (concat (map (memo h) (succs n))))
in
-- When the annotation set of the
-- current node is empty, then we have to
-- perform a
if (length (myannots n) == 0) && ((length annotsuccs) > 1)then
{- if length (succs n) > 1 then
error ("<<Annotation failure>> Interface has to be annotated. "++(show n))
else -}
case (trace ("Analyzing in component "++cname++"..\n"++"Before renaming successors annotations\n"++"Check for cycles in: \n"++"Comp: "++(getCompname n)++" Intf: "++(getIntfname n)++" Inst: "++(getFunname n)) (hasCycleInAnnots annotsuccs)) of
Nothing -> map (replaceFunname (getCompname n)(getFunname n)) annotsuccs
jMessage@(Just a) -> error (fromJust jMessage)
else
let
mergeannots = mergeAnnotSets (annotsuccs++(myannots n)) (myannots n)
in
case (trace ("Analyzing in component "++cname++"..\n"++"After merging successors annotations\n"++"Check for cycles in: \n"++"Comp: "++(getCompname n)++" Intf: "++(getIntfname n)++" Inst: "++(getFunname n)) (hasCycleInAnnots mergeannots)) of
Nothing -> mergeannots
jMessage@(Just a) -> error (fromJust jMessage)
g n@(InterfaceNode (annots, bo ,tp) names) = (InterfaceNode ((memo h n), bo, tp) names)
succs n = (getSuccsOfNode n graph)
myannots (InterfaceNode (annots,b,tp) names) = annots
nodes = listNodes graph
getFunname (InterfaceNode (annots, bo ,tp) (c,t,i)) = i
getCompname (InterfaceNode (annots, bo ,tp) (c,t,i)) = c
getIntfname (InterfaceNode (annots, bo ,tp) (c,t,i)) = t
in
map (g) nodes
The idea is that the every node in the graph is visited only once, moreover that the function "h" is computed only once for every node.
My implementation is not working properly. I don't know the cause for my problem, so can anyone hint me one the right use of the memo-function?
Thanks in advance..
Kind regards,
Tom
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org//pipermail/haskell/attachments/20041130/180f596c/attachment-0001.htm
More information about the Haskell
mailing list