[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))))
                                                                                                  -- 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)
                                                                                                       mergeannots = mergeAnnotSets (annotsuccs++(myannots n)) (myannots n)
                                                                                                      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
                                         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,

-------------- 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