Q1. Big Picture

Functional languages try to avoid mutable state for several reasons. One is that a program's correctness is easier to verify when the program has minimal state. Another is that the program can be optimized better by the compiler / interpreter executing the code; for example, any call can be replaced with its resulting return value if the function has no side effects, and any two lists with the same elements can refer to the same list if the lists are immutable. Another is that the program can often be parallelized more easily if it has no mutation. Another is that it leads to robust programs that are less easily damaged by effects caused in a different part of the program.



Q2. ML Functions

fun range([]) = 0
|   range([x]) = 1                (* unnecessary but OK *)
|   range(L as first::rest) =
        let
            fun minMax([], min, max) = max - min + 1        (* or if/else instead of Int.min/max *)
            |   minMax(head::tail, min, max) =
                    minMax(tail, Int.min(min, head), Int.max(max, head))
        in
            minMax(rest, first, first)
        end;



Q3. ML Currying/Composition

val acronym = implode o List.filter Char.isUpper o map (hd o explode);

val acronym = (reducex op ^) o (map Char.toString) o (List.filter Char.isUpper) o (map (hd o explode));



[edit] Q4. Scheme Expressions

a)
(define x 1)
(define y 2)
(define z 7)
(let ((z (+ x y z)))
  (let* ((x (+ y z))
         (y (+ x z)))
    (list x y z)))                     ; ANSWER:  (12 22 10)

b)
(define x 1)
(define y 2)
(define (f n) (+ x y n))
(set! y 3)
(define a (f y))
(define c x)
(define x 4)
(define b (let ((a 5)) (f a)))
(list a b c x y)                       ; ANSWER:  (7 12 1 4 3)

