Convert imperative to functional style using ramda.js

Question

I'm write the code for convert array of number to new datalist using imperative style but i want to convert it to functional style using javascript library like ramdajs

background of code Suppose the dollar value There are 5 coins in total, 25 dollars, 20 dollars, ... 1 dollar. We will have to exchange money for dollar coins. With the least amount of coins

const data = [25, 20, 10, 5, 1];
const fn = n => data.map((v) => {
    const numberOfCoin = Number.parseInt(n / v, 10);
    const result = [v, numberOfCoin];
    n %= v;
    return numberOfCoin ? result : [];
  }).filter(i => i.length > 0);

the result of this code should be

fn(48) => [[25, 1], [20, 1], [1, 3]]
fn(100) => [[25, 4]]

Answer 1

This variant of the answer from user633183 will find the minimum number of coins, it doesn't use the common technique that chooses the maximum number of each larger denomination at the possible expense of choosing more coins overall.

Note that this can involve substantially more calculations than the original answers or the initial ones from customcommander.

change here returns a list of coin values, so for, say, 58 it will return [25, 25, 5, 1, 1, 1]. makeChange converts that to the [ [25, 2], [5, 1], [1, 3] ] format. If you change the minLength function from <= to <, then this would generate [ [25, 1], [20, 1], [10, 1], [1, 3] ]. This is the same number of coins, but using different denominations.

If the order of the return doesn't matter to you, you could also remove the sort line.

The mix of styles here is somewhat unfortunate. We could replace that Ramda pipeline version of makeChange with one more like change if we tried. But I think in Ramda; this is what came most easily to mind. Replacing change with a Ramda pipeline would not be as easy, as it's harder to do recursion in such a style.

---

Thanks to customcommander for pointing out a flaw in an earlier version of this answer.

---

const minLength = (as, bs) =>
  as.length <= bs.length ? as : bs

const change = ([ c, ...rest ], amount = 0) => 
  amount === 0
    ? []
    : c === 1
      ? Array(amount).fill(1) 
      : c <= amount
        ? minLength (
          [ c, ...change ([c, ...rest], amount - c)],
          change (rest, amount)
        )
        : change (rest, amount)

const makeChange = pipe(
  change,
  countBy(identity),
  toPairs,
  map(map(Number)),
  sort(descend(head)) // if desired
)

const coins =
  [ 25, 20, 10, 5, 1 ]

console.log (makeChange (coins, 40))
//=> [ [ 20, 2 ] ]

console.log (makeChange (coins, 45))
//=> [ [ 25, 1 ], [ 20, 1 ] ]

console.log (change (coins, 48))
//=> [ [ 25, 1 ], [ 20, 1 ], [ 1, 3 ] ]

console.log (makeChange (coins, 100))
//=> [ [ 25, 4 ] ]

<script src = "https://cdnjs.cloudflare.com/ajax/libs/ramda/0.26.1/ramda.js"></script>
<script> const { pipe, countBy, identity, toPairs, map, sort, descend, head } = R </script>

Answer 2

I think you had a pretty good start already but there are a few things I'd change in order to make it more functional:

1. Use expressions rather than statements (e.g. no return)
2. Do not mutate data (e.g. no n %= v)

You don't necessarily need Ramda for this:

const coins = value =>
  [25, 20, 10, 5, 1].reduce(([acc, val], cur) =>
    val < cur ? [acc, val] : [[...acc, [cur, Math.floor(val / cur)]], val % cur],
    [[], value]
  )[0];


console.log(coins(48));
console.log(coins(100));

If you find yourself using map then filter, you're most likely needing reduce. In my function coins above, the iterator returns an array that contains an array of pairs of coins and number of coins and the reduced value for each step.

Note that at each step I use a destructuring assignment to capture the array of pairs and the reduced value in individual parameters.

Now, it is of course possible to use Ramda for this as well:

const {compose, filter, last, mapAccum, flip} = R;

const mapIterator = (a, b) => [a % b, [b, Math.floor(a / b)]];
const withCoins = ([coins, number]) => number > 0;
const coins = compose(filter(withCoins), last, flip(mapAccum(mapIterator))([25, 20, 10, 5, 1]));

console.log(coins(48));
console.log(coins(100));

<script src="https://cdnjs.cloudflare.com/ajax/libs/ramda/0.26.1/ramda.min.js"></script>

EDIT: as Scott rightly pointed out, any of my solutions above will give you the least amount of change.

This turned out to be more involved than I expected and I settled on a solution which I'm sure can be improved:

I define 5 sets of coins:

1. [1]
2. [5, 1]
3. [10, 5, 1]
4. [20, 10, 5, 1]
5. [25, 20, 10, 5, 1]

I compute how much change each set produces and keep only the one which produces the least.

For example to change 30:

1. 1 × 30
2. 5 × 6
3. 10 × 3
4. 20 × 1, 10 × 1 (Keep this set)
5. 25 × 1, 5 × 1

