List of Functors

Question

This might apply for any type class, but lets do it for Functors as I know them better. I wan't to construct this list.

l = [Just 1, [1,2,3], Nothing, Right 4]

and then

map (fmap (+1)) l

to get

[Just 2, [2,3,4], Nothing, Right 5]

I know they are all Functors that contain Ints so it might be possible. How can I do this?

Edit

This is turning out to be messier than it would seem. In Java or C# you'd declare the IFunctor interface and then just write

List<IFunctor> l = new List<IFunctor> () {
    new Just (1),
    new List<Int>() {1,2,3},
    new Nothing<Int>(),
    new Right (5)
}

assuming Maybe, List and Either implement the IFunctor. Naturally Just and Nothing extend Maybe and Right and Left extend Either. Not satisfied with this problem being easier to resolve on these languages!!!

There should cleaner way in Haskell :(

Answer 1

In Haskell, downcasting is not allowed. You can use AnyFunctor, but the trouble with that is there is no longer any way to get back to a functor that you know. When you have an AnyFunctor a, all you know is that you have an f a for some f, so all you can do is fmap (getting you another AnyFunctor). Thus, AnyFunctor a is in fact equivalent to ().

You can add structure to AnyFunctor to make it more useful, and we'll see a bit of that later on.

Functor Coproducts

But first, I'll share the way that I would probably end up doing this in a real program: by using functor combinators.

{-# LANGUAGE TypeOperators #-}

infixl 1 :+:   -- declare this to be a left-associative operator

data (f :+: g) a = FLeft (f a) | FRight (g a)
instance (Functor f, Functor g) => Functor (f :+: g) where
    -- left as an exercise

As the data type reads, f :+: g is a functor whose values can be either f a or g a.

Then you can use, for example:

l :: [ (Maybe :+: []) Int ]
l = [ FLeft (Just 1), FRight [2,3,4], FLeft Nothing ]

And you can observe by pattern matching:

getMaybe :: (Maybe :+: g) a -> Maybe a
getMaybe (FLeft v) = v
getMaybe (FRight _) = Nothing

It gets ugly as you add more functors:

l :: [ (Maybe :+: [] :+: Either Int) Int ]
l = [ FLeft (FLeft Nothing), FRight (Right 42) ]
-- Remember that we declared :+: left-associative.

But I recommend it as long as you can handle the ugliness, because it tracks the list of possible functors in the type, which is an advantage. (Perhaps you eventually need more structure beyond what Functor can provide; as long as you can provide it for (:+:), you're in good territory.)

You can make the terms a bit cleaner by creating an explicit union, as Ganesh recommends:

data MyFunctors a
    = FMaybe (Maybe a)
    | FList [a]
    | FEitherInt (Either Int a)
    | ...

But you pay by having to re-implement Functor for it ({-# LANGUAGE DeriveFunctor #-} can help). I prefer to put up with the ugliness, and work at a high enough level of abstraction where it doesn't get too ugly (i.e. once you start writing FLeft (FLeft ...) it's time to refactor & generalize).

Coproduct can be found in the comonad-transformers package if you don't want to implement it yourself (it's good exercise though). Other common functor combinators are in the Data.Functor. namespace in the transformers package.

Existentials with Downcasting

AnyFunctor can also be extended to allow downcasting. Downcasting must be explicitly enabled by adding the Typeable class to whatever you intend to downcast. Every concrete type is an instance of Typeable; type constructors are instances of Typeable1 (1 argument); etc. But it doesn't come for free on type variables, so you need to add class constraints. So the AnyFunctor solution becomes:

{-# LANGUAGE GADTs #-}

import Data.Typeable

data AnyFunctor a where
    AnyFunctor :: (Functor f, Typeable1 f) => f a -> AnyFunctor a

instance Functor AnyFunctor where
    fmap f (AnyFunctor v) = AnyFunctor (fmap f v)

Which allows downcasting:

downcast :: (Typeable1 f, Typeable a) => AnyFunctor a -> Maybe (f a)
downcast (AnyFunctor f) = cast f

This solution is actually cleaner than I had expected to be, and may be worth pursuing.

Answer 2

One approach is to use existentials:

{-# LANGUAGE GADTs #-}
data AnyFunctor v where
    AnyFunctor :: Functor f => f v -> AnyFunctor v

instance Functor AnyFunctor where
    fmap f (AnyFunctor fv) = AnyFunctor (fmap f fv)

The input list you ask for in your question isn't possible as it stands because it's not correctly typed, so some wrapping like AnyFunctor is likely to be necessary however you approach it.

You can make the input list by wrapping each value in the AnyFunctor data constructor:

[AnyFunctor (Just 1), AnyFunctor [1,2,3],
 AnyFunctor Nothing, AnyFunctor (Right 4)]

Note that when you use fmap (+1) it's a good idea to use an explicit type signature for the 1 to avoid any problems with numeric overloading, e.g. fmap (+(1::Integer)).

The difficulty with AnyFunctor v as it stands is that you can't actually do much with it - you can't even look at the results because it isn't an instance of Show, let alone extract a value for future use.

It's a little tricky to make it into an instance of Show. If we add a Show (f v) constraint to the AnyFunctor data constructor, then the Functor instance stops working because there's no guarantee it'll produce an instance of Show itself. Instead we need to use a sort of "higher-order" typeclass Show1, as discussed in this answer:

{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE GADTs #-}

data AnyFunctor v where
    AnyFunctor :: (Show1 f, Functor f) => f v -> AnyFunctor v

instance Functor AnyFunctor where
    fmap f (AnyFunctor fv) = AnyFunctor (fmap f fv)

data ShowDict a where
    ShowDict :: Show a => ShowDict a

class Show1 a where
    show1Dict :: ShowDict b -> ShowDict (a b)

instance Show v => Show (AnyFunctor v) where
    show (AnyFunctor (v :: f v)) =
        case show1Dict ShowDict :: ShowDict (f v) of
           ShowDict -> "AnyFunctor (" ++ show v ++ ")"

instance Show1 [] where
    show1Dict ShowDict = ShowDict

instance Show1 Maybe where
    show1Dict ShowDict = ShowDict

instance Show a => Show1 (Either a) where
    show1Dict ShowDict = ShowDict

In ghci this gives the following (I've broken the lines for readability):

*Main> map (fmap (+1)) [AnyFunctor (Just 1), AnyFunctor [1,2,3],
                          AnyFunctor Nothing, AnyFunctor (Right 4)]

[AnyFunctor (Just 2),AnyFunctor ([2,3,4]),
 AnyFunctor (Nothing),AnyFunctor (Right 5)]

The basic idea is to express the idea that a type constructor like Nothing, [] or Either a "preserves" the Show constraint, using the Show1 class to say that Show (f v) is available whenever Show v is available.

The same trick applies with other typeclasses. For example @luqui's answer shows how you can extract values using the Typeable class, which already has a built-in Typeable1 variant. Each type class that you add limits the things that you can put into AnyFunctor, but also means you can do more things with it.