What is shadowing, and how can it occur? Give an example.
Shadowing occurs when an identifier is bound within the scope of another binding of the same identifier. The more recent binding shadows the older one. Here is an example in C++.
{int x;
x = 3;
{int x;
x = 6;
}
}
The inner x shadows the outer one.
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]).
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.
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)
Write an equational definition of a function stutter where stutter([a,b,c,d]) = [a,a,b,b,c,c,d,d]. In general, stutter includes two copies of each item.
stutter([]) = []
stutter(h::t) = h::h::stutter(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, could
Let x = E + E.
ever yield a different result from
Let y = E.
Let x = y + y.
Why or why not?
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.
This is not true in a language that allows expressions to have side effects. For example, suppose that function f is defined in C++ by
int f(int& z) {return ++z;}
Then
const int x = f(z) + f(z);
does not produce the same answer as
const int y = f(z);
const int x = y + y;
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.
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.
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
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,...)
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
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.