• Due: 11:59pm Monday, February 29. This is a hard deadline (to give you sufficient time to work on your take-home exam 1, which will be posted that day and due on Monday March 7.)

  • Notes:

    • The problems needn’t be done in order. Feel free to jump around.
    • The problem set is worth 130 points.
    • We’re asking you to keep track of the time estimates for each problem/subproblem.
  • Submission:
    • Write all your Racket code in a single file yourAccountName-ps4.rkt and all your Python code in a single file yourAccountName-ps4.py
    • In the yourFullName CS251 Spring 2016 Folder that you created for PS1, create a Google Doc named yourFullName CS251 PS4.
    • For each problem and subproblem, please indicate at the beginning of each writeup approximately how long that problem took you to solve and write up.
    • Include all answers, including copies of code from your .rkt and .py files in your PS4 google doc. Please format your simplifications Problem 1b so that they’re easy to read. Format the derivation using the fixed-width Courier New font (can use a small font size if that helps).
    • Drop copies of your yourAccountName-ps4.rkt and yourAccountName-ps4.py files in your ~/cs251/drop/ps04 drop folder on cs.wellesley.edu.

1. Simplifying Inside Lambdas (15 points)

The small-step evaluation rules we have studied do not perform any evaluation of subexpressions inside the body of a lambda expression. The body is only ``opened up’’ for evaluation when the lambda expression is applied to argument values, at which point the argument values are substituted for the parameters in the body, and evaluation of the body proceeds.

However, it is possible to perform limited simplification of subexpressions inside the body of a lambda expression for purposes of optimization. Such simplifications can also make the body of a lambda expression easier to understand.

For example, consider the expression

(λ (w) 
  ((λ (x y) (+ (* x x) (* y y)))
   (+ 1 2) w))

According to our small-step evaluation rules, this is a value, and cannot be reduced more.

However, there are simplifications inside (λ (w) ...) we can perform that will not change its meaning:

  • We can simplify (+ 1 2) to 3. Performing an operation on two operand values within a function body is called constant folding. This yields the simplified expression:

    (λ (w) 
  ((λ (x y) (+ (* x x) (* y y)))
   3 w))

  • We can apply the function (λ (x y) ...) to the values 3 and w, where for the purposes of simplification we will extend the set of values to include identifiers (w in this case). This yields the simplified expression. We’ll call this simplification value propagation.

    (λ (w) (+ (* 3 3) (* w w)))

  • Finally we can perform one more constant folding step to yield

    (λ (w) (+ 9 (* w w)))

    This final lambda expression is much easier to understand than the original. Furthermore, the simplification steps we have performed avoid evaluation steps that would otherwise need to be performed later, so the simplification steps are actually optimizations that can improve the efficiency of the function (assuming it would be called more than once).

We will use the curvy arrow ↝ to indicate simplification steps within lambda bodies, as distinct from evaulation steps designated by ⇒. So the simplification steps shown above can be written:

(λ (w) 
  ((λ (x y) (+ (* x x) (* y y))) 
   (+ 1 2) w))
↝ (λ (w) 
    ((λ (x y) (+ (* x x) (* y y))) 
     3 w))
↝ (λ (w) (+ (* 3 3) (* w w)))
↝ (λ (w) (+ 9 (* w w)))

In this problem you will explore some of the benefits and limitations of such simplifications.

  1. (2 points) We will call a simplification step within a lambda expression safe if (1) it does not change the meaning of the function denoted by the lambda or (2) the simplified function does not do more work than the unsimplified one when called. Otherwise it is unsafe.

    Even in simplification, substitution can only be performed when lambda expressions are applied to values, not to arbitrary expressions. Using the following expressions, show that substituting arbitrary expressions for lambda parameters in the lambda body can be unsafe:

    • (λ (a) ((λ (b) (* b b)) (+ a a)))

    • (λ (c) ((λ (d) (+ c 1)) (/ 1 0)))

  2. (10 points) We have studied functions like the following in lecture:

    (define curry2 (λ (binop) (λ (y) (λ (z) (binop y z)))))
