Why isn’t there a typeclass for functions?

In a learning problem I’ve been messing around with, I realised I needed a typeclass for functions with operations for applying, composing etc. Reasons…

It can be convenient to treat a representation of a function as if it were the function itself, so that applying the function implicitly uses an interpreter, and composing functions derives a new description.
Once you have a typeclass for functions, you can have derived typeclasses for special kinds of functions – in my case, I want invertible functions.

For example, functions that apply integer offsets could be represented by an ADT containing an integer. Applying those functions just means adding the integer. Composition is implemented by adding the wrapped integers. The inverse function has the integer negated. The identity function wraps zero. The constant function cannot be provided because there’s no suitable representation for it.

Of course it doesn’t need to spell things as if it the values were genuine Haskell functions, but once I had the idea, I thought a library like that must already exist and maybe even using the standard spellings. But I can’t find such a typeclass in the Haskell library.

I found the Data.Function module, but there’s no typeclass – just some common functions that are also available from the Prelude.

So – why isn’t there a typeclass for functions? Is it “just because there isn’t” or “because it’s not so useful as you think”? Or maybe there’s a fundamental problem with the idea?

The biggest possible problem I’ve thought of so far is that function application on actual functions would probably have to be special-cased by the compiler to avoid a looping problem – in order to apply this function I need to apply the function application function, and to do that I need to call the function application function, and to do that…

More Clues

Example code to show what I’m aiming for…

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE GADTs #-}

--  In my first version, Doable only had the one argument f. This version
--  seemed to be needed to support the UndoableOffset type.
--
--  It seems to work, but it also seems strange. In particular,
--  the composition function - a and b are in the class, but c isn't,
--  yet there's nothing special about c compared with a and b.
class Doable f a b where
  fwdApply :: f a b -> a -> b
  compDoable :: f b c -> f a b -> f a c

--  In the first version, I only needed a constraint for
--  Doable f a b, but either version makes sense.
class (Doable f a b, Doable f b a) => Undoable f a b where
  bwd      :: f a b -> f b a

  bwdApply :: f a b -> b -> a
  bwdApply f b = fwdApply (bwd f) b

--  Original ADT - just making sure I could wrap a pair of functions
--  and there were no really daft mistakes.
data UndoableFn a b = UFN { getFwd :: a -> b, getBwd :: b -> a }

instance Doable UndoableFn a b where
  fwdApply = getFwd
  compDoable f g = UFN ((getFwd f) . (getFwd g)) ((getBwd g) . (getBwd f))

instance Undoable UndoableFn a b where
  bwd f    = UFN (getBwd f) (getFwd f)
  bwdApply = getBwd

--  Making this one work led to all the extensions. This representation
--  can only represent certain functions. I seem to need the typeclass
--  arguments, but also to need to restrict which cases can happen, hence
--  the GADT. A GADT with only one constructor still seems odd. Perhaps
--  surprisingly, this type isn't just a toy (except that the whole thing's
--  a toy really) - it's one real case I need for the exercise. Still a
--  simple special case though.
data UndoableOffset a b where
  UOFF :: Int -> UndoableOffset Int Int

instance Doable UndoableOffset Int Int where
  fwdApply (UOFF x) y = y+x
  compDoable (UOFF x) (UOFF y) = UOFF (x+y)

instance Undoable UndoableOffset Int Int where
  bwdApply (UOFF x) y = y-x
  bwd (UOFF x) = UOFF (-x)

--  Some value-constructing functions
--  (-x) isn't shorthand for subtraction - whoops.
undoableAdd :: Int -> UndoableFn Int Int
undoableAdd x = UFN (+x) (y -> y-x)

undoableMul :: Int -> UndoableFn Int Int
undoableMul x = UFN (*x) (`div` x)

--  With UndoableFn, it's possible to define an invertible function
--  that isn't invertible - to break the laws. To prevent that, need
--  the UFN constructor to be private (and all public ops to preserve
--  the laws). undoableMul is already not always invertible.
validate :: Undoable f a b => Eq a => f a b -> a -> Bool
validate f x = (bwdApply f (fwdApply f x)) == x

--  Validating a multiply-by-zero invertible function shows the flaw
--  in the validate-function plan. Must try harder.
main = do putStrLn . show $ validate (undoableAdd 3) 5
          putStrLn . show $ validate (undoableMul 3) 5
          --putStrLn . show $ validate (undoableMul 0) 5
          fb1 <- return $ UOFF 5
          fb2 <- return $ UOFF 7
          fb3 <- return $ compDoable fb1 fb2
          putStrLn $ "fwdApply fb1  3 = " ++ (show $ fwdApply fb1  3)
          putStrLn $ "bwdApply fb1  8 = " ++ (show $ bwdApply fb1  8)
          putStrLn $ "fwdApply fb3  2 = " ++ (show $ fwdApply fb3  2)
          putStrLn $ "bwdApply fb3 14 = " ++ (show $ bwdApply fb3 14)

