CODEWITHSUNDEEP
typesocaml
Mashpa
Mashpa

Reputation: 61

Understanding the type of the following function

I wrote a merge_sorted function in OCaml, which takes a comparison function and two sorted lists and merges them together. I am trying to understand why the type of this function is

('a -> 'a -> bool) -> 'a list -> 'a list -> 'a list

and not 

('a -> 'a -> bool) -> 'a list

since it just returns a list. Below is my code for the merge_sorted function

let rec merge_sorted lt a b = 
    match a with 
    | [] -> b
    | h::t -> match b with
            | []-> a 
            | hh::tt -> if (lt h hh) 
                        then h::merge_sorted lt t b 
                        else hh::merge_sorted lt a tt;;

Upvotes: 1

Views: 72

Answers (1)

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66823

The function takes three arguments of types 'a -> 'a -> bool, 'a list, and 'a list. It returns a value of type 'a list. The type of a function (when defined in curried form as yours is) consists of the argument types, separated by ->, followed by the return type.

Thus the type really is ('a -> 'a -> bool) -> 'a list -> 'a list -> 'a list. The first two 'a lists are the second and third argument types. The last 'a list is the return type.

This isn't just a notational convention. Your function actually accepts a comparison function (of type 'a -> 'a -> bool) and returns a function of two arguments. The returned function accepts a list (of type 'a list) and returns a function. And so on.

Upvotes: 2

Related Questions