[Haskell-cafe] I Need a Better Functional Language!

Alexander Solla alex.solla at gmail.com
Mon Apr 9 22:11:54 CEST 2012

On Thu, Apr 5, 2012 at 7:14 AM, Grigory Sarnitskiy <sargrigory at ya.ru> wrote:

> Hello! I've just realized that Haskell is no good for working with
> functions!
> First, what are 'functions' we are interested at? It can't be the usual
> set-theoretic definition, since it is not constructive. The constructive
> definition should imply functions that can be constructed, computed. Thus
> these are computable functions that should be of our concern. But
> computable functions in essence are just a synonym for programs.

The usual set theoretic definition is constructive -- it is the extension
of the definition which is non-constructive.  We can restrict the extension
to constructive domains.  Note that we do not need the law of the excluded
middle or double negation to define a function.

We can easily define:

> newtype Function a b =  Function (Set (a,b))
> apply :: (Function a b) -> a -> b
> apply f a = findMin . filter (\(a',_) -> a == a') $ f

and enforce the function definition/axioms with a smart constructor.  (A
Map is probably a better data structure for this purpose)

Obviously, that's not all of the imaginable possibilities. One also can
> rewrite programs. And write programs that rewrite programs. And write
> programs that rewrite programs that rewrite the first programs and so on.
> But there is no such possibility in Haskell, except for introducing a DSL.
You will always need a DSL of some kind.  Otherwise, what will you quantify
over?  This is an important point.  In order to give a function semantics,
it /must/ be interpreted.  This will either happen by the compiler, which
interprets a function definition in terms of machine code (or Haskell code,
if you use Template Haskell), or at run-time, as in the "Function a b" type
above.  With some appropriate constraints, you can even rewrite a
(->)-function in terms of a "Function"-function, and vice-versa.

toFunction :: (Enum a, Bounded a) => (a -> b) -> (Function a b)
toFunction f = Set.fromList . fmap f $ [minBound..maxBound]
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120409/0b3af3ec/attachment.htm>

More information about the Haskell-Cafe mailing list