Programming Languages (2) ---Functional Programming Basics

Enter your name and student ID.

• Name:
• Student ID:

1. Choose your language

Choose a language you want to work on for today from the following.

• Go --- designed as a "better C"
• Julia --- popular for scientific computing
• OCaml --- a practical functional language
• Rust --- a system programming language with memory safety without garbage collection

Declare your choice in the following cell. You can write any number of languages you actually worked on. In this notebook, I will work on the following language(s).

BEGIN SOLUTION END SOLUTION

2. Roadmap

• Below, you are going to learn the basics of functional programming.

• Note: follow case conventions/requirements about type names of your language; Go, Julia and Rust conventionally capitalize them and OCaml requires them to be in lowercase

3. Read documents

• Before you start, spend some time to go through relevant sections of your language manual

• Go:

• Julia:

• OCaml:

• Rust: language manual and other docs

Problem 1 : A simple recurrence relation

Write a "functional program" that is given $n$ and computes the value of $a_n$ of the following recurrence.

$$ \begin{eqnarray*} a_0 & = & 1, \\ a_n & = & 0.9\; a_{n-1} + 2 \quad (n > 0) \end{eqnarray*} $$

• If it matters in your language, make it return 64-bit floating point numbers.

The following is a "procedural" version in Python.

def a(n):
    x = 1.0
    for i in range(n):
        x = 0.9 * x + 2.0
    return x

• Here, you are asked to write a "functional" version, whose superficial characteristics are

  • it does not use loops
  • it does not update variables

• But more important is the fact that you can straightforwardly express the above recurrence using a recursive call.

• Once you master this way of thinking, you don't even have to think of loops or updating variables.

• In cells that follow, choose your language from the language selection menu.

解答セル/Answer Cell

Go

func a(n int64) float64 {
	if n == 0 {
		return 1
	} else {
		return 0.9 * a(n - 1) + 2
	}
}

Test Go

import "math"
import "fmt"
func float64_close(x float64, y float64, eps float64) {
    if math.Abs(x - y) > eps {
        fmt.Printf("NG\n")
    } else {
        fmt.Printf("OK\n")
    }
}
    float64_close(a(0),   1,          1.0e-6)
    float64_close(a(10),  13.3751096, 1.0e-6)
    float64_close(a(100), 19.9994953, 1.0e-6)
    float64_close(a(300), 20.0,       1.0e-6)

Julia

function a(n)
    if n == 0
        1
    else
        0.9 * a(n - 1) + 2
    end
end

Test Julia

function float64_close(x, y, eps)
    if abs(x - y) > eps
        println("NG")
    else
        println("OK")
    end
end
    float64_close(a(0),   1,          1.0e-6)
    float64_close(a(10),  13.3751096, 1.0e-6)
    float64_close(a(100), 19.9994953, 1.0e-6)
    float64_close(a(300), 20.0,       1.0e-6)

OCaml

let rec a n =
  if n = 0 then
    1.0
  else
    0.9 *. (a (n - 1)) +. 2.0
;;

Test OCaml

let float64_close x y eps =
  if abs_float (x -. y) > eps then
    Printf.printf "NG\n"
  else
    Printf.printf "OK\n"
;;
    float64_close (a 0)   1.0        1.0e-6;
    float64_close (a 10)  13.3751096 1.0e-6;
    float64_close (a 100) 19.9994953 1.0e-6;
    float64_close (a 300) 20.0       1.0e-6;
    flush_all ()
;;

Rust

fn a(n : i64) -> f64 {
    if n == 0 {
        1.0
    } else {
        0.9 * a(n - 1) + 2.0
    }
}

Test Rust

fn float64_close(x : f64, y : f64, eps : f64) {
    if (x - y).abs() > eps {
        println!("NG")
    } else {
        println!("OK")
    }
}
    float64_close(a(0),   1.0,        1.0e-6);
    float64_close(a(10),  13.3751096, 1.0e-6);
    float64_close(a(100), 19.9994953, 1.0e-6);
    float64_close(a(300), 20.0,       1.0e-6);

Problem 2 : Find a divisor

Write a program, or more specifically a function, smallest_divisor_geq($n$, $x$), that finds the smallest divisor of a given integer $n$ that is $\geq x$.

In Python syntax,

>>> smallest_divisor_geq(10, 2)
2
>>> smallest_divisor_geq(35, 2)
5
>>> smallest_divisor_geq(43, 2)
43

You may assume:

