17

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...

  1. 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.

  2. 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.

  • 2
    Call me crazy, but when I think of a typeclass like you're describing that's for applying and composing etc I think of applicative functors, which functions are. Perhaps that's the type class you're thinking of? – Jimmy Hoffa Oct 24 '13 at 20:25
  • 1
    I don't think Applicative is quite right - it requires the values to be wrapped as well as the functions, whereas I only want to wrap the functions, and the wrapped functions really are functions, whereas my wrapped functions normally won't be (in the most general case, they're ASTs describing functions). Where <*> has type f (a -> b) -> f a -> f b, I want an application operator with type g a b -> a -> b where a and b specify the domain and codomain of the wrapped function, but what's inside the wrapper isn't (necessarily) a real function. On Arrows - possibly, I'll have a look. – Steve314 Oct 24 '13 at 20:49
  • 3
    if you want inverse wouldn't that imply a group? – jk. Oct 24 '13 at 20:51
  • 1
    @jk. great point, realizing that there's lots of things to read about inverses of functions which may lead the OP to find what he's looking for. Here's some interesting reading off hand on the topic. But a google for haskell function inverse gives plenty of curious reading content. Perhaps he just wants Data.Group – Jimmy Hoffa Oct 24 '13 at 21:05
  • 2
    @Steve314 I thought functions with composition are a monoidal category. They are a monoid if the domain and codomain are always the same. – Tim Seguine Oct 24 '13 at 21:22
14

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

Categories

If you have a simple function concept that has identities and composition, than you have a category.

class Category c where
  id :: c a a
  (.) :: c b c -> c a b -> c a c

The disadvantage is that you cannot create a nice category instance with a set of objects (a, b, and c). You can create a custom category class I suppose.

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.

  • Category seems to lack application - ($). Arrows look like massive overkill at first sight, but still ArrowApply sounds promising - so long as I don't need to provide anything I can't it may be OK. +1 for the moment, with more checking to do. – Steve314 Oct 24 '13 at 21:03
  • 3
    @Steve314 Categories do lack application, but monads lack a universal way to run them, doesn't mean they're not useful – jozefg Oct 25 '13 at 2:31
  • There's a common reason why I can't use Applicative or Arrow (or Monad) - I can't wrap a normal function (in general) because values of my type represent a function but are represented by data, and won't support arbitrary functions if if there was a way to translate. That means I can't provide pure, arr or return for instances. BTW - those classes are useful but I can't use them for this particular purpose. Arrow isn't "massive overkill" - that was a false impression from the last time I tried to read the paper, when I wasn't ready to understand it. – Steve314 Oct 26 '13 at 10:33
  • @Steve314 The idea of providing a monad interface to build up data is what free monads are used for, check them out – jozefg Oct 26 '13 at 10:36
  • I watched the video from Haskell Exchange 2013 - Andres Löh definitely explains it well, though I still probably need to watch it again, play with the technique etc. I'm not sure it's needed here, though. My goal is to have the abstraction of a function using a representation that isn't a function (but which has an interpreter function). I don't need a side-effects abstraction, and I don't need a clean notation for sequencing operations. Once this function abstraction is in use, applications and compositions will be done one-at-a-time inside an algorithm in another library. – Steve314 Oct 26 '13 at 10:48
2

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.

  • this reads more like a comment, see How to Answer – gnat Jul 1 '15 at 20:17
  • Sorry. This is more or less my first answer ever. – user185657 Jul 1 '15 at 20:22
  • How do you suggest I improve the answer? – user185657 Jul 1 '15 at 20:23
  • consider editing to help readers see how your answer addresses the question asked, "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?" – gnat Jul 1 '15 at 20:25
  • 1
    I hope this is better – user185657 Jul 1 '15 at 21:22
1

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
  • how does this address the question asked? see How to Answer – gnat Jun 29 '15 at 15:21
  • @gnat I thought that the definitions in Data.Lambda give classes for function-like things (which was asked for)... I wasn't sure how these things are to be used. I explored this a bit. Probably, they don't provide an abstraction for function application though. – imz -- Ivan Zakharyaschev Jun 29 '15 at 15:35

protected by gnat Jul 1 '15 at 20:17

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.