🚀 go-pugleaf

In article <1992Oct1.174259@cs.utwente.nl> ramaer@cs.utwente.nl (Mark Ramaer) writes:

   "alt" chooses between two "a"-parsers.

   > alt :: ([t]->Bool) -> Parser t r a -> Parser t r a -> Parser t r a
   > alt test aa bb = \contin input ->
   >       if test input
   >	then aa contin input
   >       else bb contin input

   > sequenceOption :: ([*]->bool) -> Parser t r a -> Parser t r [a]
   > sequenceOption test aa = alt test (sequence test aa) (empty [])

   "Parser t r a" is a 2nd order type, so "alt" and "sequenceOption"
   are 3rd order functions.

Thanks Mark, this certainly is a 3rd order function. In another
posting I tried to make the requirements more precise:

   If we have polymorphism, it is not clear what level to assign to type
   variables. In fact it is quite easy to get a 3rd order functions just
   by instantiating the type of polymorphic map by a 1st order function
   type for the input list. However, I am interested in *genuine* higher
   order functions, i.e. which do not show up as instantiations of
   polymorphic functions. This means that in this context I consider the
   order of a type variable as 0.

Your function alt can be obtained by instantiating a 2nd order
polymorphic function to the type Parser, right? In this way it is not
genuinely higher order.

The following is an example of a genuine higher order function, but
alas it is not very interesting (it is just an instance of
application): 

	\lambda: f:((N->N)->N)->N.f succ
	: ((N->N)->N)->N

--
Thorsten Altenkirch		LFCS, Edinburgh

"Germany still proves reluctant to exchange email with other countries 
efficiently" - Summer 1992 Systems Newsletter, Dep. of CS,Edinburgh