Yes, I think that technique is equivalent to building the list you want backwards, and then reversing it at the end. (This is because the closures are forming a structure which is essentially a linked list, and when finally applied to an argument they build the desired actual list by traversing the closures in reverse order relative to how they were allocated.) So I agree, I don’t think it’s better in terms of allocation. Jeff

On Mar 24, 2023, at 10:53 AM, MigMit wrote:

If I understand correcly, Data.List is building a lot of closures — basically, a CPS transform. I though about it, but I'm not sure it is better.

...

...

On 24 Mar 2023, at 18:44, Johannes Waldmann wrote:

can we do better than this?

Does the implementation in Data.List do better?

https://hackage.haskell.org/package/base-4.18.0.0/docs/src/Data.OldList.html...

note that 'ascending' does some trickery there - perhaps exactly to solve the problem you describe?

Since this is about "exercise" - I would expect my students to find that code, so perhaps I'd point them to it right away, and give the task to "understand it" (= argue that it is correct). Arguing about cost seems harder.

NB: 'descending' is different here, and that's no surprise since lists are asymmetric. We do have a symmetric (and strict) implementation of sequences - how do we sort these?

https://hackage.haskell.org/package/containers-0.6.7/docs/src/Data.Sequence....

That's not exactly an advertisement for functional programming, as it has "state" written all over the place? But it makes for a nice exercise reading the types.

I needed some time to understand that the mouse-over block for an identifier contains _two_ types: the instantiated one (for the use site) and, below that, the general one (from the definition).

- J.W. _______________________________________________ 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.

_______________________________________________ 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.