• $n$ is an integer and $2 \leq n < 2^{25}$
• $x$ is an integer and $2 \leq x \leq n$
• $n$ is not visible by any integer $y$ s.t. $2 \leq y < x$

If it matters in your language, use 64-bit integers for $n$ and $x$.

Write it in a "functional" style (no loops or updates to variables).

Hint: functional thinking goes: "The trivial case is when $x$ divides $n$. Otherwise?"

解答セル/Answer Cell

Go

func smallest_divisor_geq(n int64, x int64) int64 {
    if n % x == 0 {
		return x
    } else if n < x * x {
        return n
    } else {
		return smallest_divisor_geq(n, x + 1) 
	}
}

Test Go

func int64_eq(x int64, y int64) {
    if x == y {
        fmt.Printf("OK\n")
    } else {
        fmt.Printf("NG\n")
    }
}
    int64_eq(smallest_divisor_geq(2,          2), 2)
    int64_eq(smallest_divisor_geq(3,          2), 3)
    int64_eq(smallest_divisor_geq(13 * 17,    2), 13)
    int64_eq(smallest_divisor_geq(6700417, 2), 6700417)

Julia

function smallest_divisor_geq(n, x)
    if n % x == 0
        x
    elseif n < x * x
        n
    else
        smallest_divisor_geq(n, x + 1)
    end
end

Test Julia

function int64_eq(x, y)
    if x == y
        println("OK")
    else
        println("NG")
    end
end
    int64_eq(smallest_divisor_geq(2,          2), 2)
    int64_eq(smallest_divisor_geq(3,          2), 3)
    int64_eq(smallest_divisor_geq(13 * 17,    2), 13)
    int64_eq(smallest_divisor_geq(6700417, 2), 6700417)

OCaml

let rec smallest_divisor_geq n x =
  if n mod x = 0 then
    x
  else if n < x * x then
    n
  else
    smallest_divisor_geq n (x + 1)
;;

Test OCaml

let int64_eq x y =
  if x == y then
    Printf.printf "OK\n"
  else
    Printf.printf "NG\n"
;;
    int64_eq (smallest_divisor_geq 2          2) 2;
    int64_eq (smallest_divisor_geq 3          2) 3;
    int64_eq (smallest_divisor_geq (13 * 17)  2) 13;
    int64_eq (smallest_divisor_geq 6700417    2) 6700417;
    flush_all ()
;;

Rust

fn smallest_divisor_geq(n : i64, x : i64) -> i64 {
    if n % x == 0 {
        x
    } else if n < x * x {
        n
    } else {
        smallest_divisor_geq(n, x + 1)
    }
}

Test Rust

fn int64_eq(x : i64, y : i64) {
    if x == y {
        println!("OK")
    } else {
        println!("NG")
    }
}
    int64_eq(smallest_divisor_geq(2,          2), 2);
    int64_eq(smallest_divisor_geq(3,          2), 3);
    int64_eq(smallest_divisor_geq(13 * 17,    2), 13);
    int64_eq(smallest_divisor_geq(6700417, 2), 6700417)

Problem 3 : Factorization

Write a program, or more specifically, a function factorize($n$), that finds the factorization of $n$. The answer should be a list (or an array) of integers, whose products $=$ $n$. For convenience, the factorization of 1 is an empty list (or an array). In Python,

>>> factorize(12)
[2,2,3]
>>> factorize(105)
[3,5,7]
>>> factorize(19)
[19]
>>> factorize(1)
[]

• To make the correct answer unique, the list must have numbers in the ascending order

Hint:

• Once you find a divisor of $n$, say $a$, just factorize $n/a$.
• To solve this problem, you probably need a method that takes an integer a0 and a sequence [a1, a2, a3, ...] and returns the sequence [a0, a1, a2, ...]. Here are how you can do it with each of the languages.
  • Go : append
  • Julia : vcat
  • OCaml : builtin operator ::
  • Rust : concat

解答セル/Answer Cell

• This problem requires you to prepend an element in front of an existing sequence (e.g., given an element x and a sequence p, q, r, ..., make a sequence x, p, q, r, ...
• How this can be done depends on the language and is separately addressed below

Go

• Go has an array-like data structure called "slice"
• slice is like a dynamically-sized array
• []T is a type expression representing slice of T
• []T{a,b,c,...} is an expression representing a slice containing a, b, c, ...
• Go has an append function that returns a slice extended with an arbitrary number of extra elements at the end of a slice. It can take a slice and any number of elements you want to extend the slice with. For example,
  • let s be a slice containing 1, 2, and 3 (i.e., []int64{1,2,3})
  • append(s, 4) is a slice containing 1, 2, 3, and 4
  • append(s, 4, 5) is a slice containing 1, 2, 3, 4, and 5
  • append(s, 4, 5, 6) is a slice containing 1, 2, 3, 4, 5, and 6
  • and so on
• In addition, Go allows you to pass elements of a slice to a function call as if you are passing them individually. Its syntax is f(slice...). For example, let s be the same slice,
  • f(s...) is equivalent to f(1,2,3)
• Finally, therefore append(s, t...) has an effect of concatenating two slices s and t
• To prepend an element x in front of slice a, you concatenate a singleton slice containing only x, and a
• Hence this cryptic expression append([]int64{x}, a...)

func factorize(n int64) []int64 {
	if n == 1 {
        // an empty slice
		return []int64{}
	} else {
		x := smallest_divisor_geq(n, 2)
		a := factorize(n / x)
		return append([]int64{x}, a...)
	}
}

Test Go

func int64_list_eq(a []int64, b []int64) {
    if a == nil && b == nil {
        fmt.Printf("OK\n")
    } else if a == nil || b == nil {
        fmt.Printf("NG\n")
    } else if len(a) != len(b) {
        fmt.Printf("NG\n")
    } else {
        for i := 0; i < len(a); i++ {
            if a[i] != b[i] {
                fmt.Printf("NG\n")
                return
            }
        }
        fmt.Printf("OK\n")
    }
}
    int64_list_eq(factorize(64), []int64{2, 2, 2, 2, 2, 2})
    int64_list_eq(factorize(105), []int64{3, 5, 7})

Julia

• Julia has vcat that takes an arbitrary number of arrays and concatenate them together
  • vcat([1,2,3], [4,5]) is [1,2,3,4,5]
• You can also pass a scalar, which is considered a singleton array containing only that scalar
  • vcat(1, [2,3,4,5]) is [1,2,3]
• Prepending an element x in front of an array a is as simple as vcat(x, a)

function factorize(n)
    if n == 1
        []
    else
        x = smallest_divisor_geq(n, 2)
        a = factorize(n / x)
        vcat(x, a)
    end
end

Test Julia

function int64_list_eq(a, b)
    if a == b
        println("OK")
    else
        println("NG")
    end
end
    int64_list_eq(factorize(64), [2, 2, 2, 2, 2, 2])
    int64_list_eq(factorize(105), [3, 5, 7])

OCaml

• In OCaml, this is very straightforward
• When a is a list and x an element, x :: a is a list that prepends x in front of a
• e.g., 1 :: [2; 3; 4] is [1; 2; 3; 4]

let rec factorize n =
  if n = 1 then
    []
  else
    let x = smallest_divisor_geq n 2 in
    x :: (factorize (n / x))
;;

Test OCaml

let int64_list_eq a b =
  if a = b then
    Printf.printf "OK\n"
  else 
    Printf.printf "NG\n"
;;
    int64_list_eq (factorize 1)   [];
    int64_list_eq (factorize 5)   [5];
    int64_list_eq (factorize 64)  [2; 2; 2; 2; 2; 2];
    int64_list_eq (factorize 105) [3; 5; 7];
    flush_all ()
;;

Rust

• In Rust, concat() method can concatenate any number of vectors
• Given vectors a, b, c, ...,
  • [a, b].concat() concatenates a and b
  • [a, b, c].concat() concatenates a, b and c
  • etc.
• e.g.,
  • [vec![1,2], vec![3,4,5]].concat() is a vector containing 1,2,3,4, and 5
• Therefore, to prepend x in front of a vector a, [vec![x], a].concat() will do

fn factorize(n : i64) -> Vec<i64> {
    if n == 1 {
        vec![]
    } else {
        let x = smallest_divisor_geq(n, 2);
        let a = factorize(n / x);
        [vec![x], a].concat()
    }
}

Test Rust

fn int64_list_eq(a : Vec<i64>, b : Vec<i64>) {
    if a == b {
        println!("OK")
    } else {
        println!("NG")
    }
}
    int64_list_eq(factorize(64), vec![2, 2, 2, 2, 2, 2]);
    int64_list_eq(factorize(105), vec![3, 5, 7])

Problem 4 : A Combinatorial Problem

• Write a function subset_sum($a$, $v$) which, given a sequence (array or list depending on the language) of positive integers $a$ and try to make a subset of $a$ whose sum is $v$

• More specifically, it should return either

  1. a sequence $k$ of 0/1's s.t.
  • $k$ has the same length with $a$
  • sum of elements in $a$ whose corresponding value in $k$ is one is $v$ (the $i$-th element of $a$ "corresponds to" the $i$-th element of $k$), if such a subset indeed exists, or
  1. nil (Go), nothing (Julia), or None (OCaml or Rust) if no such subset exists

• In math terms, the dot product of $a$ and the returned sequence is $v$

• In Python syntax,

>>> subset_sum([1, 1, 1, 10, 100], 12)
[1, 1, 0, 1, 0]
>>> subset_sum([1, 1, 1, 10, 100], 19)
None
>>> subset_sum([1, 2, 4, 8, 16], 13)
[1, 0, 1, 1, 0]

• To make the correct answer unique, if there are two or more subsets whose sum make $v$, a list that is lexicographically greatest should be returned (in plain terms, try to choose elements that come earlier in $a$)

解答セル/Answer Cell

Basic idea:

• This is where the functional thinking or problem solving by recursion really shines

• Imagine you are asked to make a sum of 1000 out of [12, 7, 39, 23, ...]

• The recursive thinking goes

  1. First assume take the first element in the set. Then, making 1000 out of [12, 7, 39, 23, ...] is now equivalent to making 988 (= 1000 - 12) out of the remaining [7, 39, 23, ...]
  2. Next assume instead we do not take the first element in the set. Then making 1000 is equivalent to making 1000 out of [7, 39, 23, ...]

• The code below straightforwardly expresses this idea.

• It naturally returns the lexicographically greatest one. If you are instead asked to return the lexicographically smallest one, examine the second choice first

• This problem also needs a way to represent a list or a special value indicating no such set exists

• How this is done depends on the language is separately addressed below

Go

• Go has a slice to represent a sequence and a special value nil can be used to indicate no such set exists
• nil is much like a null pointer in C/C++; it is OK to return nil from a function whose return type is a slice
• Static type checker does not complain about it. The flip side is that you always have to assume a value whose static type is a slice (or pretty much any other type, for that matter) may in fact be a nil

func subset_sum(a []int64, v int64) []int64 {
	if v == 0 {
        return make([]int64, len(a))
    }
    if len(a) == 0 {
        return nil
    }
    k1 := subset_sum(a[1:], v - a[0])
    if k1 != nil {
        return append([]int64{1}, k1...)
    }
    k0 := subset_sum(a[1:], v)
    if k0 != nil {
        return append([]int64{0}, k0...)
    }
    return nil
}

Test Go

int64_list_eq(subset_sum([]int64{1,2,3,4,5}, 8), []int64{1, 1, 0, 0, 1})
    int64_list_eq(subset_sum([]int64{33, 28, 56, 35, 19, 46, 25, 58, 17, 49, 33, 39, 37, 33, 24, 52}, 233),
        []int64{1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0})
    int64_list_eq(subset_sum([]int64{30, 37, 46, 41, 14, 46, 44, 40, 46, 30, 46, 28, 33, 31, 56}, 171),
        []int64{1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0})
    int64_list_eq(subset_sum([]int64{47, 39, 15, 27, 52, 31, 39, 54, 20, 26, 38, 19, 35, 28}, 440), nil)
    int64_list_eq(subset_sum([]int64{16, 24, 13, 20, 24, 13, 11, 31, 29, 44}, 222), nil)

Julia

• Julia has an array to represent a sequence and a special value nothing can be used to indicate no such set exists

function subset_sum(a, v)
    if v == 0
        return zeros(Int64, length(a))
    elseif v < 0 || length(a) == 0
        return nothing
    end
    k1 = subset_sum(a[2:end], v - a[1])
    if k1 != nothing
        return vcat([1], k1)
    end
    k0 = subset_sum(a[2:end], v)
    if k0 != nothing
        return vcat([0], k0)
    end
    nothing
end

Test Julia

int64_list_eq(subset_sum([1,2,3,4,5], 8), [1, 1, 0, 0, 1])
    int64_list_eq(subset_sum([33, 28, 56, 35, 19, 46, 25, 58, 17, 49, 33, 39, 37, 33, 24, 52], 233),
                  [1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
    int64_list_eq(subset_sum([30, 37, 46, 41, 14, 46, 44, 40, 46, 30, 46, 28, 33, 31, 56], 171),
                  [1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0])
    int64_list_eq(subset_sum([47, 39, 15, 27, 52, 31, 39, 54, 20, 26, 38, 19, 35, 28], 440), nothing)
    int64_list_eq(subset_sum([16, 24, 13, 20, 24, 13, 11, 31, 29, 44], 222), nothing)

OCaml

• OCaml has a type called $t$ option, which can be used to represent either a value of $t$ or a special value indicating a value does not exist
• Given a value $x$ of type $t$,
  • Some($x$) is a value of type $t$ option, indicating a value exists and it is $x$
  • None is also a value of type $t$ option, indicating a value does not exist
• Note that a static type checker of OCaml does not allow an expression like

if ...
   [1;2;3] (* a list *)
else
   None

as the static types of the two branches do not match

• You instead have to write

if ...
   (Some([1;2;3])) (* a list option *)
else
   None

let rec subset_sum a v =
  if v = 0 then
    Some(List.map (fun _ -> 0) a)
  else if v < 0 then
    None
  else
    match a with
      [] -> None
    | a0 :: ar ->
       match subset_sum ar (v - a0) with
         Some(k1) -> Some(1 :: k1)
       | None -> match subset_sum ar v with
                   Some(k0) -> Some(0 :: k0)
                 | None -> None
;;

Test OCaml

int64_list_eq (subset_sum [1; 2; 3; 4; 5] 8) (Some([1; 1; 0; 0; 1]));
  int64_list_eq (subset_sum [33; 28; 56; 35; 19; 46; 25; 58; 17; 49; 33; 39; 37; 33; 24; 52] 233)
    (Some([1; 1; 1; 1; 1; 0; 1; 0; 0; 0; 0; 0; 1; 0; 0; 0]));
  int64_list_eq (subset_sum [30; 37; 46; 41; 14; 46; 44; 40; 46; 30; 46; 28; 33; 31; 56] 171)
    (Some([1; 1; 1; 0; 1; 0; 1; 0; 0; 0; 0; 0; 0; 0; 0]));
  int64_list_eq (subset_sum [47; 39; 15; 27; 52; 31; 39; 54; 20; 26; 38; 19; 35; 28] 440) None;
  int64_list_eq (subset_sum [16; 24; 13; 20; 24; 13; 11; 31; 29; 44] 222) None;
  flush_all ()
;;

Rust

• Similar to OCaml, Rust has a type called Option<T>, which can be used to represent either a value of $T$ or a special value indicating a value does not exist
• Given a value $x$ of type $T$,
  • Some($x$) is a value of type $T$ option, indicating a value exists and it is $x$
  • None is also a value of type $T$ option, indicating a value does not exist
• Note that a static type checker of Rust does not allow an expression like

if ... {
   vec![1, 2, 3] (* a vector *)
} else {
   None
}   

as the static types of the two branches do not match

• You instead have to write

if ... {
   Some(vec![1, 2, 3]) (* a vector *)
} else {
   None
}   

fn subset_sum(a : &[i64], v : i64) -> Option<Vec<i64>> {
    if v == 0 {
        Some(vec![0; a.len()])
    } else if v < 0 || a.len() == 0 {
        None
    } else {
        match subset_sum(&a[1..], v - a[0]) {
            Some(k1) => Some([vec![1], k1].concat()),
            None => match subset_sum(&a[1..], v) {
                Some(k0) => Some([vec![0], k0].concat()),
                None => None
            }
        }
    }
}

Test Rust

fn int64_list_opt_eq(a : Option<Vec<i64>>, b : Option<Vec<i64>>) {
    match a {
        None => match b {
            None => println!("OK"),
            Some(_) => println!("NG")
        },
        Some(x) => match b {
            None => println!("NG"),
            Some(y) => int64_list_eq(x, y)
        }
    }
}
    int64_list_opt_eq(subset_sum(&vec![1,2,3,4,5], 8), Some(vec![1, 1, 0, 0, 1]));
    int64_list_opt_eq(subset_sum(&vec![33, 28, 56, 35, 19, 46, 25, 58, 17, 49, 33, 39, 37, 33, 24, 52], 233),
                      Some(vec![1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0]));
    int64_list_opt_eq(subset_sum(&vec![30, 37, 46, 41, 14, 46, 44, 40, 46, 30, 46, 28, 33, 31, 56], 171),
                      Some(vec![1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]));
    int64_list_opt_eq(subset_sum(&vec![47, 39, 15, 27, 52, 31, 39, 54, 20, 26, 38, 19, 35, 28], 440), None);
    int64_list_opt_eq(subset_sum(&vec![16, 24, 13, 20, 24, 13, 11, 31, 29, 44], 222), None)