76

Going through Haskell's documentation is always a bit of a pain for me, because all the information you get about a function is often nothing more than just: f a -> f [a] which could mean any number of things.

As is the case of the <|> function.

All I'm given is this: (<|>) :: f a -> f a -> f a and that it's an "associative binary operation"...

Upon inspection of Control.Applicative I learn that it does seemingly unrelated things depending on implementation.

instance Alternative Maybe where
    empty = Nothing
    Nothing <|> r = r
    l       <|> _ = l

Ok, so it returns right if there is no left, otherwise it returns left, gotcha.. This leads me to believe it's a "left or right" operator, which kinda makes sense given its use of | and |'s historical use as "OR"

instance Alternative [] where
    empty = []
    (<|>) = (++)

Except here it just calls list's concatenation operator... Breaking my idea down...

So what exactly is that function? What's its use? Where does it fit in in the grand scheme of things?

duplode
  • 33,731
  • 7
  • 79
  • 150
Electric Coffee
  • 11,733
  • 9
  • 70
  • 131
  • 8
    Very little is required for extremely generic operations such as `<|>`. The right way of "understanding" them is to understand the concrete instances. I.e., if you want to use `<|>` on `Maybe`, then understand what it does for `Maybe` ... – kosmikus Sep 23 '14 at 18:47
  • 4
    well it's the `<>` operation of a `Monoid` which is polymorphic in `a`. – felix-eku Sep 23 '14 at 18:59
  • 3
    The list instance is because there's an interpretation of lists as a non-deterministic choice of elements. If you read `<|>` to mean "orelse" then for two non-deterministic lists you get the non-deterministic possibilities from either, thus `(++)`. – AndrewC Sep 23 '14 at 19:54
  • 1
    ah, but that's all you need to know about it. Associative binary operation with a unit is a monoid. List monoid has empty list as a unit and `(++)` as the associative binary operation. – Sassa NF Sep 23 '14 at 22:22
  • @SassaNF But you can make at least two completely different Applicative & Alternative instance for lists a la ZipList. See [this question](http://stackoverflow.com/questions/18210765). – AndrewC Sep 24 '14 at 06:24
  • @AndrewC sure, there is more than one monoid that can be defined. – Sassa NF Sep 24 '14 at 09:46

4 Answers4

78

Typically it means "choice" or "parallel" in that a <|> b is either a "choice" of a or b or a and b done in parallel. But let's back up.

Really, there is no practical meaning to operations in typeclasses like (<*>) or (<|>). These operations are given meaning in two ways: (1) via laws and (2) via instantiations. If we are not talking about a particular instance of Alternative then only (1) is available for intuiting meaning.

So "associative" means that a <|> (b <|> c) is the same as (a <|> b) <|> c. This is useful as it means that we only care about the sequence of things chained together with (<|>), not their "tree structure".

Other laws include identity with empty. In particular, a <|> empty = empty <|> a = a. In our intuition with "choice" or "parallel" these laws read as "a or (something impossible) must be a" or "a alongside (empty process) is just a". It indicates that empty is some kind of "failure mode" for an Alternative.

There are other laws with how (<|>)/empty interact with fmap (from Functor) or pure/(<*>) (from Applicative), but perhaps the best way to move forward in understanding the meaning of (<|>) is to examine a very common example of a type which instantiates Alternative: a Parser.

If x :: Parser A and y :: Parser B then (,) <$> x <*> y :: Parser (A, B) parses x and then y in sequence. In contrast, (fmap Left x) <|> (fmap Right y) parses either x or y, beginning with x, to try out both possible parses. In other words, it indicates a branch in your parse tree, a choice, or a parallel parsing universe.

Luis Casillas
  • 29,802
  • 7
  • 49
  • 102
J. Abrahamson
  • 72,246
  • 9
  • 135
  • 180
  • but in the case of `<*>`, it more or less always does the same. `(Just (+3)) <*> (Just 4)` gives `Just 7` and `[(+3)] <*> [1..3]` gives `[4,5,6]` just like you'd expect from a `map` operation. Its meaning doesn't really change from instance to instance – Electric Coffee Sep 23 '14 at 18:58
  • 6
    @ElectricCoffee That isn't strictly true. For instance, consider first that the type [`ZipList a`](http://hackage.haskell.org/package/base-4.7.0.1/docs/Control-Applicative.html#t:ZipList) is essentially the same as `[a]`. Now `[(+1),(+2)] <*> [1,2] = [2,3,3,4]` while `ZipList [(+1),(+2)] <*> ZipList [1,2] = ZipList [2,4]`. Thus, it's not always so completely clear what `(<*>)` should mean. – J. Abrahamson Sep 23 '14 at 19:13
  • 1
    I'd just like to suggest that the meaning of `(<*>)` has common motifs, yes—and those motifs are exposed through careful examination of its laws—but I would have a hard time swallowing that it does basically the same thing instance to instance. – J. Abrahamson Sep 23 '14 at 19:20
  • Someone showed a good example using `foldl1` with `(<|>)` which actually showcases some of its power – Electric Coffee Sep 23 '14 at 19:27
  • 1
    Associativity of `(<|>)` implies that folds are useful. Folds "fix" a linear tree structure (totally left nested or totally right nested) and only due to associativity do we know we can ignore the meaning of this possible rearrangement. – J. Abrahamson Sep 23 '14 at 19:36
41

(<|>) :: f a -> f a -> f a actually tells you quite a lot, even without considering the laws for Alternative.

It takes two f a values, and has to give one back. So it will have to combine or select from its inputs somehow. It's polymorphic in the type a, so it will be completely unable to inspect whatever values of type a might be inside an f a; this means it can't do the "combining" by combining a values, so it must to it purely in terms of whatever structure the type constructor f adds.

The name helps a bit too. Some sort of "OR" is indeed the vague concept the authors were trying to indicate with the name "Alternative" and the symbol "<|>".

Now if I've got two Maybe a values and I have to combine them, what can I do? If they're both Nothing I'll have to return Nothing, with no way to create an a. If at least one of them is a Just ... I can return one of my inputs as-is, or I can return Nothing. There are very few functions that are even possible with the type Maybe a -> Maybe a -> Maybe a, and for a class whose name is "Alternative" the one given is pretty reasonable and obvious.

How about combining two [a] values? There are more possible functions here, but really it's pretty obvious what this is likely to do. And the name "Alternative" does give you a good hint at what this is likely to be about provided you're familiar with the standard "nondeterminism" interpretation of the list monad/applicative; if you see a [a] as a "nondeterministic a" with a collection of possible values, then the obvious way for "combining two nondeterministic a values" in a way that might deserve the name "Alternative" is to produce a nondeterminstic a which could be any of the values from either of the inputs.

And for parsers; combining two parsers has two obvious broad interpretations that spring to mind; either you produce a parser that would match what the first does and then what the second does, or you produce a parser that matches either what the first does or what the second does (there are of course subtle details of each of these options that leave room for options). Given the name "Alternative", the "or" interpretation seems very natural for <|>.

So, seen from a sufficiently high level of abstraction, these operations do all "do the same thing". The type class is really for operating at that high level of abstraction where these things all "look the same". When I'm operating on a single known instance I just think of the <|> operation as exactly what it does for that specific type.

nbro
  • 15,395
  • 32
  • 113
  • 196
Ben
  • 68,572
  • 20
  • 126
  • 174
  • 2
    The ingredients are merely the name of the typeclass, the type signature of the operator and some concrete examples of specific instances. The result is a recipe to understand the `Alternative` typeclass. I wonder if this approach is sufficient to explain other generalized FP concepts. Thanks! –  Nov 05 '16 at 12:30
15

An interesting example of an Alternative that isn't a parser or a MonadPlus-like thing is Concurrently, a very useful type from the async package.

For Concurrently, empty is a computation that goes on forever. And (<|>) executes its arguments concurrently, returns the result of the first one that completes, and cancels the other one.

danidiaz
  • 26,936
  • 4
  • 45
  • 95
14

These seem very different, but consider:

Nothing <|> Nothing == Nothing
     [] <|>      [] ==      []

Just a  <|> Nothing == Just a
    [a] <|>      [] ==     [a]

Nothing <|> Just b  == Just b
     [] <|>     [b] ==     [b]

So... these are actually very, very similar, even if the implementation looks different. The only real difference is here:

Just a  <|> Just b  == Just a
    [a] <|>     [b] ==     [a, b]

A Maybe can only hold one value (or zero, but not any other amount). But hey, if they were both identical, why would you need two different types? The whole point of them being different is, you know, to be different.

In summary, the implementation may look totally different, but these are actually quite similar.

MathematicalOrchid
  • 61,854
  • 19
  • 123
  • 220