CODEWITHSUNDEEP
haskellapplicativecategory-theory
crepe_lord
crepe_lord

Reputation: 21

Looking for a Haskell function related to liftA2, but works like <|> from Alternative

Consider this liftA2 function:

liftA2 :: (a -> b -> c) -> Maybe a -> Maybe b -> Maybe c
liftA2 f Nothing  Nothing  = Nothing
liftA2 f (Just x) Nothing  = Nothing
liftA2 f Nothing  (Just y) = Nothing
liftA2 f (Just x) (Just y) = f x y

This is equivalent to the real liftA2 function from Control.Applicative, but specialized for Maybe. (and also liftM2 from Control.Monad)

I'm looking for a cousin of that function, that works like this:

mystery :: (a -> a -> a) -> Maybe a -> Maybe b -> Maybe c
mystery f Nothing  Nothing  = Nothing
mystery f (Just x) Nothing  = Just x
mystery f Nothing  (Just y) = Just y
mystery f (Just x) (Just y) = Just (f x y)

The closest concept I'm aware of is <|>, but that discards the second value if there are two, whereas I would rather pass a function to combine them.

What is this mystery function called? What type class does it operate on? What terms can I google to learn more? Thank you!

Upvotes: 2

Views: 386

Answers (3)

duplode
duplode

Reputation: 34398

Here goes an extra argument in support of alignWith being the liftA2 analogue you are looking for, as dfeuer suggests.

Using the monoidal presentation of Applicative...

fzip :: Applicative f => f a -> f b -> f (a, b)
fzip u v = (,) <$> u <*> v  -- Think of this as a default implementation.

... we can do a subtle tweak on liftA2:

liftA2' :: Applicative f => ((a, b) -> c) -> f a -> f b -> f c
liftA2' f u v = f <$> fzip u v

This variation is relevant here because it translates straightforwardly to Alternative, under the products-to-sums monoidal functor interpretation:

-- fzip analogue. Name borrowed from protolude.
eitherA :: Alternative f => f a -> f b -> f (Either a b)
eitherA u v = (Left <$> u) <|> (Right <$> v)

-- Made-up name.
plusWith :: Alternative f => (Either a b -> c) -> f a -> f b -> f c
plusWith f u v = f <$> eitherA u v

plusWith, however, isn't helpful in your case. An Either a b -> c can't produce a c by combining an a with a b, except by discarding one of them. You'd rather have something that takes a These a b -> c argument, as using These a b can express the both-a-and-b case. It happens that a plusWith that uses These instead of Either is very much like alignWith:

-- Taken from the class definitions:
class Functor f => Semialign f where
    align :: f a -> f b -> f (These a b)
    align = alignWith id

    alignWith :: (These a b -> c) -> f a -> f b -> f c
    alignWith f a b = f <$> align a b

class Semialign f => Align f where
    nil :: f a

Alternative is a class for monoidal functors from Hask-with-(,) to Hask-with-Either. Similarly, Align is a class for monoidal functors from Hask-with-(,) to Hask-with-These, only it also has extra idempotency and commutativity laws that ensure the unbiased behaviour you are looking for.

One aspect of Align worth noting is that it is closer to Alternative than to Applicative. In particular, the identity of the These tensor product is Void rather than (), and accordingly nil, the identity of align, is an empty structure rather than a singleton. That might come as a surprise, given that align and friends offer us greedy zips and zips with padding, and that zip is often thought of as an applicative operation. In this context, I feel it might help to mention a fact about ZipList. ZipList offers a zippy Applicative instance for lists in lieu of the default, cartesian product one:

GHCi> fzip [1,2] [3,9,27]
[(1,3),(1,9),(1,27),(2,3),(2,9),(2,27)]
GHCi> getZipList $ fzip (ZipList [1,2]) (ZipList [3,9,27])
[(1,3),(2,9)]

What is less widely known is that ZipList also has a different Alternative instance:

GHCi> [1,2] <|> [3,9,27]
[1,2,3,9,27]
GHCi> [3,9,27] <|> [1,2]
[3,9,27,1,2]
GHCi> getZipList $ ZipList [1,2] <|> ZipList [3,9,27]
[1,2,27]
GHCi> getZipList $ ZipList [3,9,27] <|> ZipList [1,2]
[3,9,27]

Instead of concatenating the lists, it pads the first list with a suffix of the second one to the larger of the two lengths. (It is a fitting instance for the type because it follows the left distribution law .) align for lists is somewhat similar to (<|>) @ZipList, except that it isn't biased towards either list:

GHCi> align [1,2] [3,9,27]
[These 1 3,These 2 9,That 27]
GHCi> align [3,9,27] [1,2]
[These 3 1,These 9 2,This 27]

Upvotes: 0

dfeuer
dfeuer

Reputation: 48611

If I understand you correctly, you may be interested in the Semialign class from Data.Align, which offers zip-like operations that don't drop missing elements:

class Functor f => Semialign f where
  align :: f a -> f b -> f (These a b)
  align = alignWith id

  alignWith :: (These a b -> c) -> f a -> f b -> f c
  alignWith f as bs = f <$> align as bs

You can write

alignBasic :: Semialign f => (a -> a -> a) -> f a -> f a -> f a
alignBasic f = alignWith $ \case
  This a -> a
  That a -> a
  These a1 a2 -> f a1 a2
-- or just
alignBasic f = alignWith (mergeThese f)

Since Maybe is an instance of Semialign, alignBasic can be used at type

alignBasic :: (a -> a -> a) -> Maybe a -> Maybe a -> Maybe a

Upvotes: 3

amalloy
amalloy

Reputation: 92077

If you are willing to accept a different type signature, working with a Semigroup instance instead of with an arbitrary function f, then what you are looking for is the Option newtype from Data.Semigroup:

Prelude Data.Semigroup> Option Nothing <> Option Nothing
Option {getOption = Nothing}
Prelude Data.Semigroup> Option (Just [1]) <> Option Nothing
Option {getOption = Just [1]}
Prelude Data.Semigroup> Option Nothing <> Option (Just [2])
Option {getOption = Just [2]}
Prelude Data.Semigroup> Option (Just [1]) <> Option (Just [2])
Option {getOption = Just [1,2]}

For an arbitrary function you need something that is pretty specialized to Maybe - I don't really see how it could work for an arbitrary Applicative, or Alternative.

Upvotes: 4

Related Questions