(define uncurry2 (λ (curried-binop) (λ (a b) ((curried-binop a) b))))
(define flip2 (λ (binop) (λ (s t) (binop t s))))
(define o (λ (f g) (λ (x) (f (g x)))))

    The goal in this subproblem is to understand the meaning of this mystery function:

    (define mystery (uncurry2 (o (curry2 map) (curry2 (flip2 -)))))

    We will begin by applying evaluation steps until we can’t get any further:

    (uncurry2 (compose (curry2 map) (curry2 (flip2 -))))

# Replace uncurry2, o, curry2, and flip by definitions
⇒* ((λ (curried-binop) (λ (a b) ((curried-binop a) b)))
    ((λ (f g) (λ (x) (f (g x))))
     ((λ (binop) (λ (y) (λ (z) (binop y z)))) map)
     ((λ (binop) (λ (y2) (λ (z2) (binop y2 z2)))) # Rename y & z to y2 and z2 for clarity
      ((λ (binop) (λ (s t) (binop t s))) -))))

# Apply (λ (binop) (λ (y) (λ (z) (binop y z)))) to map
⇒ ((λ (curried-binop) (λ (a b) ((curried-binop a) b)))
   ((λ (f g) (λ (x) (f (g x))))
    (λ (y) (λ (z) (map y z)))
    ((λ (binop) (λ (y2) (λ (z2) (binop y2 z2))))
     ((λ (binop) (λ (s t) (binop t s))) -))))

# Apply (λ (binop) (λ (s t) (binop t s))) to -
⇒ ((λ (curried-binop) (λ (a b) ((curried-binop a) b)))
   ((λ (f g) (λ (x) (f (g x))))
    (λ (y) (λ (z) (map y z)))
    ((λ (binop) (λ (y2) (λ (z2) (binop y2 z2))))
     (λ (s t) (- t s)))))

# Apply (λ (binop) (λ (y2) ...)) to (λ (s t) (- t s))
⇒ ((λ (curried-binop) (λ (a b) ((curried-binop a) b)))
   ((λ (f g) (λ (x) (f (g x))))
    (λ (y) (λ (z) (map y z)))
    (λ (y2) (λ (z2) ((λ (s t) (- t s)) y2 z2)))))

# Apply (λ (f g) ...) to (λ (y) ...) and (λ (y2) ...)
⇒ ((λ (curried-binop) (λ (a b) ((curried-binop 
                                 a) 
                                b)))
   (λ (x) ((λ (y) (λ (z) (map y z)))
           ((λ (y2) (λ (z2) ((λ (s t) (- t s)) y2 z2))) x))))

# Apply (λ (curried-binop) ...) to (λ (x) ...) 
⇒ (λ (a b) (((λ (x) ((λ (y) (λ (z) (map y z)))
                     ((λ (y2) (λ (z2) ((λ (s t) (- t s)) y2 z2))) x)))
              a) 
            b))

    Evaluation steps get us partway toward our goal, but leave us with a complicated mess that is very difficult to understand! But you can use the simplification steps described above to further simplify it into something that is understandable.

    Being very careful, start with the last expression in the evaluation sequence and apply one simplification step at a time until you cannot simplify the function any more. You should end up with a function that is very easy to understand. In addition to producing the simplified function expression, explain in English what the function does.

  3. (3 points) If simplifications within lambda expressions are so helpful, why don’t we always apply them as part of evaluation? There is a good reason. Based on the following example, explain why simplifying the body of lambda expressions is not allowed in small-step evaluation:

    (λ (n) 
  (if (> n 0) 
      (+ n 1)
      ((λ (y) (y y)) (λ (z) (+ 1 (z z))))))

