Bad recursion? When can something be on both sides of an equation?
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/TotalDe...
On Thu, Mar 12, 2015 at 12:49:57AM -0700, Jeffrey Brown wrote:
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.
It's somewhat bizarre to write where (a,b,c,graph) = totalDescendentsCtrlr -- tricky (roots, S.empty, M.empty, graph) if where (_,b,_,_) = totalDescendentsCtrlr works, but it's a fair question from a desire to understand what's going on. When you write where (a,b,c,graph) = totalDescendentsCtrlr -- tricky (roots, S.empty, M.empty, graph) you are introducing a new name `graph` which shadows the old one. The result `graph` is "fed back in" as the input. You are saying that the value of `graph` depends on itself, which in general can lead to looping. You probably meant where (a,b,c,graph') = totalDescendentsCtrlr (roots, S.empty, M.empty, graph) or, since many of those variables are unused, as you said where (_,b,_,_) = totalDescendentsCtrlr (roots, S.empty, M.empty, graph)
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!
`fBackend` never does anything with the value of `b` whereas presumably `visitUndetPrds` and `visitTdSnvSucs` do do something with the value of `graph`. Tom
That makes sense! I did not realize the shadowing a where clauses causes happens within the where clause itself; I thought it only applied outside. Thanks, Tom! On Thu, Mar 12, 2015 at 2:46 AM, Tom Ellis < tom-lists-haskell-cafe-2013@jaguarpaw.co.uk> wrote:
On Thu, Mar 12, 2015 at 12:49:57AM -0700, Jeffrey Brown wrote:
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.
It's somewhat bizarre to write
where (a,b,c,graph) = totalDescendentsCtrlr -- tricky (roots, S.empty, M.empty, graph)
if
where (_,b,_,_) = totalDescendentsCtrlr
works, but it's a fair question from a desire to understand what's going on.
When you write
where (a,b,c,graph) = totalDescendentsCtrlr -- tricky (roots, S.empty, M.empty, graph)
you are introducing a new name `graph` which shadows the old one. The result `graph` is "fed back in" as the input. You are saying that the value of `graph` depends on itself, which in general can lead to looping. You probably meant
where (a,b,c,graph') = totalDescendentsCtrlr (roots, S.empty, M.empty, graph)
or, since many of those variables are unused, as you said
where (_,b,_,_) = totalDescendentsCtrlr (roots, S.empty, M.empty, graph)
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!
`fBackend` never does anything with the value of `b` whereas presumably `visitUndetPrds` and `visitTdSnvSucs` do do something with the value of `graph`.
Tom _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
participants (2)
-
Jeffrey Brown -
Tom Ellis