[Haskell-cafe] Bad recursion? When can something be on both sides of an equation?
Jeffrey Brown
jeffbrown.the at gmail.com
Thu Mar 12 18:15:47 UTC 2015
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 at 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 at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20150312/c1afca30/attachment.html>
More information about the Haskell-Cafe
mailing list