1. By choosing among the operations lfold, rfold, map and select, write a definition for each of the following that does not use recursion or loops.

   1. Write a function called doubleAll that takes a list x of numbers as its parameter and produces a list of the doubles numbers in list x as its result. For example, doubleAll([5,2,19,3]) = [10,4,38,6].

             double(x) = x + x
             doubleAll = map double
          

      Remark. You can always use helper functions. This definition still does not have any recursion, either direct or mutual.

   2. Write a function called firstPos that returns the first positive number from a list of numbers. For example, firstPos([-4, -2, 0, 6, 12, -9]) = 6. Presume that the list has at least one positive number in it.

             positive(x) = x > 0
             firstPos = select positive
          

2. Consider the following definition written in Astarte.

       Define f(?n) = (:n*n :: f(n+1):).
     

   What value does expression f(2) compute? Give the full value, as it would be if it were examined. (It suffices to give a clear description of the full value.)

   f(2) = [4,9,16,25,...]

   (an infinite list of the squares of the numbers 2,3,4,...)

3. Using Astarte syntax write a definition of a function called filter so that (filter p L) returns a list of all members x of list L such that p(x) is true. For example, if p is the predicate so that p(x) is true just when x < 100, then (filter p [3,81,200,34,999,3000,20]) = [3,81,34,20].

       Define filter by first
         case filter ?p [] = []
         case filter ?p (?h::?t) = h::(filter p t)  when p(h)
         case filter ?p (?h::?t) = filter p t
       %Define
     

4. Indicate how the definition of filter might be changed to prevent filter from computing the entire list before returning part of the list, so that a function that only wants to look at part of the result of filter does not need to evaluate the entire result list.

   It suffices to make it lazy. For example, replace the recursive call (filter p t) by (:filter p t:), or write

       Define filter by first
         Await then
           case filter ?p [] = []
           case filter ?p (?h::?t) = h::(filter p t)  when p(h)
           case filter ?p (?h::?t) = filter p t
         %Await
       %Define
     

   to make it fully lazy. (We did not talk about the latter approach.)

5. What is the value of Scheme expression (car (cdr (cons 'horse (cons 'zebra ()))))?

   zebra

6. Write a Scheme function called drop so that (drop n L) returns the result of removing the first n members from list L. If L has fewer than n members, then (drop n L) should return the empty list. For example, (drop 2 '(4 8 3 5 7)) = (3 5 7) and (drop 3 '(5 2)) = (). Be careful to use Scheme syntax correctly.

     (define (drop n L)
       (cond
          ((eq? n 0)  L)
          ((null? L)  ())
          (else       (drop (- n 1) (cdr L)))
       )
     )
     

Write the filter function in Scheme. That is, write a filter function so that (filter p L) returns a list of all members x of list L such that (p x) is true. Do not try to make it lazy.

    (define (filter p L) 
       (cond
          ((null? L) ())
          ((p (car L)) (cons (car L) (filter p (cdr L))))
          (else (filter p (cdr L))
       )
    )
  

Additional exercises can be found in ex1/ex1.ast. That file has you write a few function definitions. You can then run the tester to see if they work. You will need to get the support files that are used for testing. File ex1_solved.ast is a solved version. Here are the files that you need.

• ex1.ast
• ex1_solved.ast
• checkout.ast
• ex1_rules.ast
• ex1_test.ast