Code
Diff
  • const code = String.raw`
    Y = \ f . ( \ x . f (x x) ) ( \ x . f (x x) )
    True = \ t f . t
    False = \ t f . f
    Succ = \ n s z . s (n s z)
    Pred = \ n s z . n ( \ f g . g (f s) ) (\_.z) \x.x
    Minus = \ m n . n Pred m
    Times = \ m n s . m (n s)
    isZero = \ n . n (\_.False) True
    isNotZero = \ n . n (\_.True) False
    And = \ x y . x y x
    Or = \ x . x x
    GT = \ x y . isNotZero (Minus x y)
    Mod = \ n m . ( \ r . isZero (Minus m r) 0 r ) (( \ n m . ( \ d . isZero d n (Mod d m) ) (Minus n m) ) n m)
    
    # function isPrime(n) {
    #   const trial = function trial(i) {
    #     return i * i > n || n % i != 0 && trial(i+1) ;
    #   } ;
    #   return n > 1 && trial(2) ;
    # }
    
    isPrime = \ n . ( \ trial . And (GT n 1) (trial 2) )
                    ( Y \ trial i . Or (GT (Times i i) n) (And (isNotZero (Mod n i)) (trial (Succ i))) )
    `
  • 11 const code = String.raw`
    2succ = \ n f x . f (n f x)
    3pair = \a.\b.\c.c a b
    4fst = \pair.pair (\a.\_.a)
    5snd = \pair.pair (\_.\b.b)
    6plus = \pair.\f.\x.(fst pair) f ((snd pair) f x)
    7next = \prev.pair (snd prev) (plus prev)
    8fibonacci = \n. fst (n next (pair (\_.\b.b) (succ (\_.\b.b))))
    9`
    2+Y = \ f . ( \ x . f (x x) ) ( \ x . f (x x) )
    3+True = \ t f . t
    4+False = \ t f . f
    5+Succ = \ n s z . s (n s z)
    6+Pred = \ n s z . n ( \ f g . g (f s) ) (\_.z) \x.x
    7+Minus = \ m n . n Pred m
    8+Times = \ m n s . m (n s)
    9+isZero = \ n . n (\_.False) True
    10+isNotZero = \ n . n (\_.True) False
    11+And = \ x y . x y x
    12+Or = \ x . x x
    13+GT = \ x y . isNotZero (Minus x y)
    14+Mod = \ n m . ( \ r . isZero (Minus m r) 0 r ) (( \ n m . ( \ d . isZero d n (Mod d m) ) (Minus n m) ) n m)
    1010
    11// Stress testing -- "LetRec", "BinaryScott"
    12// Testing implementation of a "String" - ie. Arrays and related functions
    13const stress = String.raw`
    14# bools
    15id = \ x . x
    16true = \ a b . a
    17false = \ a b . b
    18not = \ b . b false true
    19and = \ a b . a b false
    20or = \ a b . a true b
    21xor = \ a b . a (b false true) b
    16+# function isPrime(n) {
    17+# const trial = function trial(i) {
    18+# return i * i > n || n % i != 0 && trial(i+1) ;
    19+# } ;
    20+# return n > 1 && trial(2) ;
    21+# }
    2222
    23# ints -- z = endbit, f = offbit, t = onbit
    24zero = \ z _ _ . z
    25succ = \ n _ f t . n (t zero) t (\ m . f (succ m))
    26bool = \ n . n false (\ _ . true) (\ _ . true)
    27pred = \ n z f t . n z (\ m . t (pred m)) (\ m . bool m (f m) z)
    28odd = \ n . n false false true
    29even = \ n . not (odd n)
    30mul2 = \ n _ f _ . f n
    31addSlow = \ a b . bool b (addSlow (succ a) (pred b)) a
    32subSlow = \ a b . bool a (bool b (subSlow (pred a) (pred b)) a) (zero)
    33
    34# arrays as foldr (strings)
    23+isPrime = \ n . ( \ trial . And (GT n 1) (trial 2) )
    24+ ( Y \ trial i . Or (GT (Times i i) n) (And (isNotZero (Mod n i)) (trial (Succ i))) )
    3535 `
