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
bug in nodes
#7
Comments
I believe the fix is to define the nodes() function like it is on page 8 of the paper. I have updated my CoffeeScript version like this: nodes = (m, xs, res)->
res = res ? []
switch xs.length
when 2 then res.push new Node(m, xs)
when 3 then res.push new Node(m, xs)
when 4 then res.push new Node(m, [xs[0], xs[1]]), new Node(m, [xs[2], xs[3]])
else
res.push new Node m, [xs[0], xs[1], xs[2]]
nodes m, xs.slice(3), res
res Note that I added the accumulator |
You mean quadratic? Is there a bound on the number of nodes returned by this procedure? |
Last time I calculated array insert behavior, it was O(n) but that was a long time ago, has it changed to quadratic now? ;) |
I misunderstood. You meant "avoid linear behaviour when inserting a single element (using concat I suppose, which produces a complete copy of the original array) by using push, which updates the array using at most linear time but amortized constant time". |
Sorry to come back so late but we should have EDIT: See end of Section 3.3 of Hinze and Paterson (Finger trees: a simple general-purpose data structure) page 9 (paragraph starting with "It is easy to check..." and Exercise 2). |
It there a reason why it is assumed that
xs.length <= 8
here? There is no such assumption in Hinze and Paterson.The text was updated successfully, but these errors were encountered: