Hi all, I'm working on a type-based side effect analysis for a Haskell-like language, and need to test it against some more higher order functions. The situation is a bit icky because it uses bounded quantification and various related issues (ie covariance vs contravariance) only come into play when dealing with functions of order >= 3. Trouble is, the vast majority of useful higher order functions that I can think of are of order 2. Oh, I can certainly invent toys like: order3 f = f succ order4 b f = if b then f else order3 .. and so on, but I'm left feeling unsatisfied. I vaguely remember a paper called something like "Is there any use for a seventh order function?", but I forget why they were used, and I can't find it on Google, or ACM or any of the other likely places. Does anyone have any examples of code (in whatever language) which usefully uses functions of order >= 3?? Preferably up to 5? Thanks, Ben.
Ben Lippmeier wrote:
I vaguely remember a paper called something like "Is there any use for a seventh order function?", but I forget why they were used, and I can't find it on Google, or ACM or any of the other likely places.
Does anyone have any examples of code (in whatever language) which usefully uses functions of order >= 3?? Preferably up to 5?
I don't know, but you can probably use church-encodings to pimp up the order: type Bool = ∀a . a -> a -> a -- order a + 1 type List a = ∀b . (a -> b -> b) -> b -> b -- max (order a, order b) + 1 not :: Bool -> Bool -- order 2 map :: (a -> a) -> List a -> List a -- order 3 + order a To avoid higher-rank polymorphism, just choose some arbitrary fixed types not' :: (A -> A -> A) -> (A -> A -> A) filter' :: (A -> A) -> ((A -> B -> B) -> B -> B) -> ((A -> B -> B) -> B -> B) Those functions probably aren't that useful anymore, but they once were :) Regards, apfelmus
Do you mean Okasakis "Even higher-order functions for parsing or Why would
anyone ever want to use a sixth-order function?"?
2007/12/14, Ben Lippmeier
Hi all,
I'm working on a type-based side effect analysis for a Haskell-like language, and need to test it against some more higher order functions. The situation is a bit icky because it uses bounded quantification and various related issues (ie covariance vs contravariance) only come into play when dealing with functions of order >= 3.
Trouble is, the vast majority of useful higher order functions that I can think of are of order 2. Oh, I can certainly invent toys like:
order3 f = f succ order4 b f = if b then f else order3
.. and so on, but I'm left feeling unsatisfied.
I vaguely remember a paper called something like "Is there any use for a seventh order function?", but I forget why they were used, and I can't find it on Google, or ACM or any of the other likely places.
Does anyone have any examples of code (in whatever language) which usefully uses functions of order >= 3?? Preferably up to 5?
Thanks, Ben.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
-- Dipl.-Inform. Steffen Mazanek Institut für Softwaretechnologie Fakultät Informatik Universität der Bundeswehr München 85577 Neubiberg Tel: +49 (0)89 6004-2505 Fax: +49 (0)89 6004-4447 E-Mail: steffen.mazanek@unibw.de
Ben Lippmeier wrote:
I vaguely remember a paper called something like "Is there any use for a seventh order function?", but I forget why they were used, and I can't find it on Google, or ACM or any of the other likely places.
http://citeseer.ist.psu.edu/okasaki99functional.html Functional Pearls Even Higher-Order Functions for Parsing or Why Would Anyone Ever Want To Use a Sixth-Order Function? (1999) Chris Okasaki Journal of Functional Programming HTH Christian
participants (4)
-
apfelmus -
Ben Lippmeier -
Christian Maeder -
Steffen Mazanek