Different ways of declaring a function-CodePudding

When declaring a function, I've 3 different ways:

let f x = ...

let f = (fun x -> ...)

let f = function
    | ...  -> (pattern matching)

It's this last one that I don't fully understand how it works.

I was doing a function that, considering a list (we'll assume it has integers in it but could be anything), reverses it, pretty basic, but with a complexity of O(n). After struggling for an hour at least I check the answer, and it is written like this:

let reverse lst =
    let rec aux acc = function
          | [] -> acc
          | hd :: tl -> aux (hd :: acc) tl
    in
    aux [] lst

I thought that using the key word function was just another way of doing patter matching, but when I do this:

let reverse lst =
    let rec aux acc = 
        match aux with 
          | [] -> acc
          | hd :: tl -> aux (hd :: acc) tl
    in
    aux [] lst

It doesn't work, and idk why. On top of that, why can we add tl at the end of the first function? Isn't aux a single argument function?

CodePudding user response：

There are a few problems with this question. First, the code you give as the solution for reverse is not valid OCaml. It matches aux (which is a function) against list patterns. Most likely aux was supposed to be acc. But even so it doesn't seem right because it should have two arguments (the accumulated result and the input that still needs to be processed).

Second, your two code examples are the same. You seem to be saying that one works and one doesn't work. That doesn't make sense since they're the same.

IMHO you need to rewrite the question if you want to get a helpful answer.

CodePudding user response：

Ocaml uses currying, which means that a two-argument function is the same thing that a function whose return value is a function.

To define a two-argument function, you can combine all the ways you know of creating one-argument functions:

let f x y = x   y

let f x = (fun y -> x   y)

let f x = function
    | y -> x   y

let f = (fun x -> (fun y -> x   y))

let f = function
    | x -> function
        | y -> x   y

let f x = (let g y = x   y in g)

etc, etc.

All these definitions for f lead to the same result:

val f : int -> int -> int = <fun>

# f 3 4;;
- : int = 7

Note that the signature of f is:

val f : int -> int -> int = <fun>

If we added parentheses to better understand this signature, it would be this:

val f : int -> (int -> int) = <fun>

Meaning that f is a one-argument function whose return value is a one-argument function whose return value is an int.

Indeed, if we partially apply f:

# f 3;;
- : int -> int = <fun>

# let add_three = f 3;;
val add_three : int -> int = <fun>

# add_three 4;;
- : int = 7

The code you give at the end of your question is wrong. It's most likely intended to be this:

let reverse lst =
    let rec aux acc l = 
        match l with 
          | [] -> acc
          | hd :: tl -> aux (hd :: acc) tl
    in
    aux [] lst;;

val reverse : 'a list -> 'a list = <fun>

# reverse [1;2;3;4;5];;
- : int list = [5; 4; 3; 2; 1]