The application involves a kind of unification where unified values aren’t equal, but are related via those invertible functions – Prolog-style logic but with a = f(b) constraints rather than a = b. Most of the composition will result from optimizing a union-find structure. The need for inverses should be obvious.

If no item in a unified set has an exact value, then a particular item can only be quantified relative to another item in that unified set. That’s why I don’t want to use “real” functions – computing those relative values. I could drop the whole function aspect and just have absolute and relative quantities – I probably only need numbers/vectors and (+) – but my inner architecture astronaut wants his fun.

The only way I break the links apart again is via backtracking, and everything is pure – union-find will be done using keys into an IntMap as “pointers”. I have simple union-find working, but as I haven’t added the invertible functions yet, there’s no point listing it here.

Reasons I can’t use Applicative, Monad, Arrow etc

The main operations I need the function abstraction class to provide are application and composition. That sounds familiar – e.g. the Applicative (<*>), Monad (>>=) and Arrow (>>>) are all composition functions. However, the types that implement the function abstraction in my case will contain some data structure that represents a function, but which isn’t (and can’t contain) a function, and which can only represent some limited set of functions.

As I mentioned in the explanation of the code, sometimes I can only quantify one item relative to another because no item in a “unified” cluster has an exact value. I want to be able to derive a representation of that function, which in general will be the composition of several provided functions (walking up to a common ancestor in the union/find tree) and of several inverse functions (walking back down to the other item).

Simple case – where the original “functions” are limited to integer-offset “functions”, I want the composed result as an integer-offset “function” – add the component offsets. That’s a big part of why the composition function needs to be in the class as well as the application function.

This means I cannot provide the operations pure, return or arr for my types, so I can’t use Applicative, Monad or Arrow.

This isn’t a failure of those types – it’s a mismatch of abstractions. The abstraction I want is of a simple pure function. There’s no side-effecting, for example, and no need to build a convenient notation for sequencing and composing the functions other than an equivalent of the standard (.) that applies to all functions.

I could instance Category. I’m confident that all my functiony-things will be able to provide an identity, though I probably don’t need it. But as Category doesn’t support application, I’d still need a derived class anyway to add that operation.

Well, I don’t know of any baked in ideas that market themselves as representing “function-y” things. But there are several that come close

Arrows

If your functions have a notion of products and can inject arbitrary functions, than arrows are for you

 class Arrow a where
   arr :: (b -> c) -> a b c
   first :: a b c -> a (b, d) (c, d)
   second :: a b c -> a (d, b) (d, c)

ArrowApply has a notion of application which looks important for what you want.

Applicatives

Applicatives have your notion of application, I’ve used them in an AST to represent function application.

class Functor f => Applicative f where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f b -> f c

There are many other ideas. But a common theme is to build up some data structure representing your function, and than pass it to an interpretation function.

This also how many free monads work. I’d suggest poking at these if you’re feeling brave, they’re a powerful tool for the stuff that you’re suggesting and essentially let you build up a datastructure using do notation and then collapse it into a side effecting computation with different functions. But the beauty is that these functions just operation on the datastructure, and aren’t really aware of how you made it all. This is what’d I’d suggest for your example of an interpreter.

As you point out, the main problem with using Applicative here is that there is no sensible definition for pure. Hence, Apply was invented. At least, that’s my understanding of it.

Unfortunately, I do not have examples on hand of instances of Apply that aren’t also Applicative. It is claimed this is true for IntMap, but I have no idea why. Similarly, I don’t know whether your example – offset integers – admits an Apply instance.

In addition to the mentioned Category, Arrow, and Applicative:

I’ve also discovered Data.Lambda by Conal Elliott:

Some function-like classes, having lambda-like construction

Looks interesting, of course, but difficult to understand without examples…

Examples

Examples can be found in the wiki-page about tangible values (TV) who seem to be one of the things that caused the creation of TypeCompose library; see Inputs and function-valued outputs.

The TV library’s idea is to display Haskell values (including functions) in a tangible manner.

To follow the StackOverflow rule about not posting bare lonks, I copy some bits below which should give the idea of these things:

The first example reads:

apples, bananas :: CInput Int
apples  = iTitle "apples"  defaultIn
bananas = iTitle "bananas" defaultIn

shoppingO :: COutput (Int -> Int -> Int)
shoppingO = oTitle "shopping list" $
            oLambda apples (oLambda bananas total)

shopping :: CTV (Int -> Int -> Int)
shopping = tv shoppingO (+)

which gives when run as runIO shopping (see there for more comments, GUIs, and more examples):

shopping list: apples: 8
bananas: 5
total: 13

Filed under: softwareengineering - @ 03:51

Thẻ: haskell, standard-library

Thiết kế website giá rẻ

Danh mục

Why isn’t there a typeclass for functions?

Categories

Arrows

Applicatives

Examples