Can we simplify queues and deques?

[treeowl]

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]

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

[treeowl]

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]

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