search

treeowl / compact-sequences

Stacks and queues with compact representations
BSD 3-Clause "New" or "Revised" License
16 stars 4 forks source link

Can we simplify queues and deques? #46

Open treeowl opened 4 years ago

treeowl commented 4 years ago

I really wanted to implement queues and deques by close analogy to Okasaki's implicit queue and implicit deque structures, with Hinze and Paterson's strictness modification to cons and snoc to avoid thunk chains. Unfortunately, I wasn't able to come up with an amortization argument to support that. Maybe someone else can help? If it's possible, then we'll be able to simplify the structures and code considerably, and likely improve performance.

treeowl commented 4 years ago

@koengit, we discussed this at ICFP. I'd be interested in your thoughts.

treeowl commented 4 years ago

I think I might have an idea. Okasaki's rule of thumb about adding debit allowances from left digits to ones from right digits doesn't seem to apply directly, but I think a modification might. I'm going to try a rule that a node contributes s debit allowance to all its descendants if one digit is safe, but 3*s debit allowance if both digits are safe. Maybe that'll do the trick?

treeowl commented 4 years ago

No, I don't see a way there either.