Test Cases
Diff
  • const chai = require("chai");
    const assert = chai.assert;
    chai.config.truncateThreshold = 0;
    
    // const LC = require("LC");
    const LC = { compile: () => compile(code), config } // Temporary. Would normally import, see line above.
    LC.config.purity = "LetRec";
    LC.config.numEncoding = "Church";
    
    const solution = LC.compile();
    const {isPrime} = solution;
    
    describe("Sample Tests", function() {
      it("Basics", function() {
        assert.equal(isPrime(0) (true)(false), false);
        assert.equal(isPrime(1) (true)(false), false);
        assert.equal(isPrime(2) (true)(false), true);
        assert.equal(isPrime(3) (true)(false), true);
        assert.equal(isPrime(4) (true)(false), false);
        assert.equal(isPrime(5) (true)(false), true);
        assert.equal(isPrime(6) (true)(false), false);
        assert.equal(isPrime(7) (true)(false), true);
        assert.equal(isPrime(8) (true)(false), false);
        assert.equal(isPrime(9) (true)(false), false);
        assert.equal(isPrime(10) (true)(false), false);
        assert.equal(isPrime(11) (true)(false), true);
        assert.equal(isPrime(12) (true)(false), false);
        assert.equal(isPrime(13) (true)(false), true);
        assert.equal(isPrime(14) (true)(false), false);
        assert.equal(isPrime(15) (true)(false), false);
        assert.equal(isPrime(16) (true)(false), false);
        assert.equal(isPrime(17) (true)(false), true);
        assert.equal(isPrime(18) (true)(false), false);
        assert.equal(isPrime(19) (true)(false), true);
      });
    });
  • 11 const chai = require("chai");
    22 const assert = chai.assert;
    33 chai.config.truncateThreshold = 0;
    44
    55 // const LC = require("LC");
    6const LC = { compile: () => compile(code), config: options } // Temporary. Would normally import, see line above.
    6+const LC = { compile: () => compile(code), config } // Temporary. Would normally import, see line above.
    77 LC.config.purity = "LetRec";
    88 LC.config.numEncoding = "Church";
    99
    1010 const solution = LC.compile();
    11const fibonacci = solution.fibonacci;
    12// const subSlow = solution.subSlow; // Uses BinaryScott
    11+const {isPrime} = solution;
    1313
    1414 describe("Sample Tests", function() {
    1515 it("Basics", function() {
    16 assert.equal(fibonacci(0), 0);
    17 assert.equal(fibonacci(1), 1);
    18 assert.equal(fibonacci(2), 1);
    19 assert.equal(fibonacci(3), 2);
    20 assert.equal(fibonacci(4), 3);
    21 assert.equal(fibonacci(5), 5);
    22 assert.equal(fibonacci(6), 8);
    23 assert.equal(fibonacci(7), 13);
    24 assert.equal(fibonacci(20), 6765);
    25// assert.equal(fibonacci(20), 6764);
    26
    27// assert.equal(subSlow(355)(56), 299)
    15+ assert.equal(isPrime(0) (true)(false), false);
    16+ assert.equal(isPrime(1) (true)(false), false);
    17+ assert.equal(isPrime(2) (true)(false), true);
    18+ assert.equal(isPrime(3) (true)(false), true);
    19+ assert.equal(isPrime(4) (true)(false), false);
    20+ assert.equal(isPrime(5) (true)(false), true);
    21+ assert.equal(isPrime(6) (true)(false), false);
    22+ assert.equal(isPrime(7) (true)(false), true);
    23+ assert.equal(isPrime(8) (true)(false), false);
    24+ assert.equal(isPrime(9) (true)(false), false);
    25+ assert.equal(isPrime(10) (true)(false), false);
    26+ assert.equal(isPrime(11) (true)(false), true);
    27+ assert.equal(isPrime(12) (true)(false), false);
    28+ assert.equal(isPrime(13) (true)(false), true);
    29+ assert.equal(isPrime(14) (true)(false), false);
    30+ assert.equal(isPrime(15) (true)(false), false);
    31+ assert.equal(isPrime(16) (true)(false), false);
    32+ assert.equal(isPrime(17) (true)(false), true);
    33+ assert.equal(isPrime(18) (true)(false), false);
    34+ assert.equal(isPrime(19) (true)(false), true);
    2828 });
    2929 });

