Applying lifted functions to tuples (of arbitrary length) in Haskell

1.1k views Asked by At

Is there any explanation for why a lifted function, when applied to 2-tuple, only applies to the 2nd entry:

f x = x + 1
f <$> (2,2)
    // -> (2,3)

On the other hand, tuples of any other length than 2 return errors. Also

:t f <$>

returns an error. Is it possible to see the type of f <$> when acting on tuples?

Is there any explanation for that behaviour?

The Data.Tuple documentation is extremely brief and has no mention of how functions are lifted to tuples. Is there any source explaining it?


Update. A part of question about 2-tuples is related to this answer, where, however, the above question about multiple length tuples is not addressed.

4

There are 4 answers

9
Daniel Wagner On

One could (and arguably, GHC should) define a Functor instance for triples and larger tuples. To wit:

instance Functor ((,,) a b) where
    fmap f (a, b, c) = (a, b, f c)

If this instance truly doesn't exist anywhere in base, I suspect that's mostly oversight, though I don't know the history well enough to say for sure. You can include this in any code where it seems useful, with the caveat that you should then absolutely put a fairly strict upper bound on the version of base in your *.cabal file, as this instance might reasonably be included in future versions of base. The PVP allows only the third component of the version to change in such a case, so include at least that many components in your upper bound!

2
gallais On

Is there any explanation for why a lifted function, when applied to 2-tuple, only applies to the 2nd entry

Because tuples are heterogeneous which means that, in general, it would not make sense to try to apply a function of type b -> c to each component of a tuple of type (a, b).

If you want pairs of values of the same type, you can declare your own type Pair and then have the functor instance apply the function to each component.

data Pair a = Pair { fst :: a
                   , snd :: a }

instance Functor Pair where
  fmap f (Pair fst snd) = Pair (f fst) (f snd)

Is it possible to see the type of f <$> when acting on tuples?

f <$> is a section (a partially applied infix operator). To get its type, you need to wrap it with parentheses like so:

:t (f <$>)

The Data.Tuple documentation is extremely brief and has no mention of how functions are lifted to tuples. Is there any source explaining it?

The combinator (<$>) (and (<*>)) are more general than just for tuples, you can find them in the Control.Applicative module.

4
duplode On

In this answer, I will just expand a bit on one of the suggestions I made in a comment.

Is it possible to see the type of f <$> when acting on tuples?

(<$>) is a polymorphic function:

GHCi> :t (<$>)
(<$>) :: Functor f => (a -> b) -> f a -> f b

With GHC 8, you can use the TypeApplications extension to specialise polymorphic functions by supplying instantiations of some or all of their type variables (in this case, f, a and b, in that order):

GHCi> :set -XTypeApplications 
GHCi> :t (<$>) @Maybe
(<$>) @Maybe :: (a -> b) -> Maybe a -> Maybe b
GHCi> :t (<$>) @Maybe @Int
(<$>) @Maybe @Int :: (Int -> b) -> Maybe Int -> Maybe b
GHCi> :t (<$>) @Maybe @_ @Bool
(<$>) @Maybe @_ @Bool :: (t -> Bool) -> Maybe t -> Maybe Bool
GHCi> :t (<$>) @_ @Int @Bool
(<$>) @_ @Int @Bool
  :: Functor t => (Int -> Bool) -> t Int -> t Bool
GHCi> :t (<$>) @Maybe @Int @Bool
(<$>) @Maybe @Int @Bool :: (Int -> Bool) -> Maybe Int -> Maybe Bool

To use that with pairs, use the prefix syntax for the pair type constructor:

GHCi> :t (<$>) @((,) _)
(<$>) @((,) _) :: (a -> b) -> (t, a) -> (t, b)
GHCi> -- You can use the specialised function normally.
GHCi> -- That includes passing arguments to it.
GHCi> f x = x + 1
GHCi> :t (<$>) @((,) _) f
(<$>) @((,) _) f :: Num b => (t, b) -> (t, b)

The _ in ((,) _) leaves it unspecified what the type of the first element of the pair (which is the first argument of the (,) type constructor) should be. Every choice of it gives rise to a different Functor. You can be more specific if you wish:

GHCi> :t (<$>) @((,) String) f
(<$>) @((,) String) f :: Num b => (String, b) -> (String, b)

Lastly, it is worth having a look at what happens if you try that with 3-tuples:

GHCi> :t (<$>) @((,,) _ _) f
(<$>) @((,,) _ _) f
  :: (Num b, Functor ((,,) t t1)) => (t, t1, b) -> (t, t1, b)

As Daniel Wagner discusses in his answer, base doesn't define a Functor instance for 3-tuples. In spite of that, the type checker cannot exclude the possibility that someone somewhere might have defined an instance specific for some choice of the first two type parameters, however pointless that would be. For that reason, the speculative constraint Functor ((,,) t t1) shows up in the type (no such thing happens with pairs because there is a Functor ((,) a) instance in base). As expected, that blows up as soon as we try to instantiate the first two type parameters:

GHCi> :t (<$>) @((,,) Bool String) f

<interactive>:1:1: error:
    • Could not deduce (Functor ((,,) Bool String))
        arising from a use of ‘<$>’
      from the context: Num b
        bound by the inferred type of
                 it :: Num b => (Bool, String, b) -> (Bool, String, b)
        at <interactive>:1:1
    • In the expression: (<$>) @((,,) Bool String) f
2
K. A. Buhr On

All the other answers here seem pretty good, but I don't think anyone precisely answered your question yet.

I believe the reason 2-tuples (and no other tuples) are treated this way by default is because this allows them to be used in the same way as a Writer in a monadic context. (That is, ((,) a) and Writer are isomorphic.)

For example, given a function running in a Writer monad:

import Control.Monad.Writer

foo :: Int -> Writer [String] Int
foo n = do tell ["Running foo " ++ show n]
           if (n <= 0) then do
             tell ["We are done!"]
             return 1
           else do
             rest <- foo (n-1)
             return (n * rest)

you can rewrite it using the Monad instance of ((,) a):

bar :: Int -> ([String], Int)
bar n = do tell' ["Running bar " ++ show n]
           if (n <= 0) then do
             tell' ["We are done!"]
             return 1
           else do
             rest <- bar (n-1)
             return (n * rest)
  where tell' str = (str, ())

and you'll find that these do the same thing:

runWriter (foo 5)
bar 5

up to the ordering of the pair.

The definition of tell' is only needed because ((,) a) hasn't been made an instance of MonadWriter for some reason.

(Edited to add:) While you could extend the definition to larger tuples, this doesn't really provide any additional generality over the definition for the pair: one component of the pair is a monoid to which you can write, and the other component is the underlying "value" in the monad context -- if you need more components for one or the other, you can just make the component a tuple itself.