Trying To Implement Sorted Insert Into An Int List: Expression Expected Type int list Has Type int list -> int list

I have the following function defined:

let rec sortedInsert (x: int) (lima: int list) =
match(lima) with
|[] -> []
|head::tail when x>head -> head::sortedInsert(x tail)
|head::tail -> x::sortedInsert(head tail);;

The idea is to insert a value x_i in a list [x_1,x_2,…,x_n], such that [x_1<=…x_(i-1)<=x_i<=x_(i+1)<=…].

The error that is raised is
“expression was expected to have type
‘int list’
but here has type
‘int list → int list’”

I understand, this to mean, that the expression returns a function, rather than an integer list due to the function call sortedInsert(x/head tail). But I don’t understand why?
Doesn’t it in the end terminate to an integer list due to my first clause?

Secondly, why did it expect “int list” as the returned type in the first place? It looks like a higher order function to me, that is of the type (int list → (int list → int list))?

And finally, how would I go about fixing this so it fits my purpose?

Welcome BrugerX!

So your implementation is actually spot on, and the only thing causing you trouble is syntax.
I actually get two errors with that code, and the two sort of help to explain the full situation. One error is as you said, and the other error is

This value is not a function and cannot be applied.

and the issue is here on this part

head::sortedInsert(x tail)

So what’s going on is that sortedInsert is a function of 2 inputs, an int, and an int list, but when the compiler sees sortedInsert(x tail), it sees the function being applied just one input. There’s two problems with this, one is that (x tail) makes the compiler mad, because it’s trying to call x as a function and pass in tail as input, which leads to one of the errors:

This value is not a function and cannot be applied.

Because of course x cannot be called as a function. Then the 2nd issue is that when take sortedInsert : int -> int list -> int list and call it just a single argument, you’re left with a function int list -> int list. So if I pulled out the variable names and just left the types in, that’s kind of like saying

int :: (int list -> int list)

and then that’s where the other error message comes from. It’s expecting the right-hand side of :: to be an int list, since the left-hand side is just an int, but the right hand side is actually an int list -> int list, which is an invalid type.

So really, all this came about because you have some parentheses wrapped around the argument list. I would suggest trying to avoid extra unneeded parentheses when learning F# syntax, because they can throw you off sometimes like this. Here are some valid ways you could write it

head::sortedInsert x tail
head::(sortedInsert x tail)
head::sortedInsert (x) (tail)
head::(sortedInsert) (x) (tail)
head::(sortedInsert x) tail
head::(sortedInsert) x tail
(head::sortedInsert x tail)

but you stumbled across one of the invalid ways of writing it. In F# (as opposed to C# for example) parentheses have nothing at all to do with calling a function, and are only used for groupings.

Ahhhh, I see!

I will try my best to remember not to use () unintentionally and unnecessarily.

Also, as it turns out, the algorithm also needed a little fix (in the rare case anyone sees this post and is trying the same):

let rec sortedInsert (x: int) (lima: int list) =
match(lima) with
|[] -> x::[]
|head::tail when x>head -> head::sortedInsert x tail
|head::tail -> x::sortedInsert head tail ;;```

BrugerX, I hope you don’t mind but as I’m still very much learning F# I thought I’d see if I could modify your code to work the way I’ve been learning it.

I’ve attached the code below.

Points of note:

  1. I’ve switched the parameters round so that the function can be more-easily partially applied.
  2. I’ve removed the parentheses from around “lima” in the match (not required).
  3. I’ve replaced the x:: with [ x ] which I think is easier to read (get an empty list and output a list with one item).
  4. I’ve made the code more generic by removing the types from the parameters (and used ‘a in the list definition).
  5. I’ve renamed the parameters, but that’s just a personal thing.
let rec sortedInsert (originalList : 'a list) newItem =
    match originalList with
    | [] -> [newItem]
    | head::tail when newItem > head -> head::sortedInsert tail newItem
    | head::tail -> newItem::sortedInsert tail head

I would be interested in hearing your thoughts, and to learn from anyone if my changes have made the code worse in some way.

Notes:

  1. This function assumes a sorted original list – don’t know yet how to check and report/fail/etc. if not.
  2. I don’t know if “newItem > head” (greater than) is better or worse than “newItem >= head” (greater than or equal to) in this case.