How does banker’s method work?

How does banker’s method work?

I am reading Purely Functional Data Structures and I have trouble understanding the banker's method for persistent data structures.

Lets define tail' (_ : (!xs)) = xs, then:

For tail (tail [1,2]) the unshared cost is 1 because you just create thunk.

For tail' (tail' [1,2]) the unshared cost is 2 because you actually evaluate the expression.

Am I right?

The amortized cost of an operation is the unshared cost of the operation plus the number of debits discharged by the operation.

But how do you actually discharge debits? Author never mentions that…

Submitted July 17, 2017 at 04:51PM by Ford_O
via reddit


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s