Composite functions in ocaml

Question

How can I define a composite function in a functional language, in particular with Ocaml? For example, if I write a function that calculates the negation of the result of another function, that is: not(f(x)) where f(x) returns a boolean. How can I define it?

Answer 1

Given some function f, that has the type:

f: 'a -> bool

you want to be able to generate another function to wrap it to negate the result. Let's consider the type for this new function, let's call it negated (I'm not using not since it is the name of a builtin):

negated: ('a -> bool) -> 'a -> bool

Why is this the type? Why not 'a -> bool? Well remember, we want this new function to take in an existing function and return a new function with the same type that does something different. To see it clearer, you can think of it like this: ('a -> bool) -> ('a -> bool) which is equivalent.

So now given these constraints, how can we write the negated function?

let negated f = ??

Well we first have to consider that this function needs to return a function:

let negated f = (fun x -> ??)

What next? Well, we know that the new function we create should call our wrapped function with the argument and negate it. Let's do that, call the function with the argument: f x, and negate it: not (f x). That gives us the final function definition:

let negated f = (fun x -> not (f x))

Let's see it in action:

# let f x = x < 5;;
val f : int -> bool = <fun>
# f 2;;
- : bool = true
# f 8;;
- : bool = false
# let negated f = (fun x -> not (f x));;
val negated : ('a -> bool) -> 'a -> bool = <fun>
# let g = negated(f);;
val g : int -> bool = <fun>
# g 2;;
- : bool = false
# g 8;;
- : bool = true

Answer 2

I'm not sure exactly how far you're looking to go here — the code you wrote will work fine. So I'll give a simple step-by-step on how you write this stuff from scratch. Simple negation is just:

let not = function
  | true -> false
  | false -> true

You can how write not (f x) and it will give you the negation of the result of f x.

For a function that composes functions, you can use:

let comp f g x = f (g x)

So then we can do:

let even n = match n mod 2 with
  | 0 -> true
  | _ -> false

let odd = comp not even

Answer 3

Wow, what's with all of these overly complicated answers? What's wrong with:

let compose f g x = g (f x)

To get your g(x) = not(f(x)), assuming you have an f : 'a -> bool:

let g = compose not f

Additionally, you can do cool stuff like:

let composite_function =
   let id x = x in
   let transforms = [
      (fun n -> n + 1);
      (fun n -> n * 2);
      (fun n -> n * n)
   ] in
   List.fold_left compose id transforms

Now the composite_function has type int -> int, and its effective definition is:

let composite_function n =
   let n2 = (n + 1) * 2 in
   n2 * n2

EDIT: Oh, I guess Chuck actually did do this. I probably shouldn't have just skimmed. In any case, I happen to like folding over the compose function, so I'll keep this up. :p