CODEWITHSUNDEEP
functional-programmingocamltype-systems
Swair
Swair

Reputation: 1513

What is the difference between function type ('a -> 'a) -> int -> 'a -> 'a and ('a -> 'a) -> int -> ('a -> 'a)?

When I write an Ocaml function to recursively compose the same function n times, I did this:

let rec compose f n = 
  (fun x -> if n = 1 then f x else ((compose f (n-1))) (f x));;

It gives the type 

val compose : ('a -> 'a) -> int -> 'a -> 'a = <fun>

what is the difference between type

('a -> 'a) -> int -> 'a -> 'a

and type

('a -> 'a) -> int -> ('a -> 'a)

?

How would a similar compose function look with the latter type?

Upvotes: 1

Views: 131

Answers (2)

user3240588
user3240588

Reputation: 1252

As an addition to @ivg's answer, here is a mistake i made. Consider these two functions which have the same type int -> int -> int. (;; added for pasting in the toplevel)

let f a b = 
  let ai = 
    Printf.printf "incrementing %d to %d\n" a (a + 1);
    a + 1 in
  b + ai;;

let f' a = 
  let ai = 
    Printf.printf "incrementing %d to %d\n" a (a + 1);
    a + 1 in
  function b -> b + ai;;

If you partially apply 

let f_1 = f 1;;
let f'_1 = f' 1;;

you'll see the difference. What I thought is that f does what f' does. In reality, Ocaml is eager but not so eager as to start evaluating away in partial function applications until it runs out of arguments. To point out the difference, it can make sense to write f''s type as int -> (int -> int).

Upvotes: 1

ivg
ivg

Reputation: 35210

There is no difference between them. But sometimes authors of libraries use parens to denote, that the computation is actually staged, so that it is better to apply it partially, so that you can get a more efficient function, rather then applying it every time. But from the type system perspective this functions are exactly the same, since -> type operator associates to the right.

Upvotes: 6

Related Questions