CODEWITHSUNDEEP
listrecursiondictionaryocaml
T.Woody
T.Woody

Reputation: 1228

OCaml: Returning Full List after Change to Element

Context:

In , when taking a full list in as a parameter, the method change is suppose to iterate through the list, and if a search is successful for a variable in the list, then we change that variable's binding to another value. Right now, I have the code at the bottom that does everything correctly, except returning the full list.

For clarity sake, this list should be best thought of as a dictionary that contains tuples.

Question:

How can my expression save the list that is being taken in, and return it, while iterating through it? In regards to the identified problem (can be see below), that only part of the list is being returned: Is this a fundamental flaw in the expression, or is this an easy fix? If this is an easy fix, what can be added to throw that in for the final return?

Code:

let rec change key value dict =
  match dict with
    | [] -> [(key, value)] (*Adding to the dictionary*)
    | (a,b) :: dict -> if compare a key = 0 then (a, value)::dict      (*changing value*)
                       else                      change key value dict (*continue search*)
;;

EXAMPLES OF CODE:

# let list = [(1,2);(4,2);(2,1)];;
val list : (int * int) list = [(1, 2); (4, 2); (2, 1)]
# change 2 3 list;;
- : (int * int) list = [(2, 3)]
# change 1 1 list
  ;;
- : (int * int) list = [(1, 1); (4, 2); (2, 1)]
# change 4 1 list
  ;;
- : (int * int) list = [(4, 1); (2, 1)]
# change 7 1 list
  ;;
- : (int * int) list = [(7, 1)]

ANSWER:

let rec change key value dict =
  match dict with
    | [] -> (key, value)::dict (*Adding to the dictionary*)
    | (a,b) :: dict -> if compare a key = 0 then (a, value)::dict (*changing value*)
                       else (a,b)::change key value dict (*continue search*)
;;

If you see the above, in the fifth line, at the else statement, there is an addition of (a,b):: which does the recursion in the correct way.

Upvotes: 0

Views: 584

Answers (1)

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66813

It might help to think more like a functional programmer. What I'm trying to say is that you should stop thinking of it as a change to the old list. You should think of it as a whole new list.

In words, you might want to think something like this:

  • If the list is empty, the result is empty
  • If the list looks like hd :: tl, the result depends on what hd looks like.
  • In particular, if hd is something I'm supposed to modify, the result looks like the modified hd followed by a modified tl.
  • But if the head isn't something I'm supposed to modify, the result looks like hd followed by a modified tl.

If you think this way, the code should be pretty easy to write.

Update

It appears that you have some invariants on your dictionary that I didn't take into account. If you know dictionary entries are unique the third case changes to returning a modified hd followed by the old tl.

If you also want to add the entry if it doesn't appear, the first bullet changes to return a list of your one pair (rather than returning an empty list).

I'm trying to illustrate a way of thinking more functionally (possibly unsuccessfully, but that's what I'm trying :-).

Upvotes: 1

Related Questions