search

andrewthad / linear-containers

Containers supporting in-place modification
BSD 3-Clause "New" or "Revised" License
5 stars 1 forks source link

More Polymorphic Functions #8

Closed andrewthad closed 5 years ago

andrewthad commented 5 years ago

The map function from Linear.List is sadly less polymorphic than its counterpart in Data.List. While it is possible to write a more polymorphic map, it requires reallocating every cons cell.

andrewthad commented 5 years ago

Wait a minute. The map function in Linear.List already has to reallocate every cons cell.

chessai commented 5 years ago

yep

andrewthad commented 5 years ago

Nevermind. The real underlying problem ends up being Linear.Reference.modify. It has to be monomorphic. We could have a variant that can change the type of the payload, but it would free the original reference and allocate new memory.

That said, it is still possible to provide both flavors. The options are: (1) a rewrite rule when the types match or (2) another module for more polymorphic variants.

andrewthad commented 5 years ago

I lean toward the second option.

chessai commented 5 years ago

i like (2) better

andrewthad commented 5 years ago

As I think about it more, the utility of map on most of the data structures built here is minimal. The goal is to allow the user to have giant maps that live in unmanaged memory. Mapping over one of these would still be expensive because you would have to touch every value in the map. For the toy example of a singly-linked list, map seems less awful (since most algorithms operating on a linked list have to scan the whole thing anyway), but on many data structures with better performance characteristics, this operation isn't worth doing, monomorphically or polymorphically.

andrewthad commented 5 years ago

The unsound approach can still be found at https://github.com/andrewthad/linear-containers/tree/non_higher_kinded_static_reference. I'm closing this for now, but anyone can feel free to comment here if they have a breakthrough.