Using the string encoding described below, define a term hello which is equivalent to "Hello, world!"

Encodings

  • purity -> Let
  • true, false -> Church encoding
  • Number -> Church encoding (only used as chars)
  • char -> a number corresponding to ascii code
  • nil -> an empty string: \ _ -> false
  • cons -> add a char to a string: \ char string b1 . b1 true (\ b2 . b2 char string)

Fixed for existing bugs. Now with number literals.

Code
Diff
  • const code = String.raw`
    # Preloaded
    
    true = \ a b . a
    false = \ a b . b
    
    pair = \ a b c . c a b
    nil = \ _ . false
    cons = \ c s . pair true (pair c s)
    
    # Code
    hello = cons 72
          ( cons 101
          ( cons 108
          ( cons 108
          ( cons 111
          ( cons 44
          ( cons 32
          ( cons 119
          ( cons 111
          ( cons 114
          ( cons 108
          ( cons 100
          ( cons 33
                 nil
          ))))))))))))
    `
  • 11 const code = String.raw`
    2# bools
    2+# Preloaded
    3+
    33 true = \ a b . a
    44 false = \ a b . b
    55
    6# numbers
    7zero = false
    8succ = \ n f x . f (n f x)
    9add = \ a b f x . a f (b f x)
    10mul = \ a b f . a (b f)
    11
    12three = \ f x . f ( f ( f x ))
    13ten = succ (mul three three)
    14thirtytwo = succ (succ (mul ten three))
    15thirtythree = succ thirtytwo
    16fortyfour = succ (add ten thirtythree)
    17seventytwo = mul (succ ( succ (add three three))) (mul three three)
    18hundred = mul ten ten
    19hundredone = succ hundred
    20hundredeight = succ (add three (add three hundredone))
    21hundredeleven = add three hundredeight
    22hundredforteen = add three hundredeleven
    23hundrednineteen = succ (succ (add three hundredforteen))
    24
    25# data
    2626 pair = \ a b c . c a b
    2727 nil = \ _ . false
    2828 cons = \ c s . pair true (pair c s)
    2929
    30# [72, 101, 108, 108, 111, 44, 32, 119, 111, 114, 108, 100, 33]
    31hello = cons seventytwo
    11+# Code
    12+hello = cons 72
    13+ ( cons 101
    14+ ( cons 108
    15+ ( cons 108
    16+ ( cons 111
    17+ ( cons 44
    18+ ( cons 32
    19+ ( cons 119
    20+ ( cons 111
    21+ ( cons 114
    22+ ( cons 108
    23+ ( cons 100
    24+ ( cons 33
    25+ nil
    26+ ))))))))))))
    4545 `

fixing bugs in the parser

  • numbers were wrapped in a spurious V
  • () was not accepted
