Vfrdtyky

I have a function that returns the LCM of a range of numbers. It works great, but this has a function inside of a function inside of a function. My question is why can I not simplify the nested smallestCommon() by removing scm() from inside of it? Why does this particular solution need this if else functionality so deeply nested?

function smallestCommons(arr) {

  var max = Math.max(...arr);

  var min = Math.min(...arr);

  var candidate = max;



  var smallestCommon = function(low, high) {

  // inner function to use 'high' variable

    function scm(l, h) {

      if (h % l === 0) {

         return h;

      } else {

        return scm(l, h + high);

      }

    }

    return scm(low, high);

  };



  for (var i = min; i <= max; i += 1) {

    candidate = smallestCommon(i, candidate);

  }



  return candidate;

}



smallestCommons([5, 1]); // should return 60

smallestCommons([1, 13]); // should return 360360

smallestCommons([23, 18]); //should return 6056820

Having inner functions isn't necessarily bad. Sometimes you want to reduce some local duplication, but don't want to also create a new top-level function. Used carefully, they can clean up code.

In your particular case though, it isn't necessary to have it nested. You can just pass in the high variable as a third parameter:

function scm(l, h, high) {

  if (h % l === 0) {

     return h;

  } else {

    return scm(l, h + high, high);

  }

}



function smallestCommon (low, high) {

  return scm(low, high, high);

}

This is actually a fairly common pattern when dealing with recursion: have a recursive function, and a helper function that simplifies calling the recursive function. In functional languages where recursion is common though, it's actually commonplace to have a local recursive function like you had originally (often called something like go).

And it's a shame that JS doesn't have a range function. smallestCommons is basically just a reduction over the range [min,max]. Between the lack of range function and smallestCommon having it's arguments in the wrong order though, converting your code to use reduce unfortunately got a little bulky:

function smallestCommons(arr) {

  var max = Math.max(...arr);

  var min = Math.min(...arr);



  return Array.from(new Array(max - min), (x,i) => i + min)

              .reduce((acc, i) => smallestCommon(i, acc), max);

}

You can unnest it, if you rewrite the inner functions in such a way, that they don't reference variables in their outer scope.

function scm(l, h, step) {

  if (h % l === 0) {

     return h;

  } else {

    return scm(l, h + h, step);

  }

}



function smallestCommons(arr) {

  var max = Math.max(...arr);

  var min = Math.min(...arr);

  return scm(min, max, max);

}

It might blow your stack though, but that's a different problem. If you get a RangeError, you have to rewrite scm to be loop based instead of recursive.

I'll suggest breaking this down into smaller parts. Instead of one function that's complicated and difficult to debug, you'll have lots of functions that are easy to write and debug. Smaller functions are easier to test and reuse in other parts of your program too -

const gcd = (m, n) =>

  n === 0

    ? m

    : gcd (n, m % n)



const lcm = (m, n) =>

  Math.abs (m * n) / gcd (m, n)

  

console.log

  ( lcm (1, 5)    // 5

  , lcm (3, 4)    // 12

  , lcm (23, 18)  // 414

  )

Now we have minmax. Unique to this implementation is that it finds the min and the max using only a single traversal of the input array -

const None =

  Symbol ()



const list = (...values) =>

  values



const minmax = ([ x = None, ...rest ], then = list) =>

  x === None

    ? then (Infinity, -Infinity)

    : minmax

        ( rest

        , (min, max) =>

            then

              ( Math.min (min, x)

              , Math.max (max, x)

              )

        )



console.log

  ( minmax ([ 3, 4, 2, 5, 1 ])    // [ 1, 5 ]

  , minmax ([ 1, 5 ])             // [ 1, 5 ]

  , minmax ([ 5, 1 ])             // [ 1, 5 ]

  , minmax ([ 9 ])                // [ 9, 9 ]

  , minmax ()                   // [ Infinity, -Infinity ]

  )

By default minmax returns a list of the min and max values. We can plug the min and max directly into a range function, which might be more useful to us, as we'll see later -

const range = (m, n) =>

  m > n

    ? 

    : [ m, ... range (m + 1, n ) ]



console.log

  ( minmax ([ 3, 4, 2, 5, 1 ], range)    // [ 1, 2, 3, 4, 5 ]

  , minmax ([ 1, 5 ], range)             // [ 1, 2, 3, 4, 5 ]

  , minmax ([ 5, 1 ], range)             // [ 1, 2, 3, 4, 5 ]

  , minmax ([ 9 ], range)                // [ 9 ]

  , minmax (, range)                   // 

  )

Now that we can find the min and max of the input, create a range between the two, all that's left is calculating the lcm of the values in the range. Taking many values and reducing them to a single value is done with .reduce -

console.log

  ( minmax ([1, 5], range) .reduce (lcm, 1) // 60

  , minmax ([5, 1], range) .reduce (lcm, 1) // 60

  )

Wrap that up in a function and we're done -

const smallestCommons = xs =>

  minmax (xs, range) .reduce (lcm, 1)



console.log

  ( smallestCommons ([ 5, 1 ])    // 60

  , smallestCommons ([ 1, 13 ])   // 360360

  , smallestCommons ([ 23, 18 ])  // 6056820

  )

Verify the result in your own browser below -

const gcd = (m, n) =>

  n === 0

    ? m

    : gcd (n, m % n)



const lcm = (m, n) =>

  Math.abs (m * n) / gcd (m, n)



const None =

  Symbol ()



const list = (...values) =>

  values



const minmax = ([ x = None, ...xs ], then = list) =>

  x === None

    ? then (Infinity, -Infinity)

    : minmax

        ( xs

        , (min, max) =>

            then

              ( Math.min (min, x)

              , Math.max (max, x)

              )

        )



const range = (m, n) =>

  m > n

    ? 

    : [ m, ... range (m + 1, n ) ]



const smallestCommons = xs =>

  minmax (xs, range) .reduce (lcm, 1)



console.log

  ( smallestCommons ([ 5, 1 ])    // 60

  , smallestCommons ([ 1, 13 ])   // 360360

  , smallestCommons ([ 23, 18 ])  // 6056820

  )

extra

Above, minmax is defined using continuation passing style. We save extra computation by passing range as the specified continuation (then). However, we can call minmax without specifying a continuation and spread (...) the intermediate value to range. Either program might make more sense to you. The result is the same -

const smallestCommons = xs =>

  range (...minmax (xs)) .reduce (lcm, 1)



console.log

  ( smallestCommons ([ 5, 1 ])    // 60

  , smallestCommons ([ 1, 13 ])   // 360360

  , smallestCommons ([ 23, 18 ])  // 6056820

  )

same pig, different farm

smallestCommons is basically just a reduction over the range [min,max] - @Carcigenicate

Hopefully it helps to see the same result from multiple approaches :D

sourface

Some people will despise the above implementation of minmax regardless of its elegance and flexibility. Now that we maybe understand reducing a little better, we can show how minmax might be better implemented using direct style -

const minmax = xs =>

  xs .reduce

    ( ([ min, max ], x) =>

        [ Math.min (min, x)

        , Math.max (max, x)

        ]

    , [ Infinity, -Infinity ]

    )



const smallestCommons = xs =>

  range (...minmax (xs)) .reduce (lcm, 1) // direct style now required here