const {compose, pipe, sum, map, last, head, mapAccum, curry, flip, applyTo, sortBy, reject, not} = R;
const numCoins = compose(sum, map(last));
const changeFn = curry((coins, num) => mapAccum((cur, coin) => [cur % coin, [coin, Math.floor(cur / coin)]], num, coins)[1]);
const change1 = changeFn([1]);
const change2 = changeFn([5, 1]);
const change3 = changeFn([10, 5, 1]);
const change4 = changeFn([20, 10, 5, 1]);
const change5 = changeFn([25, 20, 10, 5, 1]);

const change = pipe(
  applyTo,
  flip(map)([
    change1,
    change2,
    change3,
    change4,
    change5]),
  sortBy(numCoins),
  head,
  reject(compose(not, last)));

console.log(change(30));
console.log(change(40));
console.log(change(48));

<script src="https://cdnjs.cloudflare.com/ajax/libs/ramda/0.26.1/ramda.min.js"></script>

Answer 3

People commonly reach for map, filter, and reduce but often the result is a bit of a square peg in a round hole.

• map doesn't makes sense because it's produces a 1-to-1 result; if I have 4 types of coins, I will always receive 4 types of change, which of course is not what we want. Use of filter forces you to do more processing to achieve the desired result.
• reduce can eliminate intermediate values caused by map+filter, but again, it's possible we will reach the desired result before having to analyze each coin. In the example of fn(100) which returns [ [25, 4] ], there's no need to even look at coins 20, 10, 5, or 1 because the result has already been reached; reducing further would be wasteful.

To me, functional programming is about convenience. If I don't have a function that does what I need, I simply make it, because it's important that my program clearly communicates its intention. Sometimes this means using a construct that's more suitable for datas I'm processing -

const change = (coins = [], amount = 0) =>

  loop                             // begin a loop, initializing:
    ( ( acc = []                   // an empty accumulator, acc
      , r = amount                 // the remaining amount to make change for, r
      , [ c, ...rest ] = coins     // the first coin, c, and the rest of coins
      ) =>

        r === 0                    // if the remainder is zero
          ? acc                    // return the accumulator

      : c <= r                     // if the coin is small enough
          ? recur                              // recur with
              ( [ ...acc, [ c, div (r, c) ] ]  // updated acc
              , mod (r, c)                     // updated remainder
              , rest                           // rest of coins
              )

                                   // otherwise (inductive) coin is too large
      : recur                      // recur with
          ( acc                    // unmodified acc
          , r                      // unmodified remainder
          , rest                   // rest of coins
          )

    )

Unlike map, filter, and reduce, our solution will not continue iterating over the input after the result has been determined. Using it looks like this -

const coins =
  [ 25, 20, 10, 5, 1 ]

console.log (change (coins, 48))
// [ [ 25, 1 ], [ 20, 1 ], [ 1, 3 ] ]

console.log (change (coins, 100))
// [ [ 25, 4 ] ]

Verify the results in your own browser below -

const div = (x, y) =>
  Math .round (x / y)

const mod = (x, y) =>
  x % y

const recur = (...values) =>
  ({ recur, values })

const loop = f =>
{ let acc = f ()
  while (acc && acc.recur === recur)
    acc = f (...acc.values)
  return acc
}

const change = (coins = [], amount = 0) =>
  loop
    ( ( acc = []
      , r = amount
      , [ c, ...rest ] = coins
      ) =>
        r === 0
          ? acc
      : c <= r
          ? recur
              ( [ ...acc, [ c, div (r, c) ] ]
              , mod (r, c)
              , rest
              )
      : recur
          ( acc
          , r
          , rest
          )

    )

const coins =
  [ 25, 20, 10, 5, 1 ]

console.log (change (coins, 48))
// [ [ 25, 1 ], [ 20, 1 ], [ 1, 3 ] ]

console.log (change (coins, 100))
// [ [ 25, 4 ] ]

Ramda users can use R.until, though readability suffers due to it's purely function-driven interface. Flexibility of loop and recur is highly favourable, imo -

const change = (coins = [], amount = 0) =>
  R.until
    ( ([ acc, r, coins ]) => r === 0
    , ([ acc, r, [ c, ...rest ] ]) =>
        c <= r
          ? [ [ ...acc
              , [ c, Math.floor (R.divide (r, c)) ]
              ]
            ,  R.modulo (r, c)
            , rest
            ]
          : [ acc
            , r
            , rest
            ]
    , [ [], amount, coins ]
    )
    [ 0 ]

Another alternative is to write it as a recursive function -

const div = (x, y) =>
  Math .round (x / y)

const mod = (x, y) =>
  x % y

const change = ([ c, ...rest ], amount = 0) =>
  amount === 0
    ? []
: c <= amount
    ? [ [ c, div (amount, c) ]
      , ...change (rest, mod (amount, c))
      ]
: change (rest, amount)

const coins =
  [ 25, 20, 10, 5, 1 ]

console.log (change (coins, 48))
// [ [ 25, 1 ], [ 20, 1 ], [ 1, 3 ] ]

console.log (change (coins, 100))
// [ [ 25, 4 ] ]