[Haskell-cafe] Bad recursion? When can something be on both sides of an equation?
Jeffrey Brown
jeffbrown.the at gmail.com
Thu Mar 12 07:49:57 UTC 2015
Dear Haskellers,
In another thread [1], I talked about computing what I've been lately
calling the "total descendents" of a subset S of a graph: that is, the set
of nodes t for which every maximal sequence of predecessors intersects S. I
got it done, functionally [2]. But in the process I wrote something that
hangs, and I can't figure out why.
The problem arose in the following passage. (Glab stands for Graph Label, a
synonym for Int.)
totalDescendents :: S.Set Glab -> Graph -> S.Set Glab
totalDescendents roots graph = b
where (a,b,c,graph) = totalDescendentsCtrlr -- tricky
(roots, S.empty, M.empty, graph)
totalDescendentsCtrlr :: TotalDescendentsData -> TotalDescendentsData
totalDescendentsCtrlr (a,b,c,gr) =
if S.null a' -- fails, as does a == a'
-- a == a' is one iteration slower but should have same effect
then (a',b',c',gr')
else totalDescendentsCtrlr (a',b',c',gr')
where (a',b',c',gr') = visitUndetPrds $ visitTdSnvSucs (a,b,c,gr)
Notice that in the equation marked "tricky", the object "graph" appears on
both sides. I thought that was the problem, so I rewrote that line as the
following:
where (_,b,_,_) = totalDescendentsCtrlr
and sure enough, the problem vanished.
So I tried to distill that problem to something tiny, and came up with this:
f (a) = a'
where (a',b) = fBackend (a,b) -- tricky
fBackend (a,b) =
if a' < 1
then (a',b)
else fBackend (a',b)
where a' = a - 1
I see no substantive difference between the problem with the first body of
code and the problem I expected f and fBackend to have -- but f and
fBackend work fine!
Any idea what might be happening?
Thanks,
Jeff
[1] http://permalink.gmane.org/gmane.comp.lang.haskell.cafe/115353
[2]
https://github.com/JeffreyBenjaminBrown/digraphs-on-text/blob/master/TotalDescendents.hs
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20150312/bd1b2480/attachment.html>
More information about the Haskell-Cafe
mailing list