CODEWITHSUNDEEP
ocaml
King David
King David

Reputation: 43

OCaml swapping elements in a list

I'm trying to swap two elements in a list, not really sure why mines not working.

The correct implementation should do the following:

list_swap_val [5;6;7;3] 75 => [7;6;5;3] 
list_swap_val [5;6;3] 7 5 => [7;6;3]

Here's two different implementations I've tried but both seem to just return the original list

let rec list_swap l u v =
    match l with
   |[] -> []
   |h::t -> if h = u then u::(list_swap t u v)
            else if h = v then v::(list_swap t u v)
            else h::(list_swap t u v) ;;

I also tried to do the above but with while in the match statements instead of using if, but both are not working. Where am I going wrong? Thanks for any help

Upvotes: 1

Views: 3140

Answers (3)

Anatole Dahan
Anatole Dahan

Reputation: 41

as said above, you forgot to swap. You can also use List.map :

let swap u v n = match n with
     |x when x = u -> v
     |x when x = v -> u
     |_ -> n;;
let list_swap l u v = List.map (swap u v) l;;

This calls the function "swap u v" (thanks to partial evaluation) on every element in the list "l".

However, this hides the recursive call and you should know map isn't tail-recursive. If you want to use map and have tail recursivity :

let list_swap l u v = List.rev (List.rev_map swap (u v) l);;

"rev_map" is the same as "map" except it reverses the list at the same time, and it is tail recursive. So you reverse the list once again afterwards. "rev" is also tail recursive !

Upvotes: 1

Thomash
Thomash

Reputation: 6379

As coredump- wrote you can factorize it, but you can go even further and notice that this is a map.

let swap u v x = if x = u then v else if x = v then u else x
let list_swap u v = List.map (swap u v)

Upvotes: 4

coredump
coredump

Reputation: 38809

You forgot to actually swap values: when you see a u, the first element of your returned list should be v. Here, it is as-if you build h::(list_swap t u v) in all cases. By the way, you can factorize the recursive call, which gives you finally this definition:

let rec list_swap l u v =
  match l with
    | [] -> []
    | h::t -> (if h = u then v 
                else if h = v then u 
                  else h)::(list_swap t u v);;

Upvotes: 4

Related Questions