[Haskell-cafe] First order Haskell without Data
ndmitchell at gmail.com
Wed Apr 18 21:56:52 EDT 2007
> 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.
More information about the Haskell-Cafe