1. Functional Programming. Implement a function in OCAML that takes a number as

Question

1. Functional Programming. Implement a function in OCAML that takes a number as an input and checks whether it is a prime number. The result should be a Boolean value.

2. Functional Programming. Implement the Fibonacci function by means of accumulative parameters so that it runs in linear time.

3. Functional Programming. Given the program:

let rec x = 1 and f = fun y x + y + z and z = 4 in let rec x = 2 and g = fun y x + (f y) + z in let rec x = 3 and f = fun y y and z = 5 in g 6 What is the output of the program a) with static scoping? b) with dynamic scoping?

4. Functional Programming. Implement the following functions in OCAML (alternatively in SML), without using corresponding libraries: • member takes as arguments an element e and a list l and returns whether the element is included in the list. • filter takes as arguments a predicate p and a list l and returns a list of the elements from l for which p is true. • fold_left successively combines the elements of the list with some function starting from an initial value for the empty list. This means that: fold_left f e [x1; x2; . . . ; xn] = f (...( f (f ex1) x2) . . .) xn • mapi takes as arguments a function f and a list l and applies f to each pair of an element from l and its position in l: mapi f [x1; x2; . . . ; xn] = [f x1 1; f x2 2; . . . ; f xn n] For f x i = x + i, the call mapi f [3; 3; 3] should return the list [4; 5; 6].

Explanation / Answer

Lazyness in OCaml

The keyword lazy is reserved to indicate that some expression should be evaluated lazily. It works as a function that lifts an arbitrary expression to its lazy equivalent, i.e., of type ’a -> ’a Lazy.t.

Consider for example the function
let one _ = 1
that ignores its argument and returns 1.
When called eagerly, as for example in the call one(print_string "test"), first the argument print_string "test" is evaluated (printing “test”), and then 1 is returned. If the same function call is done lazily however, the result differs. Namely, the function call one(lazy(print_string "test")) just returns 1 without printing “test”, since the argument is never used within the function body.

Together with lazy comes the function force : ’a Lazy.t -> ’a from the module Lazy that provides a way to force the evaluation of some lazy expression, i.e., a lazy expression will not evaluate until forced to do so.

lazy Nil                                                                                 []

lazy (Cons(1,lazy Nil))                                                    [1]

lazy (Cons(2,lazy (Cons(1,lazy Nil))))                       [2;1]

For convenience the function fc is installed as an abbreviation for Lazy.force.

let fc = Lazy.force

Consider from: int -> int t as a first example of a function on this kind of lazy lists.

let rec from n = lazy(Cons(n,from(n+1)))

Next consider filter : (’a -> bool) -> ’a t -> ’a t which removes all elements from a lazy list that do not satisfy a given predicate.

using the function from

let rec sieve xs = lazy(match fc xs with

| Nil -> Nil

| Cons(x,xs) ->

Cons(x,sieve(filter (fun y -> y mod x <> 0) xs)) )

Using this, the list of all primes can be computed by let primes = sieve(from 2) To get concrete results the function to_list from above is used.

E.g., the first 100 prime numbers are computed by:

# to_list 100 primes;;

- : int list =

[2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71; 73; 79; 83; 89; 97; 101; 103; 107; 109; 113; 127; 131; 137; 139; 149; 151; 157; 163; 167; 173; 179; 181; 191; 193; 197; 199; 211; 223; 227; 229; 233; 239; 241; 251; 257; 263; 269; 271; 277; 281; 283; 293; 307; 311; 313; 317; 331; 337; 347; 349; 353; 359; 367; 373; 379; 383; 389; 397; 401; 409; 419; 421; 431; 433; 439; 443; 449; 457; 461; 463; 467; 479; 487; 491; 499; 503; 509; 521; 523; 541]

These are 18 lines in total (including the type of lazy lists) to compute arbitrarily many prime numbers! (In a language that has built-in lazy lists, this would be a two-liner.)

Note:

The Sieve of Eratosthenes is a simple algorithm to compute all prime numbers. The idea is to start at the sequence of all natural numbers from 2 on, i.e.,

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 . . . .

Then repeatedly apply the following steps to the sequence:

a) mark the first element h of the sequence as prime

b) remove all multiples of h (including h itself) from the sequence

c) goto step 1 Here are the first few iterations:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 . . .

3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 . . .

5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 . . .

7 11 13 17 19 23 29 31 37 41 43 47 49 53 59 . . .

11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 . . . and so on.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.