Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[RFC] Sized Difference List #33

Open
chshersh opened this issue May 9, 2020 · 2 comments
Open

[RFC] Sized Difference List #33

chshersh opened this issue May 9, 2020 · 2 comments
Labels
enhancement New feature or request idea

Comments

@chshersh
Copy link
Contributor

chshersh commented May 9, 2020

Because of how ordinary lists are implemented in Haskell, left-associative appending of such lists is very slow. The following takes much more time than it should:

((((l1 ++ l2) ++ l3) ++ l4) ++ ...)

Optimal appending order is the following:

l1 ++ (l2 ++ (l3 ++ (l4 ++ ...))))

There's a trick called Difference List which automatically rearranges list appending to get an optimal order. The trick is representing a list in a different way: instead of storing [a], you store [a] -> [a]. It's implemented in the following packages: https://hackage.haskell.org/package/dlist

This technique is very useful if you don't have control of how lists are appending (for example, when appending inside some recursive call).

I thought, that maybe slist package could provide a data type like SDList (similar to DList) — sized difference list to optimize appending. The problem with DList is since it represents the list as a function, you can't get any info from this function for free. With SDList you should be able to store size and get at list size, so I'm thinking about data type like this:

data SDList a = SDList Size (Slist a -> Slist a)

Do you think it's worth having such a structure in the library? I guess you don't need to implement bazillion functions for this structure at first, it will be enough to have a few basic functions, because mostly you're interested in appending such difference lists and converting from and to Slist.

@chshersh chshersh added the enhancement New feature or request label May 9, 2020
@vrom911
Copy link
Member

vrom911 commented May 9, 2020

That sounds like a fun ide, @chshersh a! I don't mind to experiment on that and see how it can come handy.

Slist is not that widely used and it is completely fine to add such interesting and very related structures to make it useful for more use-cases.

@chshersh chshersh added this to the 0.2.0.0: Richer interface milestone Jun 19, 2020
@chshersh
Copy link
Contributor Author

I'm now thinking, that probably the following type would be better:

data SDList a = SDList Size ([a] -> [a])

We keep size as a separate field, and append plain lists inside.

And then will have Semigroup instance for SDList and a function of type Slist a -> SDList a

@vrom911 vrom911 removed this from the 0.2.0.0: Richer interface milestone Mar 18, 2021
@chshersh chshersh added the idea label Mar 18, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request idea
Projects
None yet
Development

No branches or pull requests

2 participants