Equilibrium index: Difference between revisions

===ES6 Procedural===

Two pass O(n), returning only the first equilibrium index.

===ES6 Functional===

A composition of pure generic functions, returning all equilibrium indices.

<lang javascript>(() => {

'use strict';

// equilibriumIndices :: [Int] -> [Int]

const equilibriumIndices = xs =>

zip(scanl1(add)(xs))(

scanr1(add)(xs)

).reduceRight((a, xy, i) =>

xy[0] === xy[1] ? (

[i, ...a]

) : a, []);

// ------------------------TEST------------------------

const main = () => {

console.log(JSON.stringify(

[

[-7, 1, 5, 2, -4, 3, 0],

[2, 4, 6],

[2, 9, 2],

[1, -1, 1, -1, 1, -1, 1],

[1],

[]

].map(equilibriumIndices)

));

// -> [[3, 6], [], [1], [0, 1, 2, 3, 4, 5, 6], [0], []]

};

// -----------------GENERIC FUNCTIONS------------------

// Tuple (,) :: a -> b -> (a, b)

const Tuple = a =>

b => ({

type: 'Tuple',

'0': a,

'1': b,

length: 2

});

// add (+) :: Num a => a -> a -> a

const add = a =>

// Curried addition.

b => a + b;

// scanl :: (b -> a -> b) -> b -> [a] -> [b]

const scanl = f =>

// scanl is like foldl or reduce, but

// returns a succession of intermediate

// values, building from the left.

v => xs => xs.reduce((a, x) => {

const v = f(a[0])(x);

return Tuple(v)(a[1].concat(v));

}, Tuple(v)([v]))[1];

// scanr :: (b -> a -> b) -> b -> [a] -> [b]

const scanr = f =>

// scanr is like foldr or reduceRight, but

// returns a succession of intermediate

// values, building from the right.

v => xs => xs.reduceRight((a, x) => {

const v = f(x)(a[0]);

return Tuple(v)([v].concat(a[1]));

}, Tuple(v)([v]))[1];

// scanl1 :: (a -> a -> a) -> [a] -> [a]

const scanl1 = f =>

// scanl1 is a variant of scanl that has no

// seed-value argument, and assumes that

// xs is not empty.

xs => xs.length > 0 ? (

scanl(f)(

xs[0]

)(xs.slice(1))

) : [];

// scanr1 :: (a -> a -> a) -> [a] -> [a]

const scanr1 = f =>

// scanr1 is a variant of scanr that has no

// seed-value argument, and assumes that

// xs is not empty.

xs => xs.length > 0 ? (

scanr(f)(

xs.slice(-1)[0]

)(xs.slice(0, -1))

) : [];

// zip :: [a] -> [b] -> [(a, b)]

const zip = xs =>

ys => Array.from({

length: Math.min(xs.length, ys.length)

}, (_, i) => [xs[i], ys[i]]);

// MAIN ---

return main();

})();</lang>

{{Out}}

<pre>[[3,6],[],[1],[0,1,2,3,4,5,6],[0],[]]</pre>