[Haskell-cafe] Hyper-recursion?

Tue Jan 17 04:56:33 UTC 2017

@Albert Y. C. Lai, Yes, I'll look into open recursion.

@Anthony Clayden, I like the idea of the directed graph, no matter what the
final answer. Land parcel changes can be seen as hierarchical trees growing
branches -- until something needs to jump to another tree -- or a tree
pruned and moved to a new home. The WWW is a great example of this, i.e., a
DOM page inside a hierarchical site -- with links jumping outside. True,
the splitting and recombining of parcels goes on forever. But I see that as
recursion, like one of the classic examples, "infinite mirrors" (the
cascading layers produced when two mirrors face one another and you stand
in the middle). Basically, anything that is changing is bifurcating and,
thus, can be seen as recursion -- whether it "comes back" or not.

Programs "execute," which means they do steps, and then they're through and
give an answer or result. They leave logs, paper printouts, new things on
the disk, answers on the screen, etc. These are terminating discrete events
-- with no natural sense of connection other than piping to a next discrete
step or a historical recounting we set up ("chess software, show me my last
two moves."). Sure, looped GUI apps or your bash terminal or a REPL place a
wrappers around this; but there is no concept of having an event be just
one layer of the persistent mirror stack. Of course my infinite mirrors
analogy breaks down, because progressing from one layer to the next can
totally reshape the whole landscape, like completing a row in Tetris can
collapse lots of real estate instantly. And yet with today's Tetris (or
chess) software, what you see is just a graphical of the continually
updated memory field underneath. Again, any chaining of the events or
remembering a previous state is unnatural, intentional after-the-fact
incursion we have done, not a look at a truly stateless, timeless
"unfolding." This may be getting a bit theoretical, but consider the WWW.
It grows like an organism -- and, surely, not inside a "program" doing it,
imposing direction; there's no program stepping through tasks, no loop
creating sites and pages. This is recursion in the wild. For that matter,
life is recursion in the wild.

Maybe software simply can't go there. The best we can do is have stuff live
in a REPL session; but I'm not sure a REPL could be true hyper-recursion.

I harp on all this because if Haskell is stateless/immutable and in total
disregard of any underlying memory field, then it seems it should progress
to hyper-recursion. All examples like parcel maps, Tetris screens, chess
apps changing -- is just -- as I said above -- graphical views of an
underlying memory field's undoubtedly destructive overwriting. I guess I'm
asking, What is the opposite of this? What would we have if the memory
field wasn't changing state? The most obvious answer would be -- a runaway
memory leak. But could we avoid the runaway memory consumption, but have
the "unfolding," the statelessness by some comp-sci sleight of hand?

On Mon, Jan 16, 2017 at 9:09 PM, Anthony Clayden <
anthony_clayden at clear.net.nz> wrote:

> >> On 16 Jan 2017 04:43, "Lawrence Bottorff" <borgauf at
> gmail.com> wrote:
> >>
> >> A while back I worked at an assessor's office, i.e., the
> people responsible
> >> for handling properties as land parcels. ...
>
> Hi Lawrence, I too worked on land parcels -- a local
> government rates billing
> and land valuation application.
>
> >> ... how property changed hands, and especially how
> property lines
> >> changed due to properties either merging or being split
> up.
> >> That is to say, how the parcel map changed over time.
>
> I think the important aspect is that the a parcel
> can be split, and one of the splits merged with another
> parcel
> that was not originally with it.
>
> (I don't know how it was in your application. but in mine
>  a legal parcel might consist of discontiguous areas of land
>  -- for example a house in a terrace parcelled with a garage
> amongst
>  a block of garages at the end of the street,)
>
> That is, looking over history you cannot group the parcels
> into a
> strict hierarchy of splits.
>
> >> Somewhere in the functional paradigm, specifically
> recursion,
> >> would seem to be a model for this issue.
>
> No I'm not seeing anything specifically functional about
> this.
> It's a directed graph, where each node is an instance of
> parcel ownership.
>
> >> So in chapter 1 of any functional programming tutorial is
> the factorial
> >> calculation function done with recursion. We beginners
> see the recursion
> >> "going out" to the "last one," then "coming back," adding
> up the results of
> >> each stage as it returns . . . like a yo-yo winding out,
> >> then winding up again.
>
> Nice image, but there's no "last one" here (nor a "first
> one"
> that we could make sense of), There's no boundary
> from where we could be "coming back".
>
> Recursion does not apply [see more below]
>
> >> David Turner dct25-561bs at mythic-beasts.com
> >> Mon Jan 16 07:47:41 UTC 2017
> >>
> >> I suspect you have stumbled onto the dual concept of
> corecursion: ...
>
> Nor corecursion.
>
> a) because of the infinite and arbitrary potential for
> splits/mergers;
> b) because even if there was some time in the distant past
>     when the whole country was a single parcel with a single
> owner.
>     (The Emperor? But even empires and countries split and
> merge.
>      Or no owner, only hunter-gatherers/nomads,
>      which might as well be a single parcel.)
>     We're never going to try to rebuild that history.
> c) because there's never going to be a future end-state.
>     Arbitrary splits/mergers will continue forever.
>     We can't predict what might be the smallest parcels
>     some area of land could be split into.
>     (Note that one trick to prevent mineral exploitation
> companies
>      from buying up glorious scenery
>      is to split it into $1-parcels and sell each to a
> different owner.)
>
>
> >> ... Haskell being the most pure functional language, is,
> hence,
> >> my starting point on this question.
>
> There's nothing specifically Haskell in this.
> A better place to ask might be lambda-the-ultimate.
>
>
> Anthony
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20170116/88e64806/attachment.html>