c)
(define a 4)
(define b 5)
(define c 6)
(define L1 '(a b))
(define L2 (cons a b))
(define L3 (list a b))
(list (+ a b c)
      (eq? (length L1) (length L3))
      (equal? (car L1) (car L2))
      (eqv? (cdr L2) (cdr L3))
      (equal? (cdr L2) (cadr L3)))     ; ANSWER:  (15 #t #f #f #t)



Q5. Scheme Procedures

(define (is-sorted lst)
  (cond ((null? lst) #t)
        ((null? (cdr lst)) #t)
        (else (and (<= (car lst) (cadr lst)) (is-sorted (cdr lst))))))

; solution #2, not zen
(define (is-sorted lst)
  (cond ((null? lst) #t)
        ((null? (cdr lst)) #t)
        ((and (<= (car lst) (cadr lst)) (is-sorted (cdr lst))) #t)
        (else #f)))

; solution #3, "I don't know how to use cond"
(define (is-sorted lst)
  (if (or (null? lst) (null? (cdr lst))) #t
      (if (> (car lst) (cadr lst)) #f
          (is-sorted (cdr lst)))))

; solution #4, "I DO know how to use cond"
(define (is-sorted lst)
  (cond ((or (null? lst) (null? (cdr lst))) #t)
        ((> (car lst) (cadr lst)) #f)
        (else (is-sorted (cdr lst)))))

; BAD... makes more than one pass over the list!  not full credit
(define (is-sorted lst)
  (cond ((null? lst) #t)
        ((= 1 (length lst)) #t)   ; <- here!
        (else (and (<= (car lst) (cadr lst)) (is-sorted (cdr lst))))))



Q6. Scheme Procedures

; standard solution
(define (merge lst1 lst2)
  (cond ((null? lst1) lst2)
        ((null? lst2) lst1)
        ((< (car lst1) (car lst2))
              (cons (car lst1) (merge (cdr lst1) lst2)))
        (else (cons (car lst2) (merge (cdr lst2) lst1)))))

; "doesn't stop when one list is empty" ... still works
(define (merge lst1 lst2)
  (cond ((and (null? lst1) (null? lst2)) null)   ; or '()
        ((null? lst1) (cons (car lst2) (merge lst1 (cdr lst2))))
        ((null? lst2) (cons (car lst1) (merge lst2 (cdr lst1))))
        ((< (car lst1) (car lst2))
              (cons (car lst1) (merge (cdr lst1) lst2)))
        (else (cons (car lst2) (merge (cdr lst2) lst1)))))

; using let (local variables)
(define (merge2 lst1 lst2)
  (cond ((empty? lst1) lst2)
        ((empty? lst2) lst1)
        (else (let* ((first1 (car lst1))
                     (first2 (car lst2))
                     (less (< first1 first2))
                     (chosen-element (if less first1 first2))
                     (new-lst1 (if less (cdr lst1) lst1))
                     (new-lst2 (if less lst2 (cdr lst2))))
                (cons chosen-element (merge new-lst1 new-lst2))))))

; "swap order of params and try again"
(define (merge lst1 lst2)
  (cond ((null? lst1) lst2)
        ((null? lst2) lst1)
        ((< (car lst1) (car lst2))
              (cons (car lst1) (merge (cdr lst1) lst2)))
        (else (merge lst2 lst1))))  ; <- HERE! swap them



Q7. Scheme Procedures

; focuses on level first, then on element type
(define (level-sum lst level)
  (cond ((null? lst) 0)
        ((< level 0) 0)
        (else
         (let* ((first (car lst))
                (rest  (cdr lst))
                (first-sum            ; contribution to sum by first element
                 (if (= 0 level)
                     ; level 0: only numbers matter
                     (if (number? first) first 0)
                     
                     ; level > 0: only lists matter
                     (if (list? first) (level-sum first (- level 1)) 0))))
           ; in
           (+ first-sum (level-sum rest level))))))
  
; focuses on element type first, then on level
(define (level-sum L n)
  (cond ((null? L) 0)
        ((< n 0) 0)
        ((number? (car L))
         (+ (if (= n 0) (car L) 0) (level-sum (cdr L) n)))
        (else   ; car L is a list
         (+ (level-sum (car L) (- n 1)) (level-sum (cdr L) n)))))

(define (level-sum L n)
  (cond ((null? L) 0)
        ((< n 0) 0)
        ((list? (car L))
         (+ (level-sum (car L) (- n 1)) (level-sum (cdr L) n)))
        ((= n 0) (+ (car L) (level-sum (cdr L) n)))
        (else
         (level-sum (cdr L) n))))

(define (level-sum L level)
  (cond ((null? L) 0)
        ((= 0 level) (foldl + 0 (filter number? L)))
        (else (level-sum (foldl append '() (filter list? L)) (- level 1)))))

;        this does not work above:
;        (else (level-sum (filter list? L) (- level 1)))))

(define (level-sum L n)
  (cond ((empty? L) 0)
        ((equal? 0 n)
         ; level 0 - process numbers, skip over lists
         (if (list? (car L))
             (level-sum (cdr L) n)                ; skip over list
             (+ (car L) (level-sum (cdr L) n))))  ; handle number
        ; level > 0 - process lists, skip over numbers
        ((list? (car L))
         (+ (level-sum (car L) (- n 1))
            (level-sum (cdr L) n)))               ; handle list
        (else (level-sum (cdr L) n))))            ; skip over number

; helper that counts up instead of down
(define (level-sum L n)
  (define (sum a curr)
    (cond ((null? a) 0)
          ((and (= curr n) (number? (car a))
                (+ (car a) (sum (cdr a) curr))))
          ((list? (car a))
           (+ (sum (car a) (+ curr 1)) (sum (cdr a) curr)))
          (else (sum (cdr a) curr))))
  (sum L 0))

; higher-order solution
(define (level-sum L level)
  (cond ((null? L) 0)
        ((= 0 level) (foldr + 0 (filter number? L)))
        (else (foldr + 0 (map (lambda (item) (level-sum item (- level 1)))
                              (filter list? L))))))

; higher-order plus lambda
(define (level-sum lst n)
  (foldl + 0
         (map (lambda (v) 
                (cond ((and (equal? n 0) (number? v)) v)
                      ((list? v) (level-sum v (- n 1)))
                      (else 0))) lst)))

; recursion down to the individual numbers
(define (level-sum L n)
  (cond ((< n 0) 0)
        ((null? L) 0)
        ((number? L) (if (= n 0) L 0))
        ((= n 0) (foldl + 0 (filter number? L)))
        (else (foldl + 0 (map (lambda (x) (level-sum x (- n 1))) L)))))



Q8. Scheme Streams

; 1  3  6  10  15  21  28  36
;  +2 +3 +4  +5  +6  +7  +8
(define (triangular)
  (define (helper i incr)
    (cons i (lambda () (helper (+ i incr) (+ incr 1)))))
  (helper 1 2))

; same as first but reversed order of args
(define (triangular)
  (define (helper a b)
    (cons b (lambda () (helper (+ a 1) (+ a b)))))
  (helper 2 1))

; same as first solution but adds 1 inside helper first parameter
(define (triangular)
  (define (helper x n)
    (cons x (lambda () (helper (+ x n 1) (+ n 1)))))
  (helper 1 1))

; starts at 1/0 instead of 2/1
(define (triangular)
  (define (helper i sum)
    (cons (+ i sum) (lambda () (helper (+ i 1) (+ sum i)))))
  (helper 1 0))



Q9. JavaScript Expressions

(a)  a.length                                  // 3
(b)  b === (parseInt("5 hi") - "3")	       // true
(c)  typeof(a) + typeof(c)                     // "objectobject"
(d)  c.a + c.b                                 // "2c"
(e)  a.map(function(x) {return x.length;})     // [2, 3, 1]



Q10. JavaScript Functions

// typical solution that builds up the result array
Array.prototype.without = function() {
    var result = [];
    for (var i = 0; i < this.length; i++) {
        var found = false;
        for (var j = 0; j < arguments.length; j++) {
            if (this[i] === arguments[j]) {
                found = true;
                break;
            }
        }
        
        if (!found) {
            result.push(this[i]);
        }
    }
    
    return result;
};

// "leet haxor one-liner using filter" solution
Array.prototype.without = function() {
    var args = [].concat(arguments);
    return this.filter(function(x) { return args.indexOf(x) < 0; });
};

Array.prototype.without = function() {
    // make a copy of this array    
    var result = [];
    for (var i = 0; i < this.length; i++) {
        result[i] = this[i];
    }
    
    // look for each element from arguments; if found, shift left
    for (var i = 0; i < arguments.length; i++) {
        for (var j = 0; j < result.length; j++) {
            if (result[j] === arguments[i]) {
                // remove it by shifting left
                for (var k = j; k < result.length; k++) {
                    result[k] = result[k + 1];
                }
                result.length -= 1;
                j--;
            }
        }
    }
    return result;
};

Array.prototype.without = function() {
	var temp = this;
	var arg = arguments;
	for (var i = 0; i < arg.length; i++) {
		temp = temp.filter(function(x) {return x !== arg[i];});
		print(temp);
	}
	return temp;
}



Q11. JavaScript Regular Expressions

// \d and three-groups-of-digits solution
String.prototype.isIpAddress = function() {
    return !!this.match(/^(\d{1,3}\.){3}\d{1,3}$/);
};

// [0-9] solution
String.prototype.isIpAddress = function() {
    return this.match(/^[0-9]{1,3}\.[0-9]{1,3}\.[0-9]{1,3}\.[0-9]{1,3}$/);
};

// "I don't remember the {1,3} notation" solution
String.prototype.isIpAddress = function() {
    return this.match(/^[0-9][0-9]?[0-9]?\.[0-9][0-9]?[0-9]?\.[0-9][0-9]?[0-9]?\.[0-9][0-9]?[0-9]?$/);
};



Q12. JavaScript Functions

Array.prototype.flatten = function() {
    var result = [];
    for (var i = 0; i < this.length; i++) {
        if (typeof(this[i]) === "object" && 
                typeof(this[i].length) !== "undefined") {
            result = result.concat(this[i].flatten());
        } else {
            result.push(this[i]);
        }
    }
    return result;
};

Array.prototype.flatten = function() {
    var result = [];
    for (var i = 0; i < this.length; i++) {
        if (typeof(this[i]) === "object" && this[i].length !== undefined) {
            var flat = this[i].flatten();
            for (var j = 0; j < flat.length; j++) {
                result.push(flat[j]);
            }
        } else {
            result.push(this[i]);
        }
    }
    return result;
};

Array.prototype.flatten = function() {
    var result = [];
    function helper(element) {
        if (element instanceof Array && element.length !== undefined) {
            for (var i = 0; i < element.length; i++) {
                helper(element[i]);
            }
        } else {
            result[result.length] = element;
        }
    }
    
    helper(this);
    return result;
};

Array.prototype.flatten = function() {
    var result = [];
    function helper(element) {
        if (element instanceof Array && element.length !== undefined) {
            for (var i = 0; i < element.length; i++) {
                helper(element[i]);
            }
        } else {
            result[result.length] = element;
        }
    }
    
    helper(this);
    return result;
};

Array.prototype.flatten = function() {
    var result = [];
    function help(n) {
        if (typeof(n) == "object" && typeof(n.length) != "undefined") {
            if (n.length > 0) {
                n.map(help);     // or forEach
            }
        } else {
            result.push(n);
        }
    }
    
    help(this);
    return result;
};

Array.prototype.flatten = function() {
    var y = [];
    function flat(x) {
        x.forEach(function(z) {
            if (typeof(z) === "object" && typeof(z.length) === "number") {
                flat(z);
            } else {
                y.push(z);
            }
        });
    }
    
    flat(this);
    return y;
};

Array.prototype.flatten = function() {
    if (this.length === 0) {
        return [];
    } else if (this[0].length !== undefined) {
        return this[0].flatten().concat(this.slice(1, this.length).flatten());
    } else {
        return [this[0]].concat(this.slice(1, this.length).flatten());
    }
};