2. Compositional Programming (30 points)

  1. (4 points) Many functions can be express by nesting invocations of higher-order functions like foldr, map, and filter. Below is an example. Explain in English what the intrigue function does. Do not explain in words the Racket code or algorithm. Rather, given input n, describe the output in declarative terms, like you might see in a contract for the intrigue function without seeing its implementation.

    It may be helpful to use the mathematical notation for summation in your solution. For example, the following notation means the sum of the squares of all integers i between 1 and 10:

    (define (intrigue n)
  (foldr + 0
         (map (λ (row) (foldr + 0 row))
              (map (λ (hi) (range 1 (+ hi 1)))
                   (range 1 (+ n 1))))))

  2. (10 points) Consider the following helper functions:

    (define (o f g) (λ (x) (f (g x))))
(define (o-all funs) (foldr o (λ (x) x) funs))
(define (curry2 binop) (λ (x) (λ (y) (binop x y))))
(define (curry3 ternop) (λ (x) (λ (y) (λ (z) (ternop x y z)))))
(define (flip2 binop) (λ (x y) (binop y x)))

    Using such functions, we can express nested invocations like those in intrigue using compositions of combinators, which are expressions that denote functions without using explicit lambdas. For example, here is a definition for a function that sums the squares of odd integers from 1 up to (and including) a given limit:

    (define sum-of-squares-of-odds-up-to
  (o-all (list (((curry3 foldr) +) 0)
               ((curry2 map) ((curry2 (flip2 expt)) 2))
               ((curry2 filter) (o ((curry2 =) 1) ((curry2 (flip2 remainder)) 2)))
               ((curry2 range) 1)
               ((curry2 +) 1)
               )))

> (sum-of-squares-of-odds-up-to 9)
165 ; 1^2 + 3^2 + 5^2 + 7^2 + 9^2

    Give an alternative definition of intrigue that has the following pattern, where each of the functions <fun_1> through <fun_k> is expressed without using any explicit lambdas:

    (define intrigue-composed
  (o-all (list <fun_1> 
               ...
               <fun_k>)))

  3. (7 points) In mathematics, the n-fold composition of a function f, written f n is f composed with itself n times. Thus, f 2 = f ◦ f, f 3 = f ◦ f ◦ f, and so on. Note that f 1 = f, and f 0 = the identity function.

    Define a Racket function (n-fold n f) that takes a nonnegative integer n and a unary function f and returns the n-fold composition of f. In your definition, you may not use explicit recursion. There are many different ways to define n-fold without recursion! You are allowed to use higher-order functions we’ve studied (e.g., map, foldr, foldl, genlist, iterate) as well as standard Racket functions like range.

    Here are some examples of using n-fold:

    (define (id x) x)
(define (inc x) (+ x 1))
(define (dbl y) (* y 2))

> ((n-fold 2 inc) 0)
2