Code
Diff
  • const code = String.raw`
    add = \ m n s z . m s (n s z)
    go = \ return a b . return b (add a b)
    K = \ x _ . x
    fibonacci = \ n . n go K 0 1
    `
  • 11 const code = String.raw`
    2succ = \ n f x . f (n f x)
    3pair = \a.\b.\c.c a b
    4fst = \pair.pair (\a.\_.a)
    5snd = \pair.pair (\_.\b.b)
    6plus = \pair.\f.\x.(fst pair) f ((snd pair) f x)
    7next = \prev.pair (snd prev) (plus prev)
    8fibonacci = \n. fst (n next (pair (\_.\b.b) (succ (\_.\b.b))))
    9`
    10
    11// Stress testing -- "LetRec", "BinaryScott"
    12// Testing implementation of a "String" - ie. Arrays and related functions
    13const stress = String.raw`
    14# bools
    15id = \ x . x
    16true = \ a b . a
    17false = \ a b . b
    18not = \ b . b false true
    19and = \ a b . a b false
    20or = \ a b . a true b
    21xor = \ a b . a (b false true) b
    22
    23# ints -- z = endbit, f = offbit, t = onbit
    24zero = \ z _ _ . z
    25succ = \ n _ f t . n (t zero) t (\ m . f (succ m))
    26bool = \ n . n false (\ _ . true) (\ _ . true)
    27pred = \ n z f t . n z (\ m . t (pred m)) (\ m . bool m (f m) z)
    28odd = \ n . n false false true
    29even = \ n . not (odd n)
    30mul2 = \ n _ f _ . f n
    31addSlow = \ a b . bool b (addSlow (succ a) (pred b)) a
    32subSlow = \ a b . bool a (bool b (subSlow (pred a) (pred b)) a) (zero)
    33
    34# arrays as foldr (strings)
    2+add = \ m n s z . m s (n s z)
    3+go = \ return a b . return b (add a b)
    4+K = \ x _ . x
    5+fibonacci = \ n . n go K 0 1
    3535 `

show decoded value in test failure message.

valueOf and decoded are defined on Function.prototype; things won't work ( for different reasons ) if not.

toInt has been removed from awaitArg; it didn't seem useful.

testing seems faster. (??) failing tests take relatively long though ( and longer than succeeding tests of the same size ). fortunately, a failing test stops the it group, so it doesn't seem a major problem.

I have tried to make awaitArg.term to print a nice lambda expression. couldn't do it.

a failed test now shows

expected { [Function: awaitArg]
  term: { name: 'f', body: { name: 'x', body: [Object] } },
  env: {},
  decoded: 6765 } to equal 6764

Updates to fromInt and toInt

Probably gives initial compile and runtime efficiency improvements, both in time and space.

I feel clever. :P

Code
Diff
  • const code = String.raw`
    succ = \ n f x . f (n f x)
    pair = \a.\b.\c.c a b
    fst = \pair.pair (\a.\_.a)
    snd = \pair.pair (\_.\b.b)
    plus = \pair.\f.\x.(fst pair) f ((snd pair) f x)
    next = \prev.pair (snd prev) (plus prev)
    fibonacci = \n. fst (n next (pair (\_.\b.b) (succ (\_.\b.b))))
    `
    
    // Stress testing -- "LetRec", "BinaryScott"
    // Testing implementation of a "String" - ie. Arrays and related functions
    const stress = String.raw`
    # bools
    id = \ x . x
    true = \ a b . a
    false = \ a b . b
    not = \ b . b false true
    and = \ a b . a b false
    or = \ a b . a true b
    xor = \ a b . a (b false true) b
    
    # ints -- z = endbit, f = offbit, t = onbit
    zero = \ z _ _ . z
    succ = \ n _ f t . n (t zero) t (\ m . f (succ m))
    bool = \ n . n false (\ _ . true) (\ _ . true)
    pred = \ n z f t . n z (\ m . t (pred m)) (\ m . bool m (f m) z)
    odd = \ n . n false false true
    even = \ n . not (odd n)
    mul2 = \ n _ f _ . f n
    addSlow = \ a b . bool b (addSlow (succ a) (pred b)) a
    subSlow = \ a b . bool a (bool b (subSlow (pred a) (pred b)) a) (zero)
    
    # arrays as foldr (strings)
    `
  • 11 const code = String.raw`
    22 succ = \ n f x . f (n f x)
    33 pair = \a.\b.\c.c a b
    44 fst = \pair.pair (\a.\_.a)
    55 snd = \pair.pair (\_.\b.b)
    66 plus = \pair.\f.\x.(fst pair) f ((snd pair) f x)
    77 next = \prev.pair (snd prev) (plus prev)
    88 fibonacci = \n. fst (n next (pair (\_.\b.b) (succ (\_.\b.b))))
    99 `
    1010
    1111 // Stress testing -- "LetRec", "BinaryScott"
    1212 // Testing implementation of a "String" - ie. Arrays and related functions
    1313 const stress = String.raw`
    1414 # bools
    1515 id = \ x . x
    1616 true = \ a b . a
    1717 false = \ a b . b
    1818 not = \ b . b false true
    1919 and = \ a b . a b false
    2020 or = \ a b . a true b
    2121 xor = \ a b . a (b false true) b
    2222
    2323 # ints -- z = endbit, f = offbit, t = onbit
    2424 zero = \ z _ _ . z
    2525 succ = \ n _ f t . n (t zero) t (\ m . f (succ m))
    2626 bool = \ n . n false (\ _ . true) (\ _ . true)
    2727 pred = \ n z f t . n z (\ m . t (pred m)) (\ m . bool m (f m) z)
    2828 odd = \ n . n false false true
    2929 even = \ n . not (odd n)
    3030 mul2 = \ n _ f _ . f n
    3131 addSlow = \ a b . bool b (addSlow (succ a) (pred b)) a
    3232 subSlow = \ a b . bool a (bool b (subSlow (pred a) (pred b)) a) (zero)
    3333
    3434 # arrays as foldr (strings)
    3535 `

