[Haskell-cafe] Re: Examples of useful functions of order >= 3?

[apfelmus]

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