[Haskell-cafe] Bad recursion? When can something be on both sides of an equation?

[Tom Ellis]

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