(* Sample midterm questions *) 


(* General form of question. Here is a function understand what it does *) 
fun foo ([], xs, ys) = (xs,ys) 
  | foo ((x,y)::rs, xs, ys) = foo(rs, x::xs, y::ys);

(* 

1) What is the type of foo ? 

2) Which of the following is a correct call to foo 
		
a) foo([1,2,3,4], [], [])
b) foo([(1,2), (3,4)], [1,2], [3,4])
c) foo([([1,2,3], [1,2])], [[1,2]], [[3,4]])
d) foo([(1,"a"),(2,"b")], ["a"], [2])

3) What is the result of 

foo([(["a","b"],["c","d"]),(["e","f"],["g","h"])],[],[["w","h"]])

*) 


(* General form of questions here is a grammar. Understand what it does *) 
(* Consider the following grammar 

E = T "-" E | T 
T = "0" | "1" 


Which of the following strings can be derived using this grammar: 

a) 0-1-1 
b) -1 
c) 1-1-1
d) -1-0-
 


*) 


(* General form: Express one higher order function as another *) 
(* Express map f using foldr *) 
fun mymap f = foldr (fn(x,l)=> f x :: l) [] ;


(* General form: Here is a piece of code in Scheme write it in ML 
or the opposite *) 

(* 
 
(define (foo f L) 
  (cond ((null? L) '())
	(else (cons (f (car L)) (foo f (cdr L))))))

*) 


(* What is the result of 
(foo (lambda (x) (+ x x)) '(1 2 3))
*) 


fun mlfoo(f,[]) = [] 
  | mlfoo(f,x::xs) = f(x)::mlfoo(f,xs);


(* Which well known higher order function is mlfoo ? *) 



(* Consider the following ML datatype for a binary tree *) 

datatype ('a,''b) bintree = Leaf of 'a
			  | Node of ('a,''b) bintree * ''b * ('a,''b) bintree;


(* what is the type of the following value *) 

val bar = Node(Node(Leaf 1, "a", Leaf 2), "ab", Leaf 3)

(* draw the tree given above *) 

(* what does the following function do ? *) 

fun foo1(Leaf n) = n 
  | foo1(Node (ltr,l,rtr)) = case (ltr,rtr) of 
				(Leaf l,Leaf r) => l+r 
			      | (Leaf l,rtr)   => foo1(rtr)  
			      | (ltr, Leaf r)  => foo1(ltr)
			      | (ltr,rtr)     => foo1(ltr) + foo1(rtr); 
		
(* what are the values of *) 

foo1(bar); 
val bar1 = Node(Node(Leaf 1, "a", Leaf 2), "ab", Node(Leaf 1, "b", Leaf 2));
foo1(bar1);

(* convert to tail recursive *) 
fun myf 0 = 0 
  | myf n = 3 + 2 * (myf(n-1) + myf(n-1));


(* what is the value of *) 
myf(3);

(* Write a tail recursive version *) 
fun myftr(0,k) = (0,k)
  | myftr(n,k) = myftr(n-1, 3 + 4*k);

(* write a foonew that takes one argument 
and uses footr to calculate the result *) 

fun myfnew n = let fun myftr(0,k) = (0,k) 
		     | myftr(n,k) = myftr(n-1, 3+ 4*k)
	       in 
		   myftr(n,0)
	       end;
    



(* foldl, foldr explained *) 


(* foldl folds from left to right *) 
fun foldl f b [] = b 
  | foldl f b (x::xs) = foldl f (f(x,b)) xs;

(* foldr folds from right to left *) 
fun foldr f b [] = b 
  | foldr f b (x::xs) = f(x, foldr f b xs);