[Haskell-cafe] Bad recursion? When can something be on both sides of an equation?
Tom Ellis
tom-lists-haskell-cafe-2013 at jaguarpaw.co.uk
Thu Mar 12 09:46:45 UTC 2015
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
More information about the Haskell-Cafe
mailing list