Haskell function from (a -> [b]) -> [a -> b]

Question

I have a function seperateFuncs such that

seperateFuncs :: [a -> b] -> (a -> [b])
seperateFuncs xs = \x -> map ($ x) xs

I was wondering whether the converse existed, i.e. is there a function

joinFuncs :: (a -> [b]) -> [a -> b]

I think not (mainly because lists are not fixed length), but perhaps I'll be proved wrong. The question then is there some datatype f which has a function :: (a -> f b) -> f (a -> b)?

Answer 1

You can generalize seperateFuncs to Applicative (or Monad) pretty cleanly:

seperateFuncs :: (Applicative f) => f (a -> b) -> (a -> f b)
seperateFuncs f x = f <*> pure x

Written in point-free style, you have seperateFuncs = ((. pure) . (<*>)), so you basically want unap . (. extract), giving the following definition if you write it in pointful style:

joinFuncs :: (Unapplicative f) => (a -> f b) -> f (a -> b)
joinFuncs f = unap f (\ g -> f (extract g))

Here I define Unapplictaive as:

class Functor f => Unapplicactive f where
    extract  :: f a -> a
    unap     :: (f a -> f b) -> f (a -> b)

To get the definitions given by leftaroundabout, you could give the following instances:

instance Unapplicative [] where
    extract = head
    unap f = [\a -> f [a] !! i | i <- [0..]]

instance Unapplicative ((->) c) where
    extract f = f undefined
    unap f = \x y -> f (const y) x

I think it's hard to come up with a "useful" function f :: (f a -> f b) -> f (a -> b) for any f that isn't like (->).

Answer 2

First of all, you can brute-force yourself this function all right:

joinFuncs f = [\x -> f x !! i | i<-[0..]]

but this is obviously troublesome – the resulting list is always infinite but evaluating the ith element with x only succeds if length(f x) > i.

To give a "real" solution to

The question then is there some datatype f which has a function :: (a -> f b) -> f (a -> b)?

Consider (->)c. With that, your signature reads (a -> (c->b)) -> (c->(a->b)) or equivalently (a -> c -> b) -> c -> a -> b which, it turns out, is just flip.

Of course, this is a bit of a trivial one since seperateFuncs has the same signature for this type...

Answer 3

"Is there some datatype f which has a function :: (a -> f b) -> f (a -> b)?"

In fact, there is an even more general version of this function in the Traversable type class, which deals with commutable functors:

class (Functor t, Foldable t) => Traversable t where

  ... 

  sequenceA :: Applicative f => t (f b) -> f (t b)

How is this related to your function? Starting from your type, with one type substitution, we recover sequenceA:

1. (a -> f b) -> f (a -> b) ==> let t = (->) a
2. t (f b) -> f (t b)

However, this type has the constraint that t must be a Traversable -- and there isn't a Traversable instance for (->) a, which means that this operation can't be done in general with functions. Although note that the "other direction" -- f (a -> b) -> (a -> f b) works fine for all functions and all Applicatives f.

Answer 4

I have recently had to think quite a bit about problems that reduce to a question very similar to yours. Here's the generalizations that I found.

First, it is trivial to do this (at Tinctorius pointed out):

f2m :: Functor f => f (a -> b) -> a -> f b
f2m f a = fmap ($a) f

But it is impossible to do this in general:

m2a :: Monad m => (a -> m b) -> m (a -> b)

One insightful way of understanding this, which somebody kindly explained to me in the #haskell irc channel, is that if there existed an m2a function, there would be no difference between Applicative and Monad. Why? Well, I don't follow it 100%, but it's something like this: Monad m => a -> m b is the very common type of monadic actions with one parameter, while Applicative f => f (a -> b) is the also very common type of what, for not knowing the proper name, I'll call "applicable applicatives." And the fact that Monad can do things that Applicative cannot is tied to the fact that m2a cannot exist.

So now, applied to your question:

joinFuncs :: (a -> [b]) -> [a -> b]

I suspect the same "Monad /= Applicative" argument (which, again, let me stress, I don't fully understand) should apply here. We know that the Monad [] instance can do things that the Applicative [] instance cannot. If you could write a joinFuncs with the specified type, then the [a -> b] result must in some sense "lose information" compared to the a -> [b] argument, because otherwise Applicative [] is the same as Monad []. (And by "lose" information I mean that any function with joinFuncs's type cannot have an inverse, and thus it is guaranteed to obliterate the distinction between some pair of functions f, g :: a -> [b]. The extreme case of that is joinFuncs = undefined.)

I did find that I needed functions similar to m2a So the special case that I found is that it's possible to do this:

import Data.Map (Map)
import qualified Data.Map as Map

-- | Enumerate a monadic action within the domain enumerated by the 
-- argument list.
boundedM2a :: Monad m => (a -> m b) -> [a] -> m [(a,b)]
boundedM2a f = mapM f'
    where f' a = do b <- f a
                    return (a, b)

-- | The variant that makes a 'Map' is rather useful.
boundedM2a' :: (Monad m, Ord a) => (a -> m b) -> [a] -> m (Map a b)
boundedM2a' f = liftM Map.fromList . boundedM2a f

Note that in addition to the requirement that we enumerate the as, an interesting observation is that to do this we have to "materialize" the result in a sense; turn it from a function/action into a list, map or table of some sort.

Answer 5

The question "can I have function with type signature joinFuncs :: (a -> [b]) -> [a -> b] is incomplete without also saying what laws you want this function to satisfy. Without laws, you may solve this problem by defining joinFuncs _ = [] (always returning an empty list). This trivial function satisfies the required type signature but is most likely useless.

One way of demanding that joinFuncs be useful is to impose the non-degeneracy law, separateFuncs . joinFuncs == id. Then one can show that it is impossible to implement joinFuncs for this type signature.

A more general case of this type signature is (a -> f b) -> f (a -> b) where f is some functor. I call such functors "rigid". See this question Is this property of a functor stronger than a monad? for more details.

All rigid functors R satisfy the property that the type R () has only one distinct value, i.e. it is equivalent to (). This allows us to see right away that the List functor is not rigid, because List () is not equivalent to ().

The simplest non-trivial example of a rigid functor is type R a = (a -> p) -> a where p is a fixed type. The functor R defined in this way is actually a rigid monad.