[Haskell-cafe] First order Haskell without Data

[Neil Mitchell]

Hi

> A first order language without data types cannot exist - what could
> the arguments of functions be, if they cannot be function types or
> data types?

I should have clarified, in my mind I was thinking "allowing only
non-recursive constants, namely Int's".

> If you allow recursive primitive types, then data can be
> trivially encoded, by the sum-of-products construction.  If you allow
> non-recursive primitive types, then any function space contains only
> functions with a priori bounded argument and result sets, and thus
> your language is trivally Turing incomplete.

True, I guess that is the most minimal we can do then.

> > * data types -> higher order is in "Efficient Interpretation by
> > Transforming Data Types and Patterns to Functions"
> > http://www.cs.nott.ac.uk/~nhn/TFP2006/Papers/03-JansenKoopmanPlasmeijer-EfficientInterpretation.pdf
>
> You could just have referenced Church encoding ;)

I like that paper as it shows a really trivial encoding of case and
constructors into the Church encoding - i.e. how you'd transform
Haskell to it easily with examples.

Thanks

Neil