Given the definition
f([]) = []
f(h::t) = (h*h)::f(t) when h > 10
f(h::t) = f(t) when h <= 10
show an inside-out evaluation of expression f([4,12,15,6,11]).
Show the entire expression at each step.
Assume that arithmetic is done as soon as possible.
f([4,12,15,6,11])
= f([12,15,6,11]) (since 4 <= 10)
= 144::f([15,6,11]) (since 12 > 10 and 12*12=144)
= 144::225::f([6,11]) (since 15 > 10 and 15*15=225)
= 144::225::f([11]) (since 6 <= 10)
= 144::225::121::f([]) (since 11 > 10 and 11*11=121)
= 144::225::121::[]
= 144::225::[121]
= 144::[225,121]
= [144,225,121]
Remarks.
Be sure to follow the rules exactly. Do not forget about the [] at the end. The :: operator associates to the right.
Write an equational definition of a function prefix so that prefix(x,y) is true just when list x is a prefix of list y. For example, prefix([1,2], [1,2,4,6]) is true, but prefix([1,2], [1,5,2,6]) is false. The empty list is a prefix of every list.
This is written in an equational pseudocode.
prefix([],x) = true
prefix(h::t,[]) = false
prefix(a::u,b::v) = (a == b) and prefix(u,v)
Show an inside-out evaluation of prefix([1,2], [1,2,3,4]) using your definition of prefix from the preceding question. Show the entire expression at each step.
prefix([1,2], [1,2,3,4])
= (1 == 1) and prefix([2], [2,3,4])
= true and prefix([2], [2,3,4])
= true and ((2 == 2) and prefix([], [3,4]))
= true and (true and (prefix([], [3,4])))
= true and (true and true)
= true and true
= true
Note: This function uses the boolean 'and' operator, which is often
implemented as a conditional expression: A and B is the
same as cond(A, B, false). The significance of this is
that evaluation of 'and' expressions is not done inside-out. If a
conditional 'and' expression is used, then evaluation of
prefix([1,2], [1,2,3,4]) is as follows.
prefix([1,2], [1,2,3,4])
= (1 == 1) and prefix([2], [2,3,4])
= true and prefix([2], [2,3,4])
= prefix([2], [2,3,4])
= (2 == 2) and prefix([], [3,4])
= true and prefix([], [3,4])
= prefix([], [3,4])
= true
Notice that (true and A) is replaced by A in this
conditional evaluation of 'and'.
Write an equational definition of a function called smallest so that smallest(n,x) is the smallest member of list n::x. For example, smallest(3, [6,4,7]) = 3 and smallest(8, [2,5]) = 2. You may presume that you have a function called min that takes the minimum of two numbers. For example, min(7,4) = 4.
Here are two solutions.
Definition 1: does not use min.
smallest(n,[]) = n
smallest(n,h::t) = smallest(n,t) when n <= h
smallest(n,h::t) = smallest(h,t) when n > h
Definition 2: uses min.
smallest(n,[]) = n
smallest(n,h::t) = smallest(min(n,h),t)
In a purely functional language, is it ever possible to compute the same expression twice in the same context and get different values? For example, if E is an expression, and you compute E two times, one right after another, could the first computation yield a different result from the second computation? Why or why not? (Note: Astarte is not a purely functional language. Think about the functional subset of Astarte. What is functional programming?)
Two evaluations of the same expression in the same context must always yield the same value. This is because there are no variables that can be changed.
Answer the preceding question, but instead of for a purely functional language, for an imperative language such as C++.
In a language that allows expressions to have side effects it is possible to evaluate the same expression twice and to get different answers. For example, suppose that function f is defined in C++ by
int f(int& z) {return ++z;}
Then
int z = 20;
const int x = f(z) + f(z);
does not produce the same answer as
int z = 20;
const int y = f(z);
const int x = y + y;
The two occurrences of f(z) do not produce the same answer.
By choosing among the operations foldLtoR, foldRtoL and map write a definition for each of the following that does not use recursion or loops.
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].
Remark. You can always use helper functions. This
definition still does not have any recursion, either direct
or mutual. You can avoid the helper function using the following
definition.
double(x) = x + x
doubleAll = map double
Define double = map (?x => x + x).
Write a function called maxlist(m,L) that computes the largest value in list m::L. That is, it computes the maximum of m and the largest value in list L. Assume that function max is available where max(x,y) is the larger of x and y.
maxlist(m,L) = foldLtoR(m,max) L
Function select is written so that (select p x) returns a the first member m of list x such that p(m) is true. Notice that p is a predicate, a function that produces a boolean result. (For the purposes of this question, it will not matter what select does when there is no such m.) Predicate odd? returns true on an odd number and false on an even number.
What is the value of Astarte expression map(select odd?)[[2,3,4,5],[1,2,3,4],[2,4,6,7,8]]?
[3,1,7]You are given the following function definition in Astarte.
Define f ?x ?y ?z = y x (x::z).
What kind of thing is parameter z? (A number, a list, a function, or something else)? A list. Notice expression x::z. The right-hand operand of :: is required to be a list.
What kind of thing is parameter y? (A number, a list, a function, or something else)? A function. Remember that juxtaposition is the operation of applying a function. Expression y x (x::z) applies y to x, and takes the result of that and applies it to (x::z). So y is a function, and (y x) is also a function.
What kind of thing does expression f(2) yield? (A number, a list, a function, or something else? Is this expression allowed?) A function. Function f is curried. If you give it one parameter, it produces a function that is waiting for the remaining parameters.
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.) Evaluating a promise does not
change the value that is represented, it only changes the representation of
the value.
f(2) = [4,9,16,25,...]
(an infinite list of the squares of the numbers 2,3,4,...)
What is the value of Scheme expression (car (cdr (cons 'horse (cons 'zebra ()))))?
zebra. It takes the second member of list (horse zebra).