-

open List;



(* 1. Functions takes a list l and an int n ; Outputs l where the indexes are offset by n places *)
 fun rotN(nil, n) = []
   | rotN(l, 0) = l
   | rotN(h::t, n:int) = if (n > 0) then 
   							rotN([last(t)]@rev(tl(rev(h::t))),n-1)
                         else
                         	rotN(t@[h], n+1);

(* function that takes a list l and an int k and returns
	 a list with the first k elements of l and a second list with the remaining elements *)

fun splitList(nil, k) = (nil, nil)
  | splitList(l, k) = (take (l, k), drop (l, k));


(* 3.) *)

fun posRemove (nil, k, l, count) = l
	| posRemove (h::t, k, l, count) = 
		if (count = 0) then 
			posRemove (t, k, l@[h], count+1)
		else if (count mod k <> 0) then 
			posRemove (t, k, l@[h], count+1)
		else
			posRemove(t, k, l, count+1);

fun posReWrap (l, k:int) = posRemove(l, k, nil, 0);


(* 4.) *)

(*function that find the nth fibonacci number: *)

fun fib n =
  if n < 3 then
    1
  else
    fib (n-1) + fib (n-2);

(* function that finds x number of fibonacci numbers where x is the length of the list, 
	but if the next fibonacci number is larger than the length of the list the function stops and 
	returns the list it has built up to that point *)

fun nFibs (~1, l, len) = l
	| nFibs (n, nil, len) = nFibs(n+1, [fib(n)], len)
	| nFibs (n, l, len) =  
		if (fib(n+1) > len andalso n <> len) then 
			nFibs(~1, l, len)
		else
			nFibs(n + 1, l@[fib(n)], len);

(* check if a number is in a list. 
could be made more efficient with binary search maybe since
the fibonaci list is sorted? *)

fun inList (x, nil, inL) = inL
	| inList(x, h::t, inL) =
		if (x = h) then
			inList(x, nil, true)
		else 
			inList(x, t, inL);

(* function that takes a list and returns the elements of the list whose index is not a 
	fibonacci number *)

fun remFibIndex(nil, fibList, l, count) = l
	| remFibIndex (h::t, fibList, l, count) = 
		if (inList(count, fibList, false) = false) then
			remFibIndex (t, fibList, l@[h], count + 1)
		else
			remFibIndex (t, fibList, l, count + 1);

(* wrapper function that just takes the list as specified and returns the list with elements
	whose original index wasn't a fibonaci number: *)

fun noFibIndex (l) = remFibIndex(l, nFibs(0, [], List.length(l)), [], 0);

(* 5.*)