Dealing with unit in Ocaml

Question

So I have a function r which is supposed to apply a function to every element in the list provided it meets a given predicate, and return that list. i.e.

let p x = x > 2;;
let f x = x+1;;

r p f [1;2] => []

I am using a map function that applies a function to every element in a list and then returns that list. Thus my implementation for r is as follows

let r f p l = map f (map (fun x -> if (p x) then x) l );;

but if I attempt to call r like in the example above I get a type error because f and p are expressions for ints and it expected expression for units. Where did I go wrong?

Answer 1

First of all let me explain, why unit comes into play.

In OCaml if/then/else is not a statement, it is an expression, like ternary operator in C-like languages or like conditional expression in Python. Than means, that being an expression it always must have a value. You cannot just give an expression for the true branch, and omit the else branch, unless the value to the else branch is trivial and always known to a compiler. And the latter is only possible for the unit type. Since this type is inhabited with only one value, then if you true branch returns a value of type unit, compiler already knows what would return the false branch. That's why you can omit else part of the expression, that evaluates to unit. And the omission of the else part is satisfactory proof for the compiler that the whole expression has type unit. That means, that in expression if (p x) then x, compiler decided that x has type unit, because there is no else part.

Now to the task. map must return a value for each element of the list. It cannot skip or rearrange, or change the structure. For this there're other higher order functions called filter_map, concat_map, filter, etc.

But lets try to do something without leaving the original wording. So back to your example, we need do something in the else part. What we should return to designate that there is no value? We can return None that is a value of type option, e.g.,

if p x then Some x else None

Notice, that we also need to lift the then part to the option type. As a result we will have a list of type 'a option list. Then we need to filter it, removing Nones.

Other choice is to return an empty list (aka nil), instead of None:

if p x then [x] else []

Then we will have a 'a list list that can be easily transformed to 'a list with concat operation. Moreover, we can notice, that there is no need to create an intermediate list, we can apply f just in place (i.e., there is an opportunity for deforesting optimization here):

if p x then [f x] else []

And finally we have:

let r f p l = concat (map (fun x -> if p x then [f x] else []) l)

Later, you will discover, that both option and list are monads, and this trick with map and concat is actually the core operation for all monads, called bind and denoted as >>=. With this operator defined, we can write r function more elegantly:

let r f p l = l >>= fun x -> if p x then [f x] else []

where the bind operator can be implemented (inefficiently), as

let (>>=) x f = concat (map f x) 

But this all was functional mumbo-jumbo, practically, it is better just to use fold_left (as Jeffrey suggested), and accumulate your result in an auxiliary list, without forgetting to reverse it:

let r f p l = rev (fold_left (fun xs x -> if p x then f x :: xs else xs) [] l)

And in real-world programming, you will be using the standard library functions such as List.filter_map or List.concat_map for that.

Answer 2

The map function applies a function to every element of a list and returns the list of results. It always returns a list of equal length to the input list. So your problem statement doesn't make complete sense.

At a lower level, the expression if (p x) then x is only legitimate if x has type unit. I.e., the meaning of if b then e is the same as if b then e else (), and both sides of the if have to be the same type.

If you want to return a list of a different length than your input list, you'll need to use a fold function rather than map.