• Give a set of rules for a function which computes the list of squares of each of a list of numbers. (This could be done with map, but do it from scratch instead.)
rex> squares([]) => [];
rex> squares([A|L]) => [A*A | squares(L)];
• • Give a set of rules for computing the sum of a list of numbers; for computing the product of a list of numbers. (This could be done with reduce, but do it from scratch instead.)
Sum
rex> sum(L) = sum(L,0);
rex> sum([],N) => N;
rex> sum([A|L],N) => sum(L,N+A);
Product
rex> product(L) = product(L,1);
rex> product([],N) => N;
rex> product([A|L],N) => product(L,N*A);
• • Using your function days_of_month constructed in an earlier exercise, give rules for the function total_days which takes as an argument a list of months and returns the sum of the days in those months.
rex> total_days(L) = total_days(L,0);
rex> total_days([],N) => N;
rex> total_days([A|L],N) => total_days(L,N + month_to_days(A));
• • 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(L) = average(L,0,0);
rex> average([],0,0) => 0;
rex> average([],N,M) => N/M;
rex> average([A|L],N,M) => average(L,N+A,M+1);
• • Indicate two different ways to compute the sum of the squares of a list of numbers.
Low-Level Method
rex> sum_square(L) = sum_sq(L,0);
rex> sum_sq([],N) => N;
rex> sum_sq([A|L],N) => sum_sq(L,(A*A) + N);
High-Level Method
rex> sum_square(L) = reduce(+, 0, map((X) => X*X, L));
• • Give rules which define the function flip, which operates on lists, and exchanges successive pairs of elements. If there is an odd number of elements, 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 just one:
flip([A, B | L]) => .... ;
rex> flip([]) => [];
rex> flip([A]) => [A];
rex> flip([A,B|L]) => [B,A | flip(L)];
• • • Give rules for the function at_least which tells whether a list has 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 inefficient for large lists.
rex> at_least(X,L) = at_least(X,L,1);
rex> at_least(X,[],C) => 0;
rex> at_least(X, [A|L] ,C) => X <= C ? 1 : at_least(X,L,C+1);
• • • Like the previous problem, except at_most.
rex> at_most(X,L) = at_most(X,L,1);
rex> at_most(X,[],L) => 1;
rex> at_most(X, [A|L], C) => X < C ? 0 : at_most(X,L,C+1);
• • The function select has the property of selecting the Ith element of 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, ...., XN-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,X) = select(I,L,X,0);
rex> select(I,[],X,C) => X;
rex> select(I,[A|L],X,C) => I == C ? A : select(I,L,X,C+1);
• • The function find_index has the property of computing the index of the first occurrence of a given element within a list. If there is no such occurrence, -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(X,L) = find_index(X,L,0);
rex> find_index(X,[],C) => -1;
rex> find_index(X, [A|L], C)=> X == A ? C : find_index(X,L,C+1);
• • • Give rules for a function remove_duplicates which removes all duplicates in a list. For example
remove_duplicates([1, 2, 1, 3, 1, 2, 3]) ==> [1, 2, 3]
rex> remove_duplicates([]) => [];
rex> remove_duplicates([A|L]) => member(A,L) ? remove_duplicates(L) :
[A | remove_duplicates(L);
• • Give rules for a function that gives the value of a list representing the 2-adic representation of a number, least-significant digit first, using the digits 1 and 2.
• • • Give rules for a function that gives the list representation of a number in 2-adic form, least-significant digit first.
• • • Give rules for a function that produces the list of prime factors of a natural number. For example:
factors(72) ==> [2, 2, 2, 3, 3]
• • Using functions above, give rules for a function that produces the unique prime factors of a natural number. For example
unique_factors(72) ==> [2, 3]
rex> unique_factors(X) = remove_duplicates(factors (X));
• • Give rules for the function subst which makes substitutions in a list. Specifically, subst(A, L, R) returns a new list which is like list L except that whenever A would have occurred as a member of L, R occurs instead.
rex> subst(A,[],R)=>[];
rex> subst(A, [Z|L], R, N)=> A == Z ? [R | subst(A,L,R)] : [Z |
subst(A,L,R)];
• • By adding an extra argument, and assuming integer functions mod and div, generalize the function add_bin to a function which adds in an arbitrary radix.
• • • Devise a function which will multiply two numbers represented as a list of bits, least-significant-bit first. Notice that this function has some advantage over the standard multiplication function found in most programming languages, namely that it will work for arbitrarily-large numbers.
• • • Sometimes we use numeral systems of mixed radix. For example, in referring to time within a given month, we could use expressions of the form D:H:M:S for days, hours, minutes, and seconds. H ranges from 0 to 24, M from 0 to 59, and S from 0 to 59. To compute the number of seconds from the start of the day corresponding to a given time, we'd compute:
S + 60*(M + 60*(H+24*D)).
Generalize this mixed radix computation by giving rules for a function value that takes as arguments two lists, one giving the ranges and another giving the ordinal numbers within these ranges. For example, in the current case we would call
value( [S, M, H, D], [60, 60, 24] )
• • • Devise a function that will divide one number represented in binary by another, yielding a quotient and a remainder. This function should return the pair of two items as a list. Do the division digit-by-digit, don't convert to another form first.
• • The function keep takes two arguments: a predicate and a list: keep(P, L) is the list of those items in L such that P is true for the item. For example,
keep(odd, [1,3,2,4,6,7]) ==> [1,3,7]
Provide rex rule definitions for keep.
rex> keep(F,[]) => [];
rex> keep(F,[A|L]) => F(A) ? [A | keep(F,L)] : keep(F,L);
• • The function drop is like function keep above, except that the items for which P is not true are kept. For example,
drop(odd, [1,3,2,4,6,7]) ==> [2,4,6]
Provide rex rule definitions for drop.
rex> drop(F,[]) => [];
rex> drop(F,[A|L]) => F(A) ? drop(F,L) : [A | drop(F,L)];
• • The function select takes two arguments: a list of 0's and 1's and another list, usually of the same length. select(S, L) is the list of those items in L for which the corresponding element of S is 1. For example,
select([1,0,0,1,1,0], [1,3,2,4,6,7]) ==> [1,4,6]
Provide rex definitions for select.
rex> select([],M) => [];
rex> select(L,[]) => [];
rex> select([A|L], [B|M]) => A == 1 ? [B | select(L,M)] :
select(L,M);
• • Iterated function systems are used for producing so-called "fractal" images. These entail applying a function repeatedly to an initial seed argument. Let
FN(X)
denote
F(F(F...(F(X))...))
N applications of F
including the definition:
F0(X) = X.
Give rewrite rules for the function iterate informally defined by:
iterate(N, F, X) ==> FN(X)
• • • Restate the definition of Ackermann's function using iterate.
• • • By indefinite iteration we mean iteration that stops when some condition is true, rather than by iterating a pre-determined number of times. The condition for stopping is best expressed as a predicate, say P. Give the rewrite rules for a function
indefinite_iterate(P, F, X)
defined to compute
Fn(X)
where n is the least value of N such that P(FN(X)) == 1.
• • • Give the rules for a function which transposes a matrix represented as a list of lists. Your function can assume that each "row" of the matrix has the same number of elements without checking. You might, however, wish to construct a separate function which checks the integrity of the matrix. Check your definition carefully and show that the types match up.
• • • Referring to the previous problem, if you understand matrix addition and multiplication, construct functions which carry out these operations.
• • • • If you understand matrix inversion, construct a function which carries out this operation.
• • Show how to use enumeration to define the function radix without using the % and / functions.
| Return |