| |
Write definitions for the following functions using map,
filter, and reduce to do all of the list
iteration. Your functions should have only a single case (no list
pattern matching) and no 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).
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 @ 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].
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).
Note that for both of these problems it may be useful to first define
auxilliary functions that do much of the work. However, only the
functions and types I have named should be available at the top
level. Any supporting declarations you make should be hidden using
local or let. (You will find it easiest to
develop and debug your work, however, if you delay the hiding until
your functions are working correctly.) Also, 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.
|
