[Haskell-cafe] Honest constant-space mergesort

[Ryan Reich]

With list fusion, neither input nor output actually is necessarily
allocated. Though I take your point, I'm not griping about setup code that
maintains a pure facade, but about the allocations that purity demands in
the middle.

On Sat, Jan 12, 2019, 13:59 Frank Staals <frank at fstaals.net wrote:

> Ryan Reich <ryan.reich at gmail.com> writes:
>
> > I am, for entertainment, trying to figure out how to implement a
> > constant-space bottom-up mergesort in Haskell.  This is quite easy to at
> > least describe imperatively: break the list into ordered blocks, merge
> > adjacent ones, and repeat with double the length until there's only one
> > block and you're done.  For a linked list like [a] in Haskell, this
> should
> > be constant-space.  Unfortunately, it is not.
> >
> > You can definitely express the above algorithm nicely if you organize
> those
> > blocks into an [[a]], but then you are creating O(n) new lists.  Even if
> > you go to extremes to keep the blocks concatenated, though, you still
> have
> > the issue that every time you merge two lists, you are creating a new
> list
> > and that involves the allocator.  (Note that the implementation of
> > Data.List.sort does this.)
> >
> > The C equivalent would proceed by just overwriting the linking pointers
> in
> > each node, without allocating new nodes to do so, but of course, that's
> not
> > going to work in Haskell.  I considered using something like STRef to
> > represent the links (so, departing from the plain [a] type) but even
> then,
> > if you overwrite the contents of one of those, the garbage collector
> still
> > needs to know.  This is better than allocating more space, but it is not
> > necessary because the algorithm never actually makes any of the nodes
> > unreachable.  Also, I understand that using a lot of STRefs is bad for
> > efficiency.
> >
> > Is there any way to do this in (GHC) Haskell and get the algorithm down
> to
> > the bare minimum?  If there is, is it any different than just "writing C
> in
> > Haskell"?  That is, can one coerce GHC into emitting the mutable-link
> > operations and not doing collections, from high-level code?  Although
> I've
> > definitely seen examples of algorithms that compile down to such unboxed
> > depths, this one has been really resistant to improvement.
> >
> > Thanks,
> > Ryan Reich
> > _______________________________________________
> > 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.
>
> If you want your sort function to have type: Ord a => [a] -> [a] then I
> would think that you'd need to at least n new space anyway (where n is
> the length of the list), since you cannot actually overwrite the input
> list anyway.
>
> --
>
> - Frank
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20190112/ed01f4a8/attachment.html>