OCaml unexpected type

Question

I have to write a function to remove elements from a lazy list. Indexes of elements to be removed are in list xs.

I don't know where I should sort xs? When I try in this way I get "Error: This expression has type...".

type 'a llist = LNil | LCons of 'a * (unit -> 'a llist)

let rec remove xs ll =
let rec helper = 
    function
    | (_, i, LNil) -> LNil
    | (h::t, i, LCons(x, xf)) -> if h = i then helper (t, (i + 1), xf())
                                 else LCons(x, fun() -> helper (h::t, (i + 1), xf()))
    | ([], i, LCons(x, xf)) -> LCons(x, xf)
in helper (List.sort xs, 0, ll);;

Answer 1

List.sort from OCaml standard library has the following interface:

val sort : ('a -> 'a -> int) -> 'a list -> 'a list

That means, that it accepts a function and a list. The function should have type 'a -> 'a -> int, i.e., it takes two elements of arbitrary type 'a and returns a value of type int that defines the mutual order of the arguments. The second argument is a list of values, where each value has type 'a. A usual invocation of the sort function is:

List.sort compare [2;1;4;3]

So with this knowledge we can tackle with your program:

You invoke List.sort on xs this has two consequences:

1. type inference system concludes that xs is a function of type 'a -> 'a -> int.

2. The result of List.sort xs is a function of type 'a list -> 'a list. This is because, List.sort requires two arguments, but you provided only one.

Answer 2

(List.sort xs) is a function that takes a list & returns a list - as xs is supposed to be the function that sorts the element of the list; you miss to pass a list as arg.

...whereas a list is expected.