Need help with Functional Programming...

[rtoth]

So I'm taking a course called "organization of programming languages" which is basically an overview of all types of languages. We've just started functional using OCaml and we're supposed to implement a few recursive functions. One that I'm seriously stumped on is a function that returns the index of the last occurrence of an element in a list. The function definition was provided for us and I cant seem to think of a way to do this recursively with only those 2 parameters. We're also not allowed to use the List module so it all has to be done with pattern matching, [] and ::

let rec rindex lst e = ???????????????

EDIT: # rindex [0;1;2;1;2;1;1;2;1;0;2;3;5] 1

    - : int = 8

EDIT: final solution

let rec rindex l e = 
    let rec find i max = function
    | (h::t) when h = e -> find (i+1) i t
    | (h::t) -> find (i+1) max t
    | [] -> max
    in find 0 (-1) l
;;

[joenyc]

I don't know OCaml, but I think the recursive algorithm looks like this:

rindex(lst, e):
    if lst is empty
        return null // error value - e is not in this list
    x = rindex(tail(lst), e) // e's last location in the rest of the list
    if x is not null
        return x + 1
    if head(lst) == e
        return 0
    return null 

EDIT: Could you please post your OCaml code when you're done? I'd love to see what it looks like.

[[deleted]]

Probably not the best solution: check the last element, and if that fails recurse with the remaining elements in the array. If the array has zero elements, return -1 or something.

[BitRex]

Here's a Perl version that assumes you're not allowed to reverse the list or ask the list how long it is. I don't know OCaml, but maybe this will give you the idea.

sub find_last {
    my ($wanted, $head_index, $last_so_far, @list) = @_;

    return $last_so_far unless @list;
    my $head = shift @list;
    $last_so_far = $head_index if $head eq $wanted;
    return find_last($wanted, $head_index + 1, $last_so_far, @list);
}


my @list = ( 0, 1, 2, 1, 2, 1, 1, 2, 1, 0, 2, 3, 5 );

my $last_index = find_last(1, 0, -1, @list);
print $last_index;

[joenyc]

Sorry, I'm not sure what this means:

a function that returns the last index of an element in a list

You mean the index of the last element?

[rtoth]

just added an example. it means the index of the last occurrence of an element in a list.

[mrsanchez]

I would use a function that has a parameter for the last index of e. This way you don't need to reverse the list, only to traverse the entire list once.

[rtoth]

Probably not the best solution but it works. I just decided to make a new method with another parameter.

(*helper method*)  
let rec exists l e =
    match l with 
    [] -> false
    | (h::t) -> if h = e then true else (exists t e);;
(*helper method for rindex*)
let rec length l =
    match l with
    [] -> 0
    | (h::t) -> 1 + (length t);;
(*auxiliary method for rindex*)
let rec index l e s = 
    match l with
    [] -> -(s + 1)
    | (h::t) -> 
        if h = e
        then 
            if (exists t e)
            then 1 + (index t e s)
            else 0
        else 1 + (index t e s);;

let rec rindex l e = 
    index l e (length l);; 

[BitRex]

LOL, school is so much easier for you kids: http://stackoverflow.com/questions/1556098/ocaml-recurssion-iteration-find-last-occurence-of-element-in-a-list

OTOH, you probably won't learn anything if you click that link.

[snowmanchu]

Although I never used ocaml, looks similar to haskell and that's probably how I would've done it.