Friday, March 25, 2016

left-pad

In the wake of an epic ragequit where Azer Koçulu removed all of his modules from npm (the node.js package manager), there have been so many entertaining discussions and explanations covering what happened.

Today, Programming Praxis posted the leftpad challenge, pointing out that the original solution ran in quadratic time due to it's use of character-by-character string concatenation (but not pointing out that it only works with strings).

First, the original code in Javascript:

function leftpad (str, len, ch) {
  str = String(str);
  var i = -1;
  if (!ch && ch !== 0) ch = ' ';
  len = len - str.length;
  while (++i < len) {
    str = ch + str;
  }
  return str;
}

Now, a (simpler? faster? more general?) version in Factor:

:: left-pad ( seq n elt -- newseq )
    seq n seq length [-] elt <repetition> prepend ;

Using it, you can see it works:

IN: scratchpad "hello" 3 CHAR: h left-pad .
"hello"

IN: scratchpad "hello" 10 CHAR: h left-pad .
"hhhhhhello"

And it even works with other types of sequences:

IN: scratchpad { 1 2 3 } 3 0 left-pad .
{ 1 2 3 }

IN: scratchpad { 1 2 3 } 10 0 left-pad .
{ 0 0 0 0 0 0 0 1 2 3 }

I should also point out that Factor has pad-head that does this in the standard library and node.js has a pad-left module that solves the quadratic time problem (but still only works with strings).

No comments: