[Caml-list] really HO Functions

[Caml-list] really HO Functions

[Radu Grigore]

For this message I'll classify functions on "levels" based on how many
nested parenthesis are needed to represent their type.

Functions of level 0 (e.g. int -> int, char -> int -> int, ...) are
the most used in programming. In widespread languages like C#, Java
and C++ they are almost the only kind of functions used.

Functions of level 1 (e.g. ('a -> 'b) -> ('b -> 'c) -> ('a -> 'c)) are
used a lot when programming in a functional language. They are also
the ones that appear in examples and tutorials written for imperative
programmers. This category includes fold, iter, map, composition.

However a language like OCaml allows N to go up as much as you want.
My question is: are there functions of level >= 2 used in practice
(e.g. (('a -> 'b -> 'a) -> 'a -> 'b list -> 'a) -> 'c)? If so, are
there any typical ones that appear in many applications (maybe not as
widespread like map & company but at least of comparable usefulness)?
One example of a level 2 function (stolen from a recent post by Jon
Harrop) is this:
  let sum fold = fold (+);;

regards,
radu

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

RE: [Caml-list] really HO Functions

[Jacques Carette]

The best answer is from Chris Okasaki in
Even Higher-Order Functions for Parsing or Why Would Anyone Ever Want To Use
a Sixth-Order Function? by Chris Okasaki. Journal of Functional Programming,
8(2):195-199, March 1998.

Abstract: We illustrate the use of third-, fourth-, fifth-, and even
sixth-order functions with examples taken from a combinator parsing library.


Available at http://www.eecs.usma.edu/Personnel/okasaki/jfp98.ps

Jacques

-----Original Message-----
From: owner-caml-list@pauillac.inria.fr
[mailto:owner-caml-list@pauillac.inria.fr] On Behalf Of Radu Grigore
Sent: September 29, 2004 2:48 PM
To: caml-list
Subject: [Caml-list] really HO Functions


For this message I'll classify functions on "levels" based on how many
nested parenthesis are needed to represent their type.

Functions of level 0 (e.g. int -> int, char -> int -> int, ...) are the most
used in programming. In widespread languages like C#, Java and C++ they are
almost the only kind of functions used.

Functions of level 1 (e.g. ('a -> 'b) -> ('b -> 'c) -> ('a -> 'c)) are used
a lot when programming in a functional language. They are also the ones that
appear in examples and tutorials written for imperative programmers. This
category includes fold, iter, map, composition.

However a language like OCaml allows N to go up as much as you want. My
question is: are there functions of level >= 2 used in practice (e.g. (('a
-> 'b -> 'a) -> 'a -> 'b list -> 'a) -> 'c)? If so, are there any typical
ones that appear in many applications (maybe not as widespread like map &
company but at least of comparable usefulness)? One example of a level 2
function (stolen from a recent post by Jon
Harrop) is this:
  let sum fold = fold (+);;

regards,
radu

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives:
http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ:
http://caml.inria.fr/FAQ/ Beginner's list:
http://groups.yahoo.com/group/ocaml_beginners

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] really HO Functions

[Jon Harrop]

On Wednesday 29 September 2004 19:48, Radu Grigore wrote:
> My question is: are there functions of level >= 2 used in practice
> (e.g. (('a -> 'b -> 'a) -> 'a -> 'b list -> 'a) -> 'c)?

I've just had a look through some real programs that I've written and the 
answer is definitely yes. I use them quite a lot. For >2 they are mainly 3, 
sometimes 4 and I haven't seen any >4.

> If so, are 
> there any typical ones that appear in many applications (maybe not as
> widespread like map & company but at least of comparable usefulness)?

I seem to use them when I write generic functions which are later specialised.

> One example of a level 2 function (stolen from a recent post by Jon
> Harrop) is this:
>   let sum fold = fold (+);;

Funny to think that this function is still state-of-the-art Java and C++. ;-)

Cheers,
Jon.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] really HO Functions

[Marcin 'Qrczak' Kowalczyk]

Jon Harrop <jon@jdh30.plus.com> writes:

>> My question is: are there functions of level >= 2 used in practice
>> (e.g. (('a -> 'b -> 'a) -> 'a -> 'b list -> 'a) -> 'c)?
>
> I've just had a look through some real programs that I've written and the 
> answer is definitely yes. I use them quite a lot. For >2 they are mainly 3, 
> sometimes 4 and I haven't seen any >4.

http://citeseer.ist.psu.edu/okasaki99functional.html

-- 
   __("<         Marcin Kowalczyk
   \__/       qrczak@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] really HO Functions

[Diego Olivier Fernandez Pons]

    Bonjour,

> > > My question is: are there functions of level >= 2 used in
> > > practice (e.g. (('a -> 'b -> 'a) -> 'a -> 'b list -> 'a) -> 'c)?
> >
> > I've just had a look through some real programs that I've written
> > and the answer is definitely yes. I use them quite a lot. For >2
> > they are mainly 3, sometimes 4 and I haven't seen any >4.
>
> http://citeseer.ist.psu.edu/okasaki99functional.html

I would't call that a real example. It is just an exercice on HOF and
combinators more than a really practical application.


        Diego Olivier

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] really HO Functions

[Michal Moskal]

On Wed, Sep 29, 2004 at 09:48:03PM +0300, Radu Grigore wrote:
> For this message I'll classify functions on "levels" based on how many
> nested parenthesis are needed to represent their type.
[...]
> (e.g. (('a -> 'b -> 'a) -> 'a -> 'b list -> 'a) -> 'c)? If so, are
> there any typical ones that appear in many applications (maybe not as
> widespread like map & company but at least of comparable usefulness)?
> One example of a level 2 function (stolen from a recent post by Jon
> Harrop) is this:
>   let sum fold = fold (+);;

You may have a look at:

  http://tomasz.ii.uni.wroc.pl/ComplexityOfML.pdf

for some statistical data regarding type sizes and orders.

-- 
: Michal Moskal :: http://www.kernel.pl/~malekith :: GCS !tv h e>+++ b++
: ::: Logic is a nice contrast to the Real World. :: UL++++$ C++ E--- a?

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] really HO Functions

[Jean-Baptiste Rouquier]

Radu Grigore wrote:

>For this message I'll classify functions on "levels" based on how many
>nested parenthesis are needed to represent their type. (...)
>
>My question is: are there functions of level >= 2 used in practice
>(e.g. (('a -> 'b -> 'a) -> 'a -> 'b list -> 'a) -> 'c)?

In my soon-to-be-released library to read and write configuration files, I have
one example of this. Basically, the function reading a file (actually a method)
has on optional argument that allows the user to override the default behaviour
in case there is an error.
The argument is itself a function that get all the available information as
arguments, including a value of type (out_channel -> unit) that pretty print
(with module Format) a part of the read AST to the given output channel.
So I have
    method read : ... -> ... ->
      ?on_type_error : (... -> ... -> (out_channel -> unit) -> ... -> unit) ->
      string -> unit

Out of curiosity, may I ask why you're looking for such functions ?
Regards,

-- 
Jean-Baptiste Rouquier

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] really HO Functions

[Radu Grigore]

Thanks everyone who answered.

On Wed, 29 Sep 2004 22:48:11 +0200 (CEST), Jean-Baptiste Rouquier
<jrouquiethearchiveshouldhaveafewantispamtricks@ens-lyon.fr> wrote:

> Out of curiosity, may I ask why you're looking for such functions ?

I am learning OCaml now. The last two-three days I've written a small
prototype; then I have reviewed it and one of the observations was
that it contains no second-order function.

Possible reasons:
1. higher order functions are hard (intellectually unmanageable)
2. HOFs are not needed in practice above a certain order 
3. failure to recognize places where a HOF is needed (beyond the
standard examples in tutorial).

Number 3 was what prompted me to ask the question: a few examples
always help. Unfortunately I didn't yet had time to read the cited
articles :(.

-- 
regards,
 radu
http://rgrig.idilis.ro/

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] really HO Functions

[John Prevost]

On Sat, 2 Oct 2004 08:02:52 +0300, Radu Grigore <radugrigore@gmail.com> wrote:
> I am learning OCaml now. The last two-three days I've written a small
> prototype; then I have reviewed it and one of the observations was
> that it contains no second-order function.
> 
> Possible reasons:
> 1. higher order functions are hard (intellectually unmanageable)
> 2. HOFs are not needed in practice above a certain order
> 3. failure to recognize places where a HOF is needed (beyond the
> standard examples in tutorial).
> 
> Number 3 was what prompted me to ask the question: a few examples
> always help. Unfortunately I didn't yet had time to read the cited
> articles :(.

I highly recommend keeping at it and joining the beginners list (if
you haven't already).  Making and using higher-order (as in 2nd or
3rd, at least) functions is one of those things that you start doing
after you've been using a functional language for a while.  It does
dramatically simplify your life when you start doing it, but it's not
immediately obvious how you'll use it.

Really, this is why people should try to gain experience with a
variety of languages: it greatly expands the variety of techniques
that you think of when trying to solve a problem.  The experience will
impact how you program in every language, whether or not it has those
tools.

In any case, good luck!

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] really HO Functions

[Seth J. Fogarty]

On Sat, 2 Oct 2004 02:33:43 -0400, John Prevost <j.prevost@gmail.com> wrote:
> On Sat, 2 Oct 2004 08:02:52 +0300, Radu Grigore <radugrigore@gmail.com> wrote:
> > I am learning OCaml now. The last two-three days I've written a small
> > prototype; then I have reviewed it and one of the observations was
> > that it contains no second-order function.
> >
> > Possible reasons:
> > 1. higher order functions are hard (intellectually unmanageable)
> > 2. HOFs are not needed in practice above a certain order
> > 3. failure to recognize places where a HOF is needed (beyond the
> > standard examples in tutorial).
> >
> > Number 3 was what prompted me to ask the question: a few examples
> > always help. Unfortunately I didn't yet had time to read the cited
> > articles :(.
> 
> I highly recommend keeping at it and joining the beginners list (if
> you haven't already).  Making and using higher-order (as in 2nd or
> 3rd, at least) functions is one of those things that you start doing
> after you've been using a functional language for a while.  It does
> dramatically simplify your life when you start doing it, but it's not
> immediately obvious how you'll use it.

I've identified two places I've used HOF's, for really rather different reasons.
1) Modularity. This is probably obvious, but the hardest one to do,
and probably the more useful location. I rarely use more than
second-order functions for htis, and it is very often a refactoring.
"Oh look, in this parser we are evaluating, unwrapping ints, and
error-checking in eight places, the only difference is the function we
apply to the integers afterwards. Time for an HOF."

2) Abstraction. These are places I could have hard-coded the functions
I ended up passing in, but didn't so that the algorithm was very
obvious in the code. This allows someone to look at that one chunk of
code and go "alright, so that's the algorithm. How the specifics work
I don't know, but the general overview is independent of the rest of
the code". This may just be me, and is certainly NOT the usual use of
HOFs.

-- 
Seth Fogarty             sfogarty@[gmail.com|rice.edu|livejournal]
Neep-neep at large    AIM: Sorrath
"I know there are people in this world who do not love their fellow
human beings - and I hate people like that" --Tom Lehrer.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

RE: [Caml-list] really HO Functions

[Harrison, John R]

| I've just had a look through some real programs that I've written and
the 
| answer is definitely yes. I use them quite a lot. For >2 they are
mainly 3, 
| sometimes 4 and I haven't seen any >4.

I haven't actually checked, but I suspect I'd find something similar.
There may
be an interesting psychological observation to be made here: most people
find
very high-order functions intellectually unmanageable.

Something similar is usually acknowledged in logic with respect to long
quantifier alternations (for all x there exists a y such that for all z,
...).
I believe I once saw a provocative claim by Kreisel that most
mathematical
concepts are in fact only invented in order to hide complicated
quantifier
alternations.

John.

-----Original Message-----
From: owner-caml-list@pauillac.inria.fr
[mailto:owner-caml-list@pauillac.inria.fr] On Behalf Of Jon Harrop
Sent: Wednesday, September 29, 2004 3:31 PM
To: caml-list
Subject: Re: [Caml-list] really HO Functions


On Wednesday 29 September 2004 19:48, Radu Grigore wrote:
> My question is: are there functions of level >= 2 used in practice
> (e.g. (('a -> 'b -> 'a) -> 'a -> 'b list -> 'a) -> 'c)?

I've just had a look through some real programs that I've written and
the 
answer is definitely yes. I use them quite a lot. For >2 they are mainly
3, 
sometimes 4 and I haven't seen any >4.

> If so, are 
> there any typical ones that appear in many applications (maybe not as
> widespread like map & company but at least of comparable usefulness)?

I seem to use them when I write generic functions which are later
specialised.

> One example of a level 2 function (stolen from a recent post by Jon
> Harrop) is this:
>   let sum fold = fold (+);;

Funny to think that this function is still state-of-the-art Java and
C++. ;-)

Cheers,
Jon.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives:
http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ:
http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners