[Haskell-cafe] First order Haskell without Data

[Brandon Michael Moore]

On Thu, Apr 19, 2007 at 02:47:30AM +0100, Neil Mitchell wrote:
> Hi,
> 
> I've been wondering what is essential to Haskell and what isn't. Not
> from a point of view of what could be removed from the language, but
> what could be removed from a Core language.
> 
> Given the features of higher-order, laziness and data types:
> 
> Laziness can be converted to higher-order functions

Is this a pure language? If so you have to lose asymptotic performance
in some cases, In "More haste, less speed: lazy versus eager evaluation" by
Richard Bird, Geraint Jones and Oege De Moor there's an example of
a function that can be implemented in linear time in a lazy language
but requires O(n log n) time in a strict pure language.

It doesn't matter if you just want to reason about results, and on the
other hand for an intermediate language I suppose you might prefer
to add state and explicitly manipulate the thunking.

Brandon