Search code examples
javascriptlambda-calculusturing-machinesdeclarativecomputability

What is the most concise way to generate strings of language anbncn using JavaScript without using loops?


To convey the merits of Lambda Calculus, and even JavaScript's ability to implement such (Turing-complete) formulas, I'd like to see the most elegant and concise way that one JS file could print the correct string of the following language, given a natural number n (zero-based):

anbncn

This would also mean without the use of external libraries, nor iterative machinery (e.g. "while", "for", etc.).

anbn , for example, being a context-free grammar perhaps can get no simpler than:

function print(n) {if(n>0) {console.log('a'); print(n--); console.log('b');}}


Solution

  • Since you're OK with recursion in your example,

    function print(n) {
      printA(n);
      printB(n);
      printC(n);
    }
    
    function printA(n) {
      if (n > 0) {
        console.log('a');
      }
      printA(n - 1);
    }
    
    // with printB and printC implemented similarly.
    

    If that's not as appealing, you could roll the three printX functions together in a manner like this:

    function printABC(n) {
      print(n,3*n);
    }
    
    function print(division, current) {
      if (current > 0) {
        if (current < division) {
          console.log('c');
        }
        else if (current < division * 2) {
          console.log('b');
        }
        else {
          console.log('a');
        }
        print(division, current - 1);
      }
    }
    

    Give or take some off-by-ones with < vs <=.