Haskell – Why Isn’t There a Typeclass for Functions?

haskellstandard-library

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.

Best Answer

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.

Related Solutions

Haskell – Why Isn’t `length` Generic by Default?

It's the same reason as why we have map and fmap. Error messages/usability for newbies.

It'd by mighty confusing for many a new programmer to write

myLength = subtract 1 . genericLength

x = myLength [1, 2, 3] :: Int
y = myLength [1, 2, 3] :: Integer

and get an error complaining about the monomorphism restriction. Plus which do you prefer

Couldn't match expected type "Integer" with type "Bool"

No instance for Num Bool arising from usage ....

It's simply a matter of usability.

Furthermore, in a lot of cases you end up just wanting defaulting anyways, such as with function composition

evenElems = even . subtract 1 . genericLength

default ()
evenElems = even . genericLength -- Error ambiguous type variable.

Here we just want GHC to "pick" a random Num type and we really don't care which (it's Integer IIRC).

If everything was fully generic the defaulting rules would get um.. murky. Since As of right now there are only 4 things that are automatically available as defaults and no way to set anything fine grained (per function).

As for efficiency, typeclasses means lugging potentially lugging typeclass's dictionary and defaulting to Integer which is much more expensive than Int.

There are alternative preludes (I think classy prelude is unmaintained, but interesting) that do attempt to be as generic as possible. Using them is as simple as

 {- LANGUAGE NoImplicitPrelude #-}
 import My.Super.Awesome.Prelude

C# – Implement Haskell Typeclass with C# Interface

C#'s type system lacks a couple features necessary to properly implement type classes as an interface.

Let's start with your example, but the key is showing a fuller account of what a typeclass is and does, and then trying to map those to C# bits.

class Functor f where
  fmap :: (a -> b) -> f a -> f b

This is the type class definition, or similar to the interface. Now let's look at a definition of a type and it's implementation of that type class.

data Awesome a = Awesome a a

instance Functor Awesome where
  fmap f (Awesome a1 a2) = Awesome (f a1) (f a2)

Now we can see very obviously one distinct fact of type classes that you cannot have with interfaces. The implementation of the type class is not a part of the definition of the type. In C#, to implement an interface, you must implement it as a part of the definition of the type that implements it. This means you may not implement an interface for a type which you do not implement yourself, however in Haskell you may implement a type class for any type you have access to.

That's probably the largest immediately, but there's another fairly significant difference that makes the C# equivalent really not work nearly as well, and you are touching on it in your question. It's about Polymorphism. Also there's some relatively generic things Haskell allows you to do with type classes which outright do not translate especially when you start looking at the amount of genericism in existential types or other GHC extensions like Generic ADTs.

You see, with Haskell you can define the functors

data List a = List a (List a) | Terminal
data Tree a = Tree val (Tree a) (Tree a) | Terminal

instance Functor List where
  fmap :: (a -> b) -> List a -> List b
  fmap f (List a Terminal) = List (f a) Terminal
  fmap f (List a rest) = List (f a) (fmap f rest)

instance Functor Tree where
  fmap :: (a -> b) -> Tree a -> Tree b
  fmap f (Tree val Terminal Terminal) = Tree (f val) Terminal Terminal
  fmap f (Tree val Terminal right) = Tree (f val) Terminal (fmap f right)
  fmap f (Tree val left Terminal) = Tree (f val) (fmap f left) Terminal
  fmap f (Tree val left right) = Tree (f val) (fmap f left) (fmap f right)

Then in consumption you can have a function:

mapsSomething :: Functor f, Show a => f a -> f String
mapsSomething rar = fmap show rar

Herein lies the problem. In C# how do you write this function?

public Tree<a> : Functor<a>
{
    public a Val { get; set; }
    public Tree<a> Left { get; set; }
    public Tree<a> Right { get; set; }

    public Functor<b> fmap<b>(Func<a,b> f)
    {
        return new Tree<b>
        {
            Val = f(val),
            Left = Left.fmap(f);
            Right = Right.fmap(f);
        };
    }
}

public string Show<a>(Showwable<a> ror)
{
    return ror.Show();
}

public Functor<String> mapsSomething<a,b>(Functor<a> rar) where a : Showwable<b>
{
    return rar.fmap(Show<b>);
}

So there's a couple things wrong with the C# version, for one thing I'm not even certain it will allow you to use the <b> qualifier like I did there, but without it I am certain it wouldn't dispatch Show<> appropriately (feel free to try and compile to find out; I didn't).

The bigger problem here however is that unlike above in Haskell where we had our Terminals defined as part of the type and then usable in place of the type, due to C# lacking appropriate parametric polymorphism (which becomes super obvious as soon as you try to interop F# with C#) you can't clearly or cleanly distinguish whether Right or Left are Terminals. Best you can do is use null, but what if you're trying to make a value type a Functor or in the case of Either where you're distinguishing two types that both carry a value? Now you have to use one type and have two different values to check and switch between to model your discrimination?

The lack of proper sum types, union types, ADTs, whatever you want to call them really makes a lot of what typeclasses give you fall away because at the end of the day they let you treat multiple types (constructors) as a single type, and .NET's underlying type system simply has no such concept.

Haskell – Why Isn’t There a Typeclass for Functions?

Best Answer

Categories

Arrows

Applicatives

Related Topic