compile development

  • better error messages ( where possible )
  • compiling immediate numbers ( when appropriate )
Code
Diff
  • const code = String.raw`
    succ = \ n f x . f (n f x)
    pair = \a.\b.\c.c a b
    fst = \pair.pair (\a.\_.a)
    snd = \pair.pair (\_.\b.b)
    plus = \pair.\f.\x.(fst pair) f ((snd pair) f x)
    next = \prev.pair (snd prev) (plus prev)
    fibonacci = \n. fst (n next (pair (\_.\b.b) (succ (\_.\b.b))))
    `
  • 11 const code = String.raw`
    2succ = \n f x. f (n f x)
    2+succ = \ n f x . f (n f x)
    33 pair = \a.\b.\c.c a b
    44 fst = \pair.pair (\a.\_.a)
    55 snd = \pair.pair (\_.\b.b)
    66 plus = \pair.\f.\x.(fst pair) f ((snd pair) f x)
    77 next = \prev.pair (snd prev) (plus prev)
    88 fibonacci = \n. fst (n next (pair (\_.\b.b) (succ (\_.\b.b))))
    99 `
Test Cases
Diff
  • const chai = require("chai");
    const assert = chai.assert;
    chai.config.truncateThreshold = 0;
    
    // const LC = require("LC");
    const LC = { compile: () => compile(code), config: Options } // Temporary. Would normally import, see line above.
    LC.config.Purity = "LetRec";
    LC.config.NumEncoding = "Church";
    
    const solution = LC.compile();
    const fibonacci = solution.fibonacci;
    
    describe("Sample Tests", function() {
      it("Basics", function() {
        assert.equal(fibonacci(0), 0);
        assert.equal(fibonacci(1), 1);
        assert.equal(fibonacci(2), 1);
        assert.equal(fibonacci(3), 2);
        assert.equal(fibonacci(4), 3);
        assert.equal(fibonacci(5), 5);
        assert.equal(fibonacci(6), 8);
        assert.equal(fibonacci(7), 13);
        assert.equal(fibonacci(20), 6765);
        // assert.equal(fibonacci(20), 6764);
      });
    });
  • 11 const chai = require("chai");
    22 const assert = chai.assert;
    33 chai.config.truncateThreshold = 0;
    44
    55 // const LC = require("LC");
    6const LC = { compile: ()=>compile(code), config: Options } // Temporary. Would normally import, see line above.
    6+const LC = { compile: () => compile(code), config: Options } // Temporary. Would normally import, see line above.
    77 LC.config.Purity = "LetRec";
    88 LC.config.NumEncoding = "Church";
    99
    1010 const solution = LC.compile();
    1111 const fibonacci = solution.fibonacci;
    1212
    1818 assert.equal(fibonacci(3), 2);
    1919 assert.equal(fibonacci(4), 3);
    2020 assert.equal(fibonacci(5), 5);
    2121 assert.equal(fibonacci(6), 8);
    2222 assert.equal(fibonacci(7), 13);
    23+ assert.equal(fibonacci(20), 6765);
    24+ // assert.equal(fibonacci(20), 6764);
    2323 });
    2424 });

