How would I insert an integer into a list pile in OCaml?

Question

Running insert ls n should return a list of piles from taking ls and inserting n so that either n has been added to the head of the first pile in ls whose previous head is greater than or equal to n, or if it doesn't exist, a new pile containing just n is added to the end of ls. For example,

insert [[4]; [5]] 3 = [[3;4]; [5]]
insert [[2]; [6]] 4 = [[2]; [4;6]]
insert [[3]] 4 = [[3]; [4]]

Basically, I'm trying to use the sort helper function that appends to the list if the element is less than the first in the list, and then in that case to just return the rest of the list.

let rec insert ls n =
  match n with
    | [] -> [x]
    | y::ys -> if x < y then x::y::ys else y::insert x ys;;

let rec sort n =
  match n with
    | [] -> []
    | x::xs -> insert x (sort xs);;

Answer 1

You keep confusing the order and type of arguments in your insert function. In your text description and following from the examples section, insert has type 'a list list -> 'a -> 'a list list, but when you try to write your insert function, you match the element n with a list. In the same manner, when you call insert from sort you pass the element as the first argument.

Next, your insert function shall return a list of lists, but in the first branch of your match, [] -> [x], you return just a list. In addition, there is no x variable bound in this match or anywhere else, probably you meant n?

Finally, when you compare the first element of the input list with the element n you compare the whole pile, instead of the head of the pile.

So let's try to rectify these problems, first of all, we have to match on ls instead of n,

let rec insert ls n = 
  match ls with 
(*      ^^
     ls not n! *)

Next, if we have an empty input, then we need to return a list containing a single pile, where a pile is a list itself,

  | [] -> [[n]] (* a list containing a list with a single element `n` *)

Finally, when we match on the head of the input list, we have to keep in mind that the head is the list itself, i.e., a pile, so we need to unpack it as well,

  | (x::xs)::ys -> 
 (* ^^^^^^^ 
    here x is the head of the pile, and x::xs is the whole pile *)

and pack it back,

if n < x then (n::x::xs)::ys else (x::xs)::insert ys n
(*            ^^^^^^^^^^          ^^^^^^^
             extended pile      intact pile         *)

The next step would be to make the match complete, i.e., to think what to do when the pile is empty itself (could it be?) and what to do when x is equal to n.