**1. Is memq broken?**

memq is an in-built list search function; it finds the first occurrence of a key in a list and returns a new list starting from that key.

(memq 3 (list 1 2 3 4)) //; '(3 4) (memq 5 (list 1 2 3 4)) //; #f

Now that you know what ** memq **does, lets look at some weird behaviour

(define x (list 1 2)) (define a (list 3 4)) //; append x to the list (set! a (append a x)) (memq x a) //; #f -> x is not in a

Building on that foundation leads to the following conundrum

(define x '(1 2 3)) //; Create a cycle: last element of x is itself (set-cdr! x x) //; is x in x? (memq x x) //; never-ending loop

* memq* tests whether the key exists in the list and if it does, then it returns the list starting from the

*occurrence of the key. But what is the*

**first***occurrence in a cyclic list? Could this be the bug?*

**first****2. Algorithms, algorithms**

**Horner’s algorithm**

This is useful for calculating polynomial values at discrete points; for example, given a polynomial function, f(x) = 7x³ + 4x² + 4; what is f(3)? A potential application (and possible interview question too) is to convert string values into numbers – 1234 is the value of x³ + 2x² + 3x + 4 when x is 10.

//assuming polynomial is represented from lowest power to highest //i.e. 1234 -> [4, 3, 2, 1] function horner (poly, base) { if(base === 0) { return 0; } var val = 0; var polyLen = poly.length; for(var i = 0; i < polyLen; i++ ) { val += poly[i] * Math.pow(base, i); } return val; } horner([4,3,2,1], 10); //1234

**Fast exponentiation**

Because going twice as fast is more fun than going fast.

function exponent (base, power) { var val = 1; while(power > 0) { val = val * base; power = power - 1; } return val; }

Now, lets look at fast exponentiation.

function fastExponent(base, power) { if(power === 1) { return base; } //handle odd powers if((power % 2) === 1) { return base * fastExponent(base, (power - 1)); } var part = fastExponent(base, (power / 2)); return part * part; //square of part also works } fastExponent(10,3) //1000

Fast exponentiation grows logarithmically Ο(*log N*) while the normal one is Ο(*N*). This same concept can be reapplied to similar scenarios.

**3. Streams**

Functional programming offers many advantages but one potential downside is performance and needless calculation. For example, while imperative programming offers quick exit constructs (e.g. *break, continue)*; functional programming constructs like *filter*, *map *and *reduce *have no such corollary – the entire list has to be processed even if only the first few items are needed.

Streams offer an elegant solution to this issue by performing only just-in-time computations. Data is lazily evaluated and this makes it possible to easily (and beautifully) represent infinite lists. Inshaaha Allaah I should explain this concept in an upcoming post. It’s very beautiful and elegant and powerful.

**Related Posts on my SICP adventures**

[…] it’s quite easy to get into a non-ending loop. I once ran into a similar issue with memq in the […]

LikeLike