misterbee
misterbee

Reputation: 5172

Functor/Applicative-like typeclass for composing (a->a) functions instead of (a->b)?

I have a type that looks like this:

newtype Canonical Int = Canonical Int

and a function

canonicalize :: Int  -> Canonical  Int
canonicalize =  Canonical . (`mod` 10)  -- or whatever

(The Canonical type may not be important, it just serves to distinguish "raw" values from "canonicalized" values.)

I'd like to create some machinery so that I can canonicalize the results of function applications.

For example: (Edit: fixed bogus definitions)

cmap :: (b->Int) -> (Canonical b) -> (Canonical Int)
cmap f (Canonical x) = canonicalize $ f x

cmap2 :: (b->c->Int) -> (Canonical b) -> (Canonical c) -> (Canonical Int)
cmap2 f (Canonical x) (Canonical y) = canonicalize $ f x y

That's superficially similar to Functor and Applicative, but it isn't quite, because it's too specialized: I can't actually compose functions (as required by the homomorphism laws for Functor/Applicative) unless 'b' is Int.

My goal is to use existing library functions/combinators, instead of writing my own variants like cmap, cmap2. Is that possible? Is there a different typeclass, or a different way to structure Canonical type, to enable my goal?

I've tried other structures, like

newtype Canonical a = Canonical { value :: a, canonicalizer :: a -> a }

but that hits the same non-composability problem, because I can't translate one canonicalizer to another (I just want to use the canonicalizer of the result type, which is always Int (or Integral a)

And I can't force "specialization-only" like so, this isn't valid Haskell:

instance (Functor Int) (Canonical Int) 

(and similar variations)

I also tried

newtype (Integral a) => Canonical a = Canonical a -- -XDatatypeContexts
instance (Integral a) => Functor Canonical where
  fmap f (Canonical x) = canonicalize  $ f x

but GHC says that DatatypeContexts is deprecated, and a bad idea, and more severely, I get:

 `Could not deduce (Integral a1) arising from a use of 'C'   
 from the context (Integral a)
 bound by the instance declaration
 [...] fmap :: (a1 -> b) -> (C a1 -> C b)

which I think is saying that the constraint Integral a can't actually be used to constrain fmap to (Integral -> Integral) the way I wish, which is sort of obvious (since fmap has two type variables) :-(

And of course this isn't valid Haskell either

instance (Integer a) => Functor Canonical where

Is there a similar typeclass I could use, or am I wrong to try to use a typeclass at all for this functionality of "implicitly canonicalize the results of function calls"?

Upvotes: 4

Views: 214

Answers (3)

Michael Snoyman
Michael Snoyman

Reputation: 31305

I think what you're trying to achieve is available in the mono-traversable package, and in this case the MonoFunctor typeclass.

Upvotes: 5

J. Abrahamson
J. Abrahamson

Reputation: 74334

Your cmap is actually implementable via fmap. It's a bit strange at first, but (->) is just a datatype itself, actually equivalent to Reader. We can fmap over the return result.

cmap :: (a -> Int) -> a -> (Canonical Int)
cmap = fmap Can

You can create the other cmap variants using the same pattern

cmap2 :: (a -> b -> Int) -> a -> b -> (Canonical Int)
cmap2 = fmap (fmap Can)

cmap3 :: (a -> b -> c -> Int) -> a -> b -> c -> (Canonical Int)
cmap3 = fmap (fmap (fmap Can))

Now this usually is a bit of a strange thing to see in code, it's more common to see the less general form of fmap on (->)

instance Functor (r ->) where
  fmap = (.)

cmap :: (a -> Int) -> a -> (Canonical Int)
cmap = (.) Can
cmap f = Can . f

cmap2 :: (a -> b -> Int) -> a -> b -> (Canonical Int)
cmap2   = (.) ((.) Can)
cmap2   = (.) (Can .)
cmap2 f = (Can .) . f

cmap3 :: (a -> b -> c -> Int) -> a -> b -> c -> (Canonical Int)
cmap3   = (.) ((.) ((.) Can))
cmap3   = (.) ((.) (Can .))
cmap3   = (.) ((Can .) .)
cmap3 f = ((Can .) .) . f

Obviously this gets a little ridiculous in the higher order combinators. Pointfree style might not be the best choice.

Upvotes: 1

epsilonhalbe
epsilonhalbe

Reputation: 15967

from your type signatures this looks a bit like the Identity monad

newtype Identity a = Identity a

instance Monad Identity where
         return x = Identity x
         f >>= (Identity x)  = Identity (f x)

then in your example canonicalize = return and cmap f x = f >>= (return x)

hope this is helpful

Edit

The other structure that comes to my mind is Automorphisms (I studied math)

so if you have

data Automorphisms a = AMorph (a -> a)

then you can have a Monoid

instance Monoid Automorphism where
         mempty = id
         mappend = (.)
         mconcat = foldr1 (.)

(I hope foldr1 is the right one)

Upvotes: 2

Related Questions