compile development

  • better error messages ( where possible )
  • compiling immediate numbers ( when appropriate )
Code
Diff
  • const code = String.raw`
    succ = \n f x. f (n f x)
    pair = \a.\b.\c.c a b
    fst = \pair.pair (\a.\_.a)
    snd = \pair.pair (\_.\b.b)
    plus = \pair.\f.\x.(fst pair) f ((snd pair) f x)
    next = \prev.pair (snd prev) (plus prev)
    fibonacci = \n. fst (n next (pair (\_.\b.b) (succ (\_.\b.b))))
    `
  • 1const text = String.raw`
    1+const code = String.raw`
    22 succ = \n f x. f (n f x)
    33 pair = \a.\b.\c.c a b
    44 fst = \pair.pair (\a.\_.a)
    55 snd = \pair.pair (\_.\b.b)
    66 plus = \pair.\f.\x.(fst pair) f ((snd pair) f x)
    77 next = \prev.pair (snd prev) (plus prev)
    8fib = \n. fst (n next (pair (\_.\b.b) (succ (\_.\b.b))))
    9`
    10
    11// Proof of laziness -- using Scott
    12const lazy = String.raw`
    13succ = \ n _ f . f n
    14inf_list = \ n b . b n (inf_list (succ n))
    15counter = inf_list 0
    16`
    17
    18// Stress testing -- "LetRec", "BinaryScott"
    19// Testing implementation of a "String" - ie. Arrays and related functions
    20const stress = String.raw`
    21# bools
    22true = \ a b . a
    23false = \ a b . b
    24not = \ b . b false true
    25and = \ a b . a b false
    26or = \ a b . a true b
    27xor = \ a b . a (b false true) b
    28
    29# ints -- z = endbit, f = offbit, t = onbit
    30zero = \ z _ _ . z
    31succ = \ n _ f t . n (t zero) t (\ m . f (succ m))
    32pred = \ n z f t . n z (\ m . t (pred m)) f
    33bool = \ n . n false (\ _ . true) (\ _ . true)
    34odd = \ n . n false false true
    35even = \ n . not (odd n)
    36mul2 = \ n _ f _ . f n
    37addSlow = \ a b . bool b (addSlow (succ a) (pred b)) a
    38subSlow = \ a b . bool a (bool b (subSlow (pred a) (pred b)) a) (zero)
    39
    40# arrays as foldr (strings)
    8+fibonacci = \n. fst (n next (pair (\_.\b.b) (succ (\_.\b.b))))
    4141 `
Test Cases
Diff
  • const chai = require("chai");
    const assert = chai.assert;
    chai.config.truncateThreshold = 0;
    
    // const LC = require("LC");
    const LC = { compile: ()=>compile(code), config: Options } // Temporary. Would normally import, see line above.
    LC.config.Purity = "LetRec";
    LC.config.NumEncoding = "Church";
    
    const solution = LC.compile();
    const fibonacci = solution.fibonacci;
    
    describe("Sample Tests", function() {
      it("Basics", function() {
        assert.equal(fibonacci(0), 0);
        assert.equal(fibonacci(1), 1);
        assert.equal(fibonacci(2), 1);
        assert.equal(fibonacci(3), 2);
        assert.equal(fibonacci(4), 3);
        assert.equal(fibonacci(5), 5);
        assert.equal(fibonacci(6), 8);
        assert.equal(fibonacci(7), 13);
      });
    });
  • 11 const chai = require("chai");
    22 const assert = chai.assert;
    33 chai.config.truncateThreshold = 0;
    44
    55 // const LC = require("LC");
    6const LC = {compile: ()=>compile(stress), config: Options} // Temporary. Would normally import, see line above.
    6+const LC = { compile: ()=>compile(code), config: Options } // Temporary. Would normally import, see line above.
    77 LC.config.Purity = "LetRec";
    8LC.config.NumEncoding = "BinaryScott"
    8+LC.config.NumEncoding = "Church";
    99
    10const solution = LC.compile(); // Will compile preloaded.txt + '\n' + solution.txt
    11
    12// This line does nothing at the moment. Just seeing how it looks.
    13// The idea is that for "int" and "bool" types, we could implicitely convert
    14// on input and output, allowing for very *normal* looking equations.
    15// solution.fibonacci.type = "int -> int -> int"; // Types = int | bool | term ?
    16// const fibonacci = solution.fibonacci;
    17
    18const T = new L('a', new L('b', new V('a')));
    19const F = new L('a', new L('b', new V('b')));
    10+const solution = LC.compile();
    11+const fibonacci = solution.fibonacci;
    2020
    2121 describe("Sample Tests", function() {
    2222 it("Basics", function() {
    23
    24/* Fib Tests
    25 assert.deepEqual(fibonacci(7), 13) <- How a basic function might look, with type signature.
    26
    27 Accessing a term does an implicite evalLC call on that term (or returns a term which was already evaluated previously)
    15+ assert.equal(fibonacci(0), 0);
    16+ assert.equal(fibonacci(1), 1);
    17+ assert.equal(fibonacci(2), 1);
    18+ assert.equal(fibonacci(3), 2);
    19+ assert.equal(fibonacci(4), 3);
    20+ assert.equal(fibonacci(5), 5);
    21+ assert.equal(fibonacci(6), 8);
    22+ assert.equal(fibonacci(7), 13);
    5454 });
    5555 });
Arrays
Code
Diff
  • function remove (arr, n) {
      if ( n >= 0 )
        arr.splice(n, 1);
      return arr;
    }
  • 11 function remove (arr, n) {
    2 if (n < 0 || n >= arr.length) return arr;
    3 arr.splice(n, 1);
    2+ if ( n >= 0 )
    3+ arr.splice(n, 1);
    44 return arr;
    55 }

fib is O(n²) in practice, probably because of BigInt arithmetic.

There is also an optimisation calculating fib(n) in terms of fib(approx half n), which is actually logarithmic before BigInt arithmetic. That's even faster, in this case.

Code
Diff
  • function fib(n) {
      for ( let [a,b]=[0n,1n], i=0;; i++ )
        if ( i<n )
          [a,b] = [b,a+b];
        else
          return a;
    }
  • 1module Example where
    2
    3import Data.Semigroup (Endo(..),stimes)
    4
    5fib :: Integer -> Integer
    6fib = fst . (`appEndo` (0,1)) . (`stimes` Endo ( \ (a,b) -> (b,a+b) ))
    1+function fib(n) {
    2+ for ( let [a,b]=[0n,1n], i=0;; i++ )
    3+ if ( i<n )
    4+ [a,b] = [b,a+b];
    5+ else
    6+ return a;
    7+}
Code
Diff
  • module Example where
    
    import Data.Semigroup (Endo(..),stimes)
    
    fib :: Integer -> Integer
    fib = fst . (`appEndo` (0,1)) . (`stimes` Endo ( \ (a,b) -> (b,a+b) ))
  • 11 module Example where
    22
    33 import Data.Semigroup (Endo(..),stimes)
    44
    55 fib :: Integer -> Integer
    6fib n = fst $ n `stimes` Endo ( \ (a,b) -> (b,a+b) ) `appEndo` (0,1)
    6+fib = fst . (`appEndo` (0,1)) . (`stimes` Endo ( \ (a,b) -> (b,a+b) ))

Endo wraps a function; appEndo unwraps it.

stimes composes a wrapped function with itself n times. It is optimised to take O(log n) time.

module Example where

import Data.Semigroup (Endo(..),stimes)

fib :: Integer -> Integer
fib n = fst $ n `stimes` Endo ( \ (a,b) -> (b,a+b) ) `appEndo` (0,1)
Code
Diff
  • public static class ReverseFactorial  {
      public static int Kata(long n) {
        long i = 1;
        while ( n > 1 ) n /= i += 1 ;
        return (int) i;
      }
    }
  • 1using System;
    2
    3 public static class ReverseFactorial
    4 {
    5 public static int Kata(long n)
    6 {
    7 if(n == 0) return 1;
    8 for (long i = 2; n / i > 1; i++)
    9 {
    10 n /= i;
    11 }
    12 return (int) n;
    13 }
    14 }
    1+public static class ReverseFactorial {
    2+ public static int Kata(long n) {
    3+ long i = 1;
    4+ while ( n > 1 ) n /= i += 1 ;
    5+ return (int) i;
    6+ }
    7+}

custom.map and custom.filter should return custom arrays, not ordinary ones.

wrapper can be used for random tests as well.

Code
Diff
  • // this code should fail the tests // it does
    
    function totalAgeYoungerThan0(people, age) {
      let totalAge = 0;
      for ( let i=0; i in people; i++ ) // this will just always return 0 with the arguments we send
        if ( people[i].age < age )
          totalAge += people[i].age;
      return totalAge;
    }
    
    // this code should fail the tests // it does
    
    function totalAgeYoungerThan1(people,tooOld) {
      let totalAge = 0;
      for ( const {age} of people ) // this will throw because our argument isn't iterable
        if ( age < tooOld )
          totalAge += age;
      return totalAge;
    }
    
    // this code should fail the tests // it does
    
    function totalAgeYoungerThan2(xs, age) {
      const [person,...persons] = xs; // this will throw on not iterable
      if ( person===undefined )
        return 0;
      else if ( person.age < age )
        return totalAgeYoungerThan2(persons,age) + person.age;
      else
        return totalAgeYoungerThan2(persons,age);
    }
    
    // this code should theoretically pass the tests // it does
    // it includes the word `for` but not in a for loop
    
    function totalAgeYoungerThan3(people, age) {
      return people
        .filter(person => person.age < age)
        .reduce((formula, person) => formula + person.age, 0)
    }
    
    // passes
    
    function totalAgeYoungerThan4(people, age) {
      return people
        .filter(person => person.age < age)
        .reduce((sum, person) => sum + person.age, 0)
    }
    
    // passes
    
    const get = i => o => o[i] ;
    const lt = x => y => y < x ;
    const plus = (x,y) => y+x ;
    
    function totalAgeYoungerThan5(people,age) {
      return people.map(get("age"))
                   .filter(lt(age))
                   .reduce(plus,0)
                   ;
    }
  • 4343
    4444 function totalAgeYoungerThan4(people, age) {
    4545 return people
    4646 .filter(person => person.age < age)
    4747 .reduce((sum, person) => sum + person.age, 0)
    4848 }
    49+
    50+// passes
    51+
    52+const get = i => o => o[i] ;
    53+const lt = x => y => y < x ;
    54+const plus = (x,y) => y+x ;
    55+
    56+function totalAgeYoungerThan5(people,age) {
    57+ return people.map(get("age"))
    58+ .filter(lt(age))
    59+ .reduce(plus,0)
    60+ ;
    61+}
Loading more items...