<div dir="auto">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.</div><br><div class="gmail_quote"><div dir="ltr">On Sat, Jan 12, 2019, 13:59 Frank Staals <<a href="mailto:frank@fstaals.net">frank@fstaals.net</a> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Ryan Reich <<a href="mailto:ryan.reich@gmail.com" target="_blank" rel="noreferrer">ryan.reich@gmail.com</a>> writes:<br>
<br>
> I am, for entertainment, trying to figure out how to implement a<br>
> constant-space bottom-up mergesort in Haskell.  This is quite easy to at<br>
> least describe imperatively: break the list into ordered blocks, merge<br>
> adjacent ones, and repeat with double the length until there's only one<br>
> block and you're done.  For a linked list like [a] in Haskell, this should<br>
> be constant-space.  Unfortunately, it is not.<br>
><br>
> You can definitely express the above algorithm nicely if you organize those<br>
> blocks into an [[a]], but then you are creating O(n) new lists.  Even if<br>
> you go to extremes to keep the blocks concatenated, though, you still have<br>
> the issue that every time you merge two lists, you are creating a new list<br>
> and that involves the allocator.  (Note that the implementation of<br>
> Data.List.sort does this.)<br>
><br>
> The C equivalent would proceed by just overwriting the linking pointers in<br>
> each node, without allocating new nodes to do so, but of course, that's not<br>
> going to work in Haskell.  I considered using something like STRef to<br>
> represent the links (so, departing from the plain [a] type) but even then,<br>
> if you overwrite the contents of one of those, the garbage collector still<br>
> needs to know.  This is better than allocating more space, but it is not<br>
> necessary because the algorithm never actually makes any of the nodes<br>
> unreachable.  Also, I understand that using a lot of STRefs is bad for<br>
> efficiency.<br>
><br>
> Is there any way to do this in (GHC) Haskell and get the algorithm down to<br>
> the bare minimum?  If there is, is it any different than just "writing C in<br>
> Haskell"?  That is, can one coerce GHC into emitting the mutable-link<br>
> operations and not doing collections, from high-level code?  Although I've<br>
> definitely seen examples of algorithms that compile down to such unboxed<br>
> depths, this one has been really resistant to improvement.<br>
><br>
> Thanks,<br>
> Ryan Reich<br>
> _______________________________________________<br>
> Haskell-Cafe mailing list<br>
> To (un)subscribe, modify options or view archives go to:<br>
> <a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
> Only members subscribed via the mailman list are allowed to post.<br>
<br>
If you want your sort function to have type: Ord a => [a] -> [a] then I<br>
would think that you'd need to at least n new space anyway (where n is<br>
the length of the list), since you cannot actually overwrite the input<br>
list anyway. <br>
<br>
--<br>
<br>
- Frank<br>
</blockquote></div>