Insert number into sorted list using List.fold_right

zhxo49 0
Viewed 59

I am trying to insert a number x into a sorted list l using Ocaml's List.fold_right and return the list with the inserted element. I have figured out a way to insert it if the element is to go at the front of the list or in the middle of the list, however I cannot figure out how to code the case where the element is larger than every element in the list and thus must go at the end.

Here is what I have so far:

let insert_number (x: int) (l: int list): int list =
  List.fold_right l ~f:(
    fun cur -> fun acc -> 
      if x < cur then cur::x::accum 
      else cur::accum
  ) ~init: []

Using this with a test case like:

insert_number (3) ([1; 2; 4]);;
- : int list = [1; 2; 3; 4]

gives the correct answer. However, with a test case like this:

insert_number (3) ([1; 2]);;
- : int list = [1; 2]

the number is not inserted because it should be added to the end of the list.

Could someone help me understand how I am supposed to integrate this case into the function used with List.fold_right.

fold ocaml
4 Answers

One way to look at List.fold_right is that it looks at each element of the list in turn, but in reverse order. For each element it transforms the current accumulated result to a new one.

Thinking backward from the end of the list, what you want to do, in essence, is look for the first element of the list that's less than x, then insert x at that point.

So the core of the code might look something like this:

if element < x then element :: x :: accum else element :: accum

However, all the earlier elements of the list will also be less than x. So (it seems to me) you need to keep track of whether you've inserted x into the list or not. This makes the accumulated state a little more complicated.

I coded this up and it works for me after fixing up the case where x goes at the front of the list.

Perhaps there is a simpler way to get it to work, but I couldn't come up with one.

Jeffrey Scofield0

A fold works by passing along a set of state as it iterates over each element in a list (or other foldable data structure). The function passed in takes both the current element and that state.

I think you're really really close, but you need as Jeffrey suggests a boolean flag to indicate whether or not the value has been inserted. This will prevent multiple insertions and if the flag is still false when the fold is done, we can detect that and add the value to insert.

This match also serves the purpose of giving us an opportunity to discard the no longer needed boolean flag.

let insert v lst =
  match List.fold_right 
    (fun x (inserted, acc) -> 
       if v > x && not inserted then (true, x::v::acc) 
       else (inserted, x::acc))
    lst
    (false, []) with
  | (true, lst) -> lst
  | (_,    lst) -> v::lst
userRb2210

As I alluded to in a comment, it's possible to avoid the extra state and post-processing by always inserting the element and effectively doing a "local sort" of the last two elements:

let insert_number x l =
  List.fold_right (
    fun cur -> function
      | [] when x > cur -> [cur; x]
      | [] -> [x; cur]
      | x::rest when x > cur -> cur::x::rest
      | x::rest -> x::cur::rest 
  ) l []
glennsl0

Also, since folding doesn't seem to actually be a requirement, here's a version using simple recursion instead, which I think is far more comprehensible:

let rec insert_number x = function 
  | [] -> [x]
  | cur::rest when cur > x -> x::cur::rest
  | cur::rest -> cur::insert_number x rest
glennsl0
Related