> ((n-fold 17 inc) 100
117

> ((n-fold 3 dbl) 1)
8

> ((n-fold 2 (o inc dbl)) 5)
23

> ((n-fold 2 (o dbl inc)) 5)
26

> ((n-fold 17 id) 42) 
42

  4. (9 points) The curried n-fold operator cn-fold, defined below has some interesting properties.

    (define cn-fold (curry2 n-fold))
(define twice (cn-fold 2))
(define thrice (cn-fold 3))

> ((twice inc) 0)
2

> ((thrice inc) 0)
3

> ((twice dbl) 1)
4

> ((thrice dbl) 1)
8

    In the following questions suppose that a and b are nonnegative integers and f is a unary function. Justify your answer to each question.

    (1) (o (n-fold a f) (n-fold b f)) is equivalent to (n-fold p f) for what number p?

    (2) (o (cn-fold a) (cn-fold b)) is equivalent to (cn-fold q) for what number q?

    (3) ((cn-fold a) (cn-fold b)) is equivalent to (cn-fold r) for what number r?

    Note: In Church’s λ-calculus, it turns out that a function equivalent to (cn-fold n) can be used to represent the nonnegative integer n. As you can see above, you can even do arithmetic on these representations! In fact, these representations are called Church numerals for this reason.

3. Iterating with foldl and iterate (15 points)

  1. (5 points) A naive approach to evaluating a polynomial like x4 + 5x3 + 4x2 + 7x + 2 at input like 3 is to independently raise 3 to the powers 4, 3, 2, 1, 0, multiply each of the 5 coefficients by the 5 powers and finally add the results:

    1*(3*3*3*3) + 5*(3*3*3) + 4*(3*3) + 7*3 + 2*1 
= 1*81 + 5*27 + 4*9 + 21 + 2
= 81 + 135 + 36 + 21 + 2
= 275

    But there is a more efficient approach, known as Horner’s method, that uses only (n + 1) multiplications and (n + 1) additions that calculates the result as:

    ((((0*3 + 1)*3 + 5)*3 + 4)*3 + 7)*3 + 2
= ((((0 + 1)*3 + 5)*3 + 4)*3 + 7)*3 + 2
= (((1*3 + 5)*3 + 4)*3 + 7)*3 + 2
= (((3 + 5)*3 + 4)*3 + 7)*3 + 2
= ((8*3 + 4)*3 + 7)*3 + 2
= ((24 + 4)*3 + 7)*3 + 2
= (28*3 + 7)*3 + 2
= (84 + 7)*3 + 2
= 91*3 + 2
= 273 + 2
= 275

    Horner’s method for polynomial evaluation is remarkably simple to express using foldl on the lists of coeffcients. Show this by completing the following skeleton for the poly-eval function:

    (define (poly-eval coeffs x)
  (foldl {combining function} 
         {initial value}
         coeffs))

    For example:

    > (poly-eval (list 1 5 4 7 2) 3)
275

> (poly-eval (list 1 5 4 7 2) 0)
2 

> (poly-eval (list 1 5 4 7 2) 1)
19 

> (poly-eval (list 1 5 4 7 2) 10)
15472

;; Use map to test a bunch of inputs in parallel
> (map ((curry2 poly-eval) (list 1 5 4 7 2)) (range 11))
'(2 19 88 275 670 1387 2564 4363 6970 10595 15472)

;; Hey, can use this to convert binary numbers to decimal!
> (poly-eval (list 1 0 1 0 1 0) 2)
42

> (poly-eval (list 1 1 1 1 1 0 1 1) 2)
251

;; Or to convert hex to decimal:
> (poly-eval (list 6 1) 16)
97

> (poly-eval (list 1 7 4 9) 16)
5961

  2. (10 points) The iterative process of converting a decimal number to a sequence of binary bits is illustrated by the following iteration table for the conversion of the decimal number 38 to binary bits:

    num bits Notes
    38 ()  
    19 (0) 38 mod 2 = 0
    9 (1 0) 19 mod 2 = 1
    4 (1 1 0) 9 mod 2 = 1
    2 (0 1 1 0) 4 mod 2 = 0
    1 (0 0 1 1 0) 2 mod 2 = 0
    0 (1 0 0 1 1 0) 1 mod 2 = 1

    Based on this idea, use either iterate or iterate-apply from lecture to define a function (bits n) that takes a nonnegative integer n and returns a list of the bits for the binary representation of n. For example:

    > (bits 46)
'(1 0 1 1 1 0)

> (bits 251)
  '(1 1 1 1 1 0 1 1)

> (bits 1729)
'(1 1 0 1 1 0 0 0 0 0 1)

> (bits 1)
'(1)

> (bits 0)
'(0) ; Special case!

    Notes:

    • Here are the definitions of iterate and iterate-apply
    (define (iterate next done? finalize state)
  (if (done? state)
      (finalize state)
      (iterate next done? finalize (next state))))

(define (iterate-apply next done? finalize state)
  (if (apply done? state)
      (apply finalize state)
      (iterate-apply next done? finalize (apply next state))))

    • Handle an input of 0 as a special case.

    • As noted above, you can use poly-eval to test your results!

4. Pair Generation (35 points)

Consider the following Python pairs function, whose single argument n you may asssume is a positive integer

def pairs(n): # Assume n is a positive integer
    result = []
    for diff in range (1, n+1):
        for start in range(0, n+1-diff):
            result.append((start, start+diff))
    return result

  1. (4 points) The pairs function generates a list of pairs of integers related to input n, in a very particular order. Carefully describe in English exactly what the function does. Do not describe the Python code or algorithm. Rather, given input n, describe the output in declarative terms, like you might see in a contract for the pairs function without seeing its implementation.

  2. (8 points) Define a Racket function pairs-hof that has the same input-output behavior as the Python pairs function but is expressed in terms of nestings of higher order list functions like foldr and map. (``hof” means higher-order function). Do not use filter, foldl, genlist, iterate, or iterate-apply in this part. Also, a Python pair (v1, v2) should be represented a the dotted pair cons-cell (v1 . v2) in Racket.

  3. (10 points) Recall the genlist function presented in lecture for generating lists:

    (define (genlist next done? seed)
  (if (done? seed)
      null
      (cons seed (genlist next done? (next seed)))))

    Define a Racket function pairs-genlist that has the same input-output behavior as the Python pairs function but is defined using genlist by fleshing out the missing expressions in curly braces in the following skeleton:

    (define (pairs-genlist n) ; Assume is n a positive integer
  (genlist {next function goes here}
           {done? function goes here}
           {seed goes here}))

  4. (13 points) Define a Racket function pairs-iter that has the same input-output behavior as the Python pairs function but is expressed iteratively in terms of one or more tail-recursive functions. Unlike the Python pairs function and Racket pairs-genlist function, which add pairs from the front of the list to the end, your pairs-iter implementation should add pairs from the end of the list to the beginning.

    Notes:

    • You should not use iterate or iterate-apply in this problem! Instead, you should define one or more tail-recursive functions specialized for this particular problem.

    • You should not perform any list reversals in your pairs-iter definition.

    • There are many solution approaches, but some involve more than one tail recursive function. (Two nested loops in the Python pairs function naturally correspond to a pair of mutually recursive tail recursive functions.)

    • The pairs-iter function need not itself be recursive; it can call one or more tail-recursive functions.

    • It is helpful to use iteration tables involving concrete examples to help you define your tail recursive function(s).

5. List Processing with Tail Recursion and Loops (35 points)

One or more tail-recursive functions can be used to describe iterations that have complex termination and/or continuation conditions that are challenging to express with traditional looping constructs. In this problem we describe a complex iteration and then ask you (1) to flesh out a collection of tail recursive functions in Racket that implements it and (2) to write an equivalent loop in Python.

The iteration is invoked by a function process that takes one argument, which is a list of integers. If the list contains any elements other than integers, the behavior of process is unspecified. The elements of the list are processed left to right as follows:

  • Processing starts in add mode. In this mode each integer encountered is added to an accumulator that is initially 0, and the final value of the accumulator is return when the end of the list is reached. So in this mode, (process ints) just sums the integers in ints. For example:

    > (process (list 1 2 3 4 5))
15 ; 1 + 2 + 3 + 4 + 5
  
> (process (list 1 7 2 9))
19 ; 1 + 7 + 2 + 9

  • If the integer 42 is encountered in add mode, processing of the list immediately stops, and the answer accumulated so far is returned. For example:

    > (process (list 1 2 3 4 5 42 6 7))
15

> (process (list 1 2 3 42 4 5 42 6 7)) ; only leftmost 42 matters
6

> (process (list 42 1 2 3 4 5 6 7))
0

  • If a negative integer i is encountered in add mode, processing enters subtract mode, in which subsequent numbers are subtracted from the accumulator until another occurrence of same negative integer i is encountered, at which point processing switches back to add mode. The values of i for entering and leaving subtract mode do not affect the accumulator. If the end of the list is encountered before the matching i is found, the result of the accumulator is returned. In subtract mode, negative integers other than i are added to the accumutor and 42 does not end the computation but is simply subtracted from the accumulator. For example:

    > (process (list 1 2 3 -17 4 5 -17 6 7))
10 ; 1 + 2 + 3 + -4 + -5 + 6 + 7

> (process (list 1 2 -1 4 6 -1 7 8 -5 9 -5 10 11))
20 ; 1 + 2 + -4 + -6 + 7 + 8 + -9 + 10 + 11

> (process (list 1 2 3 -1 4 -5 6 -1 7 8 -5 9))
7 ; 1 + 2 + 3 + -4 + -(-5) + -6 + 7 + 8 + -9 (sequence ends before matching -5 encounterd)

> (process (list 1 2 -1 4 42 5 -1 6 7))
-35 ; 1 + 2 + -4 + -42 + -5 + 6 + 7

  • If the integer 0 is encountered in add mode, call the very next integer the skip value, and let a be the absolute value of the skip value. The next a integers after the skip value will be ignored, as if they aren’t there, and the values after these will be processed in add mode. Any occurrence of ‘42’, ‘0’, or a negative number in the next a integers will have no effect. If the list ends before processing the skip value after a 0 or before processing all a values after the skip value, the final value of the accumulator is returned. Note that 0 has no special effect in subtract mode, only add mode. For example:

    > (process (list 4 5 0 2 6 7 8 9))
26 ; skips 0 2 6 7, so treated like (process (list 4 5 8 9))

> (process (list 7 2 0 3 6 1 8 5 0 4 9 10))
14 ; skips 0 3 6 1 8 and 0 4 9 10, so treated like (process (list 7 2 5))

> (process (list 7 3 0))
10 ; skips 0, so treated like (process (list 7 3))

> (process (list 7 3 0 4 -1 0 8 42 5 -1 4 9))
2 ; skips 0 4 -1 0 8 42, so treated like (process (list 7 3 5 -1 4 9))

  1. (15 points) Below is the skeleton for a collection of tail-recursive functions in Racket that implements the process function described above. Flesh out the missing parts in curly braces so that process behaves correctly.

    (define (process ints)
  (add-mode 0 ints))

(define (add-mode ans ints)
  (if (null? ints)
      ans
      (let ((fst (first ints))
            (rst (rest ints)))
        (cond [(< fst 0) (subtract-mode fst ans rst)]
              [(= fst 0) (skip-mode-start ans rst)]
              {Add a clause to handle 42 here}
              [else {Process the remaining elements in add mode}]))))

 (define (subtract-mode end ans ints)
   {Subtract elements in ints until negative integer end is encountered,
    and then switch back to add mode. If ints runs out, return ans.}

 (define (skip-mode-start ans ints)
    (if (null? ints)
        ans
        (skip-mode (abs (first ints)) ans (rest ints))))

 (define (skip-mode number-of-elements-to-skip ans ints)
   {Skip the specified number of elements in ints one at a time, 
    and then return to add mode. If ints runs out, return ans.}

    Notes:

    • Your process function should work for very large lists. E.g.

      > (process (range 43 1000000))
499999499097

> (process (range 43 4000000))
7999997999097

> (process (append (range 43 1000000) 
                   (list -17) (range 0 1000000) 
                   (list -17) (range 1 43)))
-42

> (process (append (range 43 1000000) 
                   (list -17) (range 0 1000000) 
                   (list -17 42) (range 1 43)))
-903

> (process (append (range 43 1000000) 
                   (list -17) (range 0 1000000) 
                   (list -17 0 42) (range 1 50)))
-581

      Racket may run out of memory for very large arguments to range, but that’s because very large lists created by range take a lot of memory storage. The process function itself should require constant stack space, so should work on arbitrarily large lists.

    • You should test your resulting function on all of the above test cases to verify that it works correctly. You can do this by copying the following code into your Racket program and executing (test-all):

      (define (test-case expected nums)
  (let ((ans (process nums)))
    (if (= ans expected)
        (display (string-append "process passed test with answer " (number->string expected) "\n"))
        (display (string-append "*** ERROR: process got"
                                (number->string ans)
                                "but expected"
                                (number->string expected)
                                "\n")))))

(define (test-all)
    (test-case 15 '(1 2 3 4 5))
    (test-case 19 '(1 7 2 9))
    (test-case 15 '(1 2 3 4 5 42 6 7))
    (test-case 6 '(1 2 3 42 4 5 42 6 7))
    (test-case 0 '(42 1 2 3 4 5 6 7))
    (test-case 10 '(1 2 3 -17 4 5 -17 6 7))
    (test-case 20 '(1 2 -1 4 6 -1 7 8 -5 9 -5 10 11))
    (test-case 7 '(1 2 3 -1 4 -5 6 -1 7 8 -5 9))
    (test-case -35 '(1 2 -1 4 42 5 -1 6 7))
    (test-case 26 '(4 5 0 2 6 7 8 9))
    (test-case 14 '(7 2 0 3 6 1 8 5 0 4 9 10))
    (test-case 10 '(7 3 0))
    (test-case 2 '(7 3 0 4 -1 0 8 42 5 -1 4 9))
    (test-case 499999499097 (range 43  1000000))
    (test-case 7999997999097 (range 43  4000000))
    (test-case -42 (append (range 43  1000000) '(-17) (range 0 1000000) '(-17) (range 1 43)))
    (test-case -903 (append (range 43  1000000) '(-17) (range 0 1000000) '(-17  42) (range 1 43)))
    (test-case -581 (append (range 43  1000000) '(-17) (range 0 1000000) '(-17  0  42) (range 1 50)))
  )

  2. (20 points) Implement the same process function in Python, where it will take a Python list as an argument. The body of process should include a single while or for loop that performs the iteration performed by the functions add-mode, subtract-mode, skip-mode-start and skip-mode in the Racket version. Since a function like Racket’s rest would be prohibitively expensive in Python (taking Θ(n) rather than Θ(1) time for a list of length n), instead use list indexing (or a for loop) to process the integers in the list from left to right. Your Python function should work like the Racket function, even on large integers:

    In [16]: process(range(43, 1000000))
Out[16]: 499999499097

In [17]: process(range(43, 4000000))
Out[17]: 7999997999097

In [18]: process(range(43, 1000000) + [-17] + range(0,1000000) + [-17] + range(1,43))
Out[18]: -42

In [20]: process(range(43, 1000000) + [-17] + range(0,1000000) + [-17, 42] + range(1,43))
Out[20]: -903

In [21]: process(range(43, 1000000) + [-17] + range(0,1000000) + [-17, 0, 42] + range(1,50))
Out[21]: -581

    Add the following code to your Python file and use testAll() to test all the test cases from above.

    def testCase(expected, nums):
    ans = process(nums)
    if expected == ans:
        print "process passed test with answer", expected
    else:
        print "*** ERROR: process got", ans, "but expected", expected

def testAll():
    testCase(15, [1,2,3,4,5])
    testCase(19, [1,7,2,9])
    testCase(15, [1,2,3,4,5,42,6,7])
    testCase(6, [1,2,3,42,4,5,42,6,7])
    testCase(0, [42,1,2,3,4,5,6,7])
    testCase(10, [1,2,3,-17,4,5,-17,6,7])
    testCase(20, [1,2,-1,4,6,-1,7,8,-5,9,-5,10,11])
    testCase(7,[1,2,3,-1,4,-5,6,-1,7,8,-5,9])
    testCase(-35, [1,2,-1,4,42,5,-1,6,7])
    testCase(26, [4,5,0,2,6,7,8,9])
    testCase(14, [7,2,0,3,6,1,8,5,0,4,9,10])
    testCase(10, [7,3,0])
    testCase(2,[7,3,0,4,-1,0,8,42,5,-1,4,9])
    testCase(499999499097, range(43, 1000000))
    testCase(7999997999097, range(43, 4000000))
    testCase(-42, range(43, 1000000) + [-17] + range(0,1000000) + [-17] + range(1,43))
    testCase(-903, range(43, 1000000) + [-17] + range(0,1000000) + [-17, 42] + range(1,43))
    testCase(-581, range(43, 1000000) + [-17] + range(0,1000000) + [-17, 0, 42] + range(1,50))