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