[Haskell-cafe] Re: Examples of useful functions of order >= 3?
apfelmus at quantentunnel.de
Fri Dec 14 06:27:05 EST 2007
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
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 :)
More information about the Haskell-Cafe