(*Problem 1*)
fun recursiveFromTo(low:int, high:int, func:int->'a, output:'a list) =
    let val value = func(low) in
        if low > high then output else
        recursiveFromTo(low+1, high, func, output @ [value])
    end;

fun fromTo(low:int, high:int) (func:int -> 'a) =
    if high < low then [] else
    recursiveFromTo(low, high, func, []);

(*Problem 2*)
(*Part i*)
fun recursiveHalve(inList: 'a list, oddList: 'a list, evenList: 'a list) =
    let val item = List.take(inList, 1) in
        if List.length(inList) = 1 then
            if List.length(oddList @ item) = List.length(evenList) then
                (evenList, oddList @ item)
            else
                (oddList @ item, evenList)
        else
        recursiveHalve(List.drop(inList, 1), evenList, oddList @ item)
    end;

fun halve(inList: 'a list) =
    if List.length(inList) = 0
    then ([], [])
    else recursiveHalve(inList, [], []);

(*Part ii*)
fun recursiveMerge(output: 'a list, list1: 'a list, list2: 'a list) =
if List.length(list1) = 0
then output @ list2
else if List.length(list2) = 0
then output @ list1
else recursiveMerge(output @ List.take(list1, 1), list2, List.drop(list1, 1));

fun merge(list1: 'a list, list2: 'a list) =
recursiveMerge([], list1, list2);

(*Problem 3*)
(*Part i*)
fun recursiveSplitAtLast(item: ''a, inList: ''a list, frontList: ''a list, backList: ''a list) =
    if List.length(inList) = 0
    then ([], [])
    else let val out = recursiveSplitAtLast(item, List.tl(inList), frontList, backList) in
        if #1 out = nil andalso item <> List.hd(inList)
        then ((#1 out), [List.hd(inList)] @ #2 out)
        else (([List.hd(inList)] @ #1 out), (#2 out))
    end;

fun splitAtLast(item: ''a)(inList: ''a list) =
    recursiveSplitAtLast(item, inList, [], []);

(*Part ii*)

fun recursiveSplitAtFirst (item: ''a, inList: ''a list, frontList: ''a list, backList: ''a list) =
    if List.length(inList) = 0
    then (frontList, backList)
    else if backList = nil andalso item <> List.hd(inList)
    then recursiveSplitAtFirst(item, List.tl(inList), frontList @ [List.hd(inList)], backList)
    else recursiveSplitAtFirst(item, List.tl(inList), frontList, backList @ [List.hd(inList)]);

fun splitAtFirst (item: ''a)(inList: ''a list) =
    recursiveSplitAtFirst(item, inList, [], []);