[Haskell-cafe] First order Haskell without Data
Brandon Michael Moore
brandon at heave.ugcs.caltech.edu
Thu Apr 19 00:36:55 EDT 2007
On Thu, Apr 19, 2007 at 02:47:30AM +0100, Neil Mitchell wrote:
> 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.
More information about the Haskell-Cafe