Assignment #2 Solution

$30.00

Category: Tag:

Description

Write    the    functions    in    problem    1    –    3    in    a    single    file,    named    “sol2.sml”.    

Then  upload    the    file    to   the    uni06.unist.ac.kr    server  (under  your  account),    run    the

following  command    in    the    same  directory    where    you    have    sol2.sml    file.

 

plsubmit assign2 sol2.sml  

    

You  can    submit    the    file    multiple    times,    and    the    last    one    before    the    deadline    will    be    used    for    grading.    Please    test    submitting    your    solution    a    couple    of    days    before    the    deadline    to    make    sure    the    submission    works    for    you.    If    it    does    not    work,    please

contact  the    TA.

 

 

Problems  

    

  1. Simple  Eval    (10    pts)

We    define    a    simple    Propositional    Logic    as    following:

 

datatype expr = NUM of int

 

| PLUS of expr * expr

 

| MINUS of expr * expr datatype formula = TRUE

| FALSE

 

| NOT of formula

 

| ANDALSO of formula * formula

 

| ORELSE of formula * formula

 

| IMPLY of formula * formula

 

| LESS of expr * expr

 

Write  eval    function    that    takes    a    formula    value    and    returns    the    Boolean    value    of    the

formula;  i.e.    the    function    has    the    following    type:

 

eval: formula -> bool

 

IMPLY is   defined    as    in   this    link:    http://mathworld.wolfram.com/Implies.html

 

  1. Check  MetroMap    (10    pts)

We  define    a    data    type    representing    metropolitan    area    as    following:

 

datatype name = string

 

datatype metro = STATION of name

| AREA of name * metro

 

 

 

 

| CONNECT of metro * metro

 

Write  checkMetro    function    of    the    following    type:

 

checkMetro: metro -> bool

 

The  function    computes    if    the    given    metro    is    correctly    defined.    A    metro    is    correctly    defined    if    and    only    if    metro    STATION    names    appear    only    in    the    AREA    of    the    same    name.

For  example,    the    following    metros    are    correctly    defined:

 

 

 

 

 

 

 

 

AREA(“a”, STATION “a”)

AREA(“a”, AREA(“a”, STATION “a”))

AREA(“a”, AREA(“b”, CONNECT(STATION “a”, STATION “b”))) AREA(“a”, CONNECT(STATION “a”, AREA(“b”, STATION “a”)))

 

Whereas,  the    following    metros    are    incorrectly    defined:

 

AREA(“a”, STATION “b”)

AREA(“a”, AREA(“a”, STATION “b”))

AREA(“a”, AREA(“b”, CONNECT(STATION “a”, STATION “c”))) AREA(“a”, CONNECT(STATION “a”, AREA(“b”, STATION “c”)))

 

  1. Lazy  List    (40    pts    –    (i)    20   pts,  (ii)  20  pts)

(i)      A    lazy    list    is    a    data    structure    for    representing    a    long    or   even     infinite    list.    In    SML    a

lazy  list    can    be   defined    as

 

datatype ‘a lazyList = nullList

 

| cons of ‘a * (unit -> ‘a lazyList)

 

 

This  definition    says    that    lazy    lists    are    polymorphic,    having    a    type    of    ‘a.    A    value    of    a    lazy    list    is    either    nullList    or    a   cons  value    consisting   of  the   head    of   the    list    and    a    function    of    zero    arguments    that,    when    called,    will    return    a    lazy    list    representing    the    rest    of    the    list.    Write    the    following    functions    that    create    and    manipulate    lazy    lists:

 

  • seq(first,    last)        (4 pts)

This function takes two integers and returns an integer lazy list containing the sequence of values first, first+1, … , last

 

  • infSeq(first)            (4 pts)

This function takes an integer and returns an integer lazy list containing the infinite sequence of values first,first+1, ….

  • firstN(lazyListVal,n)     (4 pts)

This function takes a lazyList and an integer and returns an ordinary SML list containing the first n values in the lazyList. If the lazyList contains fewer than n values, then all the values in the lazyList are returned.

 

  • Nth(lazyListVal,n)    (4 pts)

This function takes a lazyList and an integer and returns an option representing the n-th value in the lazyList (counting from 1). If the lazyList contains fewer than n values, then none is returned. (Recall that we defined ‘a option = some of ‘a | none).

  • filterMultiples(lazyListVal,n)     (4 pts)

This function returns a new lazy list that has n and all integer multiples of n removed from a lazyList. For example, a non-lazy list version of filterMultiples would behave as follows:

filterMultiples([2,3,4,5,6],2) = [3,5]

filterMultiples([3,4,5,6,7,8],3)  = [4,5,7,8]

 

(ii)  One    of    the    algorithms    to    compute    prime    numbers    is    the    “Sieve    of    Eratosthenes.”    The    algorithm    is    simple    as    following.

 

You start with the infinite list L = 2, 3, 4, 5, …. The head of this list (2) is a prime. If you filter out all values that are a multiple of 2, you get the list 3, 5, 7,

9, …. The head of this list (3) is a prime. Now you filter out all values that are a multiple of 3, you get the list 5, 7, 11, 13, 17, …. You repeatedly take the head of the resulting list as the next prime, and then filter from this list all multiples

of the head value.

 

Write primes() function that computes a lazyList containing all prime numbers starting from 2, using the “Sieve of Eratosthenes” technique. To test your function, evaluate firstN(primes(),10); you should get [2, 3, 5, 7, 11, 13,

17, 19, 23, 29]. Try Nth(primes(),20); you should get some 71. (This may take a few seconds to compute.)

 

Hint: Create a recursive function sieve(lazyListVal) that returns a new lazyList. The first element of the cons in this lazyList should indicate the current value, as usual. The second value should be a function that calls sieve again appropriately.


error: Content is protected !!