| |
|
|
| |
The purpose of this assignment is to begin your introduction to Standard ML.
|
|
| |
Note that in some of the following functions it will be useful to first define auxilliary functions
that do much of the work. In some cases I have explicitly told you when this is so; in other cases you
will need to recognize it for yourself.
|
|
| |
- Define the function
power (x : real) (y : int) which will raise any real to any
integer power (positive or negative). The function should be recursive. You should assume that
any number raised to the power 0 is 1.
- In this problem you will write two recursive versions of the fibonnaci function, which is defined
by the recurrence:
fib(0) = 0
fib(1) = 1
fib(n+2) = fib(n+1) + fib(n)
a)
Define the function naive_fib (n : int) which computes the fibonacci function directly
according to the definition using a branching recursion. The time this function takes to compute the
value of the fibonacci number of n will grow exponentially as n grows.
b)
Define the function smart_fib (n : int) which computes the fibonacci number of n by
computing fibonacci numbers from 0 up to n successively, feeding the smaller values to the
progressively larger computations. This function should involve only a single recursive path and
therefore grow linearly as n does. You will need to do most of the computation in an auxilliary
function called smart_fib_aux that will just be called once by smart_fib and will then
call itself recursively, finally returning its calculated result to smart_fib. The purpose of
smart_fib_aux is to use tail recursion to
emulate the loop you would ordinarily use to implement this function in
an imperative language.
- Define the function
prime (n : int) which returns true if its argument is a prime number
and false otherwise.
|
|
| |
- Define the function
my_size (s : string) which returns the number of characters in the
given string. This should not rely on any built-in functions other than explode.
- Define the function
remove_vowels (s : string) which returns a copy of the string s
with all its vowels removed. To simplify the function you should first define the function vowel
(c : char) which returns true if c is a vowel, and
false otherwise, and use that function in constructing remove_vowels.
- Define the function
sieve (n : integer) which returns a list of all the numbers from 2 up
to n that are primes. You should not call the function prime written earlier, but rather use the
technique known as the Sieve of Eratosthenes. The sieve works by first building a list of all
the numbers from 2 to n. Then it removes all the numbers bigger than 2 that are divisible by 2. Then
it removes all the numbers bigger than 3 that are divisible by 3. Then all the numbers bigger than 5
divisible by 5 (after all we have already removed the numbers divisible by 2 so there won't be
anything left divisible by 4). This process is repeated, removing all the multiples of each prime
bigger than that prime.
- Define the function
diff_chars (s : string) which returns the list containing one copy of each of the characters in the string s. The order of the returned list is not important,
it may vary depending on the approach you take to the problem. Thus if the
input string were "Hello World" then the output should be some
permutation of the list [#"H",#"e",#"l",#"o",#" ",#"W",#"r",#"d"].
Note that upper and lowere case versions of the same character may be
considered to be different. (That is, you need not do anything special to
deal with the case of characters.)
|
