| |
|
|
| | The Purpose of this assignment
is to continue your introduction to Standard ML.
|
|
| | In grading this and future
assignments we will be strict in requiring that your functions types
match those specified. In particular, if a function is specified as
curried, do not make it a tuple function. (Note, however, that that
does not mean you need to put the types in your function headers. Just
that the types generated by ML should match those given.)
|
|
| |
Define the function smartFib (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 smartFibAux that will just be called once by smartFib and will then
call itself recursively, finally returning its calculated result to smartFib. The purpose of
smartFibAux is to use tail recursion to
emulate the loop you would ordinarily use to implement this function in
an imperative language.
|
|
| |
Write definitions for the following functions using map,
filter, and fold to do all of the list
iteration. Your functions should have only a single case. They
should not pattern match on the structure of the argument list. That is,
while the :: operator may appear in the body of the
function, it may not appear in the head of the function (i.e. on the
left of the = sign). You should also not make any use of
the list destructors hd
and tl. You may either define the three higher-order
functions yourself, or use the built-in versions (which are in the
List module). For full credit you should avoid declaring any auxilliary
functions unless they are explicitly mentioned below (though you may
use any unnamed functions you like, and you may call functions you
have defined for earlier problems).
sum_squares : int list -> int which returns the
sum of the squares of the numbers in its argument list.
length : 'a list -> int which computes the number
of elements in a given list.
member : ''a -> ''a list -> bool which checks
whether its first parameter is a member of the list that is given as
its second parameter.
append : 'a list -> 'a list -> 'a list which
returns the result of appending its second parameter to its first
parameter (this is built into SML as the infix @ operator).
flatten : 'a list list -> 'a list which given a
list of lists returns the result of flattening out one level of its
structure. So, for instance, the call (flatten
[[1,2,3],[4],[5,6]]) should return
[1,2,3,4,5,6].
exists : ('a -> bool) -> 'a list -> bool which
returns true if the function it is given as its first
argument returns true for any element of the list given as
its second argument, and false otherwise. This function is,
in reality, built into SML in the library function List.exists.
forall : ('a -> bool) -> 'a list -> bool which
returns true if the function it is given as its first
argument returns true for every element of the list given as
its second argument, and false otherwise. This function is,
in reality, built into SML in the library function List.all.
uniquify : ''a list -> ''a list which removes all
duplicate elements from a list, returning a list with one copy of each
element from the original list.
remove_multiples : int -> int list -> int list
which takes an integer and a list of integers and returns a list of
those integers from the original list which are not multiples of the
given integer.
sieve : int -> int list which uses the sieve
method to produce a list of all primes from 2 up to n. You may refer
to the function remove_multiples defined above, and also
a function interval : int -> int -> int list
defined as:
fun interval first last = if first > last
then nil
else (first :: (interval (first+1) last));
Note: it is very difficult using just the list-iterator functions
to get a function that actually matches the true behavior of sieve
in terms of the order and efficiency of the calculation.
We will accept versions that do not quite match up if you include a
comment explaining how you version fails to match up.
|
|
| |
Just to give you a feel for the sort of low level functions you need
to write to support the development of an interpreter (which will be
our task for much of the course). In this problem you may use any
function or operator you want, other than, of course,
Int.fromString and Real.fromString
(or anything directly related to converting
from one type to another aside from ord and real).
Note that you only need to raise the mentioned exceptions. You are not
expected to handle them at this point.
- Define a function
string_to_int : string -> int
which, given a string, will return the integer stored in the
string. So, for instance, (string_to_int "2345") should
return 2345. The function should accept either positive
or negative numbers, with negative numbers being denoted in the
traditional (non-SML) manner of a leading minus sign. So, for
instance, (string_to_int "-2345") should return
~2345.
If any character other than a digit or a minus sign is encountered
during the conversion, the exception bad_char (which you
will need to define) should be raised, with the offending character as
a parameter. Ill formed input (such as the string "-")
should lead you to raise the exception syntax_error.
- Define a function
string_to_real : string -> real
which, given a string, will return the real number stored in the
string. So, for instance, (string_to_real "-2345.678")
should return ~2345.678. The function should accept
positive and negative reals. No digits need to occur before the
decimal point, but if the decimal point is present there must be at
least one digit after it. If there is no decimal point the function
simply returns a real that has zero as a fractional part.
For extra credit, you may write the function so that the input real
includes an exponent denoted by a positive or negative integer
following an upper case E.
As above, any character other than a digit, a decimal point, a minus
sign (and E and the plus sign if you are dealing with
exponents) should raise the bad_char
exception. Ill-formed input, such as a a decimal point with no digits
after it, or an E with no exponent given, should lead you
to raise the exception syntax_error.
|
