# Functional Implementation of Co-prime pairs in array

Program finds the number of pairs of co-primes in an array using functional concepts in Node.js

const assert = require('assert')

const gcd = (a, b) => (b != 0) ? gcd(b, a % b) : a

const co_prime = (a, b) => gcd(a, b) == 1

const co_prime_pairs = (_list) => {
co_primes = []
_list.map(
(x, i) => _list.slice(i + 1)
.filter(y => co_prime(x, y))
.forEach(y => co_primes.push([x, y]))
)
return co_primes.length
}

const main = () => {
assert.equal(co_prime_pairs([1, 2, 3]), 3)
assert.equal(co_prime_pairs([4, 8, 3, 9]), 4)
}

main()


Is the time complexity similar to that of the simple for-loop implementation?

Is there any scope for improving the time-complexity by using map and filter functions?

How is my choice of variable names?

How is code formatting?

• Random thought: consider prime factoring the list elements, and then using hashes or something so you don't have to loop through each pair. – Barry Carter Nov 4 '17 at 17:38

How is my choice of variable names?

In general you used snake case for the function names which is more a ruby-style.

Additionally the function co_prime_pairs let me acept that it return pairs of co-primes. However it returns a number of co-pairs inside an array.

The variable co_primes is declared globally.

## co_prime_pairs

This function is not a pure function internally because .forEach(y => co_primes.push([x, y])) modifies co_primes.
I rewrite the function and spit the logic into:

1. build pairs
2. filter the co primes
3. return the length

The functions:

const filterCoPrimes = xss =>
xss.filter(xs => isCoPrime(xs[0], xs[1]))

const buildPair = x => y =>
[x, y]

const buildPairs = (xs, pairs) =>
xs.length === 0 || xs.length === 1
? pairs
: buildPairs(
xs.slice(1),
pairs.concat(xs.map(buildPair(xs[0])))
)


The chain:

const co_prime_pairs = xs =>
filterCoPrimes(buildPairs(xs, [])).length


If we use pipe as a kind of function composition it can be rewritten to:

const co_prime_pairs = pipe(
buildPairs([]),
filterCoPrimes,
length
)


# Full working Example

• function calls:

const gcd = (a, b) =>
(b != 0) ? gcd(b, a % b) : a

const isCoPrime = (a, b) =>
gcd(a, b) === 1

const filterCoPrimes = xss =>
xss.filter(xs => isCoPrime(xs[0], xs[1]))

const buildPair = x => y =>
[x, y]

const buildPairs = (xs, pairs) =>
xs.length === 0 || xs.length === 1
? pairs
: buildPairs(
xs.slice(1),
pairs.concat(xs.map(buildPair(xs[0])))
)

const co_prime_pairs = xs =>
filterCoPrimes(buildPairs(xs, [])).length

console.log(co_prime_pairs([4, 8, 3, 9]))

• with pipe:

const pipe = (...fns) => fns.reduce((f, g) => (...args) => g(f(...args)))

const filter = fn => xs =>
xs.filter(fn)

const map = fn => xs =>
xs.map(fn)

const length = xs =>
xs.length

const gcd = (a, b) =>
(b != 0) ? gcd(b, a % b) : a

const isCoPrime = (a, b) =>
gcd(a, b) === 1

const filterCoPrimes = xss =>
xss.filter(xs => isCoPrime(xs[0], xs[1]))

const buildPair = x => y =>
[x, y]

const buildPairs = pairs => xs =>
xs.length === 0 || xs.length === 1
? pairs
: buildPairs
( pairs.concat(xs.map(buildPair(xs[0]))) )
( xs.slice(1) )

const co_prime_pairs = pipe(
buildPairs([]),
filterCoPrimes,
length
)

console.log(co_prime_pairs ([4, 8, 3, 9]))