[Haskell-cafe] Basic list exercise

[Jeff Clites]

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 <migmit at gmail.com> 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 <johannes.waldmann at htwk-leipzig.de> 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#sort
>> 
>> 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.Internal.Sorting.html#sortBy
>> 
>> 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.