fingertree.js

fingertree.js copied to clipboard

It there a reason why it is assumed that xs.length <= 8 here? There is no such assumption in Hinze and Paterson.

const FingerTree = require( 'fingertree' ) ;
let X = FingerTree.fromArray( [ ] ) ;
for ( let i = 0 ; i < ( 4 * 4 + 4 ) ; ++i ) X = X.addLast( i ) ;
let Y = FingerTree.fromArray( [ ] ) ;
for ( let i = 0 ; i < ( 4 * 4 + 4 ) ; ++i ) Y = Y.addFirst( i ) ;
X.concat( Y ).measure( )
Error: invalid number of nodes
    at nodes (/home/aureooms/node_modules/fingertree/src/fingertree.js:994:22)
    at DelayedFingerTree.thunk (/home/aureooms/node_modules/fingertree/src/fingertree.js:963:35)
    at DelayedFingerTree.force (/home/aureooms/node_modules/fingertree/src/fingertree.js:794:24)
    at DelayedFingerTree.measure (/home/aureooms/node_modules/fingertree/src/fingertree.js:810:17)
    at FingerTree.Deep.measure (/home/aureooms/node_modules/fingertree/src/fingertree.js:576:52)
    at DelayedFingerTree.measure (/home/aureooms/node_modules/fingertree/src/fingertree.js:810:25)
    at FingerTree.Deep.measure (/home/aureooms/node_modules/fingertree/src/fingertree.js:576:52)
    at repl:1:15
    at REPLServer.defaultEval (repl.js:164:27)
    at bound (domain.js:250:14)

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 res to avoid linear array insert behavior

Note that I added the accumulator res to avoid linear array insert behavior

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". While I meant "avoid quadratic behaviour when inserting n elements..." which is the same.

Sorry to come back so late but we should have xs.length <= 12 (hint: solve x = ceil(x/3) + 8) so the implementation does not have to handle all lengths.

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).