4.9 More Recursion Examples

Problem 1

* Give a set of rules for a function which computes the list of squares of ea ch of a list of numbers. (This could be done with map, but do it from scr atch instead.)

rex > sq([]) => [] ;
rex > sq([F | R]) => [(F * F) | sq(R)] ;

Problem 2

** Give a set of rules for computing the sum of a list of numbers; for comput ing the product of a list of numbers. (This could be done with reduce, b ut do it from scratch instead.)

rex > sum([]) => 0 ;
rex > sum([F | R]) => F + sum(R) ;

rex > product([]) => 1 ;
rex > product([F | R]) => F * product(R) ;

Problem 3

rex > days_of_month(i) = [31,28,31,30,31,30,31,31,30,31,30,31](i-1) ;

rex > total_days([]) => 0 ;
rex > total_days([F | R]) => days_of_month(F) + total_days(R) ;

Problem 4

** Give a set of rules for computing the average of a list of numbers (use 0 for the average of an empty list).

rex > average([]) => 0 ;
rex > average(L) => avg(L,0,0) ;
rex > avg([], sum, length) => sum / length ;
rex > avg([F | R], sum, length) => avg(R, sum + F, length + 1) ;

Problem 5

** Indicate two different ways to compute the sum of the squares of a list of numbers.

rex > sum_sq(L) = reduce((X,Y) => X + Y*Y, 0, L) ;

rex > sum_sq(L) = reduce(+,0,map(*,L,L)) ;

Problem 6

** Give rules which define the function flip, which operates on lists, and exchanges successive pairs of elements. If there is an odd number of eleme nts, the last element is left as is. For example:

flip([1, 2, 3, 4, 5, 6, 7[) ==> [2, 1, 4, 3, 6, 5, 7]

Suggestion: Use a rule which matches on the first two elements, rather than j ust one:

flip([A, B | L]) => .... ;

rex > flip([]) => [] ;
rex > flip([A]) => [A] ;
rex > flip([A, B | L]) => [B, A | flip(L)] ;

Problem 7

*** Give rules for the function at_least which tells whether a list ha s at least a certain number of elements. For example:

at_least(3, [1, 2, 3]) ==> 1

at_least(3, [1, 2]) ==> 0

Avoid counting all of the elements of the list. This is unnecessarily ineffi cient for large lists.

rex > at_least(n, []) => n < 1 ? 1 : 0 ;
rex > at_least(0, L) => 1 ;
rex > at_least(n, [F | R]) => at_least(n - 1, R) ;

Problem 8

*** Like the previous problem, except at_most.

rex > at_most(n, L) => n > -1 ? 1 : 0 ;
rex > at_most(0, L) => 0 ;
rex > at_most(n, [F | R]) => at_most(n - 1, R) ;

Problem 9

** The function select has the property of selecting the Ith element o f a list, I >= 0, or returning a special value Other if there is no such element (the list is not long enough). That is,

select(I, [X0, X1, . . . . , X N-1], Other) ==> XI if I < N

select(I, [X0, X1, . . . . , X N-1], Other) ==> Other if I >= N

Give a set of rules for select.

rex > select(I, L, n) => length(L) < I + 1 ? n : L(I) ;

or

rex > select(I, L, n) => at_least(I+1,L)==1 ? L(I) : n ;

Problem 10

** The function find_index has the property of computing the index of the first occurence of a given element within a list. If there is no such occur rence, -1 is returned. For example,

find_index('d', ['a', 'b', 'c', 'd', 'e']) ==> 3
find_index('a', ['a', 'b', 'c', 'd', 'e']) ==> 0
find_index('g', ['a', 'b', 'c', 'd', 'e']) ==> -1

Give a complete set of rules for find_index.

rex > find_index(n, L) = find_index(n, L, 0);
rex > find_index(n, [], i) => -1 ;
rex > find_index(n, [F | R], i) => n==F ? i : find_index(n, R, i + 1) ;