CPSC 370: Functional and Logic Programming

How many partial binary boolean functions are there?
There are 3⁴=81 such functions
The triangular numbers are the number of dots in a triangle that is n rows deep and n columns wide. Thus t(4) is 1+2+3+4=10. Write a standard ML function to compute t(n).
```
fun triangle 0 = 0
  | triangle n = n + triangle (n-1) ;
    
```
or (tail-recursively)
```
fun triangle n = let
    fun t2 (0,a) = a
      | t2 (n,a) = t2(n-1,n+a)
in t2 (n,0) end
  
```
```
   .
   ..   .
   ...  ..  .
   .... ... .. .
    
```
The pyramidal numbers are the number of dots in a pyramid that is n rows long and n columns wide and n columns high. Thus p(4) is 1+3+6+10=20. Write a standard ML function to compute p(n).
```
fun pyramid 0 = 0
  | pyramid n = triangle n + pyramid (n-1) ;
```

Generalize.

fun nDimSimplex (_,0) = 0
  | nDimSimplex (0,_) = 1
  | nDimSimplex (k,n) = nDimSimplex (k-1,n) + nDimSimplex(k,n-1) ;

Guesstimate the running time behaviour of the winning and losing functions discussed in class.
See this .pdf file for a carefully worked solution.
Write winning and losing functions for Doubling Nim.
A solution can be found on galaxy.unbc.ca at /export/research/casper/cpsc370/doublingNim.sml.

This solution found there is an exponential search rather than something clever.
The function defined by
val f = n => if n>100 then n-10 else f(f(n+11))
has value max(n-10,91).
We prove this by strong induction on the quantity 101-n.

The base case is 101-n ≤ 0. Here, clearly, the claim holds as the function returns n-10 which is greater than or equal to 91.

Now, inductively, suppose that the claim holds for all 101-n less than 101-k, that is, for all n > k.

If 0 ≤ 101-k ≤ 11, we have that f(k) = f(f(k+11)) = f(k+11-10) = f(k+1) which by our induction hypothesis is 91.

If on the other hand 11 < 101-k, then f(k) = f(f(k+11)) = f(91) by our induction hypothesis = 91.