**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)) //; #fNow that you know what

does, lets look at some weird behaviourmemq(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 aBuilding 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

tests whether the key exists in the list and if it does, then it returns the list starting from thememqoccurrence of the key. But what is thefirstoccurrence 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; } fastExponent(10,3) //1000Fast exponentiation grows logarithmically Ο(

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

3. StreamsFunctional 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 likefilter,mapandreducehave 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

## One thought on “SICP Section 3.3 – 3.5 : Found a bug in memq”