3

I was reading about Applicative in Haskell from Hutton's Programming in Haskell. To understand it better I came up with the following definition for Applicative for lists:

-- Named as pure' and "app" to avoid confusion with builtin versions 
class Applicative' f where
 pure' :: a -> f a
 app :: f (a->b) -> f a -> f b

instance Applicative' [] where
 pure' x = [x]
 app _ [] = []
 app [g] (x:xs) = [(g x)] ++ app [g] xs
 app (g:gs) (x:xs) = [(g x)] ++ app gs xs

-- fmap functions could be defined as:
fmap1' :: (Applicative' f)=>(a->b) -> f a -> f b
fmap1' g x = app (pure' g) x

fmap2' :: (Applicative' f)=>(a->b->c) -> f a -> f b -> f c
fmap2' g x y = app (app (pure' g) x) y


fmap3' :: (Applicative' f)=>(a->b->c->d) -> f a -> f b -> f c -> f d
fmap3' g x y z = app (app (app (pure' g) x) y) z

An example of use of fmap2' is as follows:

Ok, one module loaded.
*Main> g = \x y -> x*y
*Main> arr1 = [1,2,3]
*Main> arr2 = [4,5,6]
*Main> fmap2' g arr1 arr2
[4,10,18]
*Main>

But the standard definition for Applicative function <*> for a list is defined as:

gs <*> xs = [g x | g <- gs, x <- xs]

Thus resulting in 

pure (*) <*> [1,2], [3,4]
[3,4,6,8]

I was wondering why it defined in the manner of for all arr1, for all arr2, apply function rather than take corresponding elements arr1, arr2 apply function. I guess the first definition is probably more useful? Are there any specific reasons for this choice?

coder_bro
  • 10,503
  • 13
  • 56
  • 88
  • 1
    http://hackage.haskell.org/package/base-4.11.1.0/docs/Control-Applicative.html#t:ZipList – leftaroundabout Jun 05 '18 at 13:56
  • @duplode I think it's not quite a duplicate, because the instance asked about here isn't really `ZipList` (though that seems to be the idea). – leftaroundabout Jun 05 '18 at 13:59
  • @leftaroundabout Oh, the `(:[])` versus `repeat` issue shows up here, too. Well-spotted; reopening. (For the sake of completeness, the suggested question was [*Why ZipList is not the default Applicative Instance for List*](https://stackoverflow.com/questions/37627513/why-ziplist-is-not-the-default-applicative-instance-for-list).) – duplode Jun 05 '18 at 14:03
  • 2
    List has already an implementation for Monad which forces the Application instance (`ap` can me written in term of `return` and `>>=` for any Monad and as to be identical to `<*>`. – mb14 Jun 05 '18 at 14:10

2 Answers2

6

This is basically the ZipList applicative instance. The main difference is

pure x = repeat x

instead of your pure x = [x].

That's needed to fulfill the applicative laws. Namely, your implementation violates the interchange law:

[id, id] <*> pure 1 ≡ [id,id] <*> [1]
                    ≡ [id 1] ++ ([id] <*> [])
                    ≡ [id 1] ++ []
                    ≡ [1]
‡ pure ($ 1) <*> [id,id] ≡ [1,1]

The requirement for an infinite pure makes ZipList somewhat funny in practice. The standard implementation is basically the most natural finite-only implementation. Arguably, it would be better if there were separate types for finite arrays and possibly-infinite lists in the prelude, and if lists had the ZipList instance.

Going by the comments, your implementation actually is fine too though, if only you pad out both lists if needed. Nice!

leftaroundabout
  • 117,950
  • 5
  • 174
  • 319
  • 1
    Another fix might be to make `app` symmetric in its handling of list ends. e.g. `app [] [] = []; app [f] [x] = [f x]; app [f] xs = map f xs; app fs [x] = map ($x) fs; app (f:fs) (x:xs) = f x : app fs xs`. Keep `pure x = [x]` as in the question. This seems like it would be a genuinely different `Applicative` than either the standard instance or `ZipList`, would work okay for *finite-only* lists, and my intuition says it shouldn't violate any of the laws (though I didn't actually check that). – Daniel Wagner Jun 05 '18 at 17:47
  • @DanielWagner my intuition says it would likely violate the composition law... it seems to behave inconsistently WRT whether to trim the longer list or to extend the shorter. But I'm not sure, it might actually be isomorphic to `MaybeT (WriterT (Min Word) ZipList)` or something like that. – leftaroundabout Jun 05 '18 at 19:53
  • 1
    It is no more inconsistent than is required by the type: empty lists propagate (as they must in any total instance), and otherwise the shorter list is always extended. – Daniel Wagner Jun 05 '18 at 20:43
  • QuickCheck says it satisfies all the laws, with one minor tweak: it needs two base cases for `[] _` and `_ []` instead of just the one `[] []` base case. [Here's some code.](https://lpaste.net/2886508826557677568) – Daniel Wagner Jun 05 '18 at 21:01
  • 2
    The (tweaked) instance is indeed legal -- `(<*>)` boils down to extending the shorter list and then using the `ZipList` instance; doing so can't possibly fail wrt associativity. That's neat. – duplode Jun 06 '18 at 05:20
  • Thanks to the above comments, I was able to change the definition to perform extension of the shorter list: `instance Applicative' [] where pure' x = [x] app _ [] = [] app [g] [x] = [(g x)] app (g:gs) [x] = [(g x)] ++ app gs [x] app [g] (x:xs) = [(g x)] ++ app [g] xs app (g:gs) (x:xs) = [(g x)] ++ app gs xs` – coder_bro Jun 06 '18 at 08:05
  • @Ngm You also need an `app [] _ = []` case. Otherwise looks good to me! – Daniel Wagner Jun 06 '18 at 13:17
  • It's not ZipList. – pigworker Jun 06 '18 at 16:47
  • an anti-ziplist – coder_bro Jun 07 '18 at 03:23
5

The basic reason why Applicative [] has the generate-all-possible-combinations behaviour, rather than any kind of zippy behaviour, is that Applicative is a superclass of Monad and is intended to behave in accordance with the Monad instance when one exists. Monad [] treats lists as failure-and-prioritized-choice, so the Applicative [] instance does, too. People often refactor monadic code using the applicative interface to reduce the number of intermediate names needed for values, and to increase opportunities for parallelism. It would be pretty scary if that caused a significant shift in the functional semantics.

That aside, the truth is, you're spoilt for choice for Applicative [] instances, and even more so if you consider empty/nonempty and finite/coinductive/infinite variations. Why is that?

Well, as I mentioned in this answer, every Applicative f begins its life as a Monoid (f ()), combining the shapes of the data, before we start to worry about the values. Lists are a case in point.

[()] is basically the type of numbers. Numbers are monoids in lots of ways.

Taking Applicative [] from Monad [] amounts to choosing the monoid generated by 1 and *.

Meanwhile, Applicative ZipList exploits Haskell's coinductive conflation and amounts to choosing the monoid generated by infinity and minimum.

The question proposes an instance which is not lawful, but is close to one that is. You'll notice <*> isn't defined for an empty list of functions, but for nonempty lists of functions, it pads out to match the list of arguments. Asymmetrically, it truncates when the arguments run out. Something's not quite right.

Two candidate fixes follow.

One is to truncate on empty on both sides, and then you must take pure = repeat and you have ZipList.

The other is to rule out empty lists and pad on both sides. Then you get the Applicative generated from the Monoid on positive numbers generated by 1 and maximum. So it's not ZipList at all. That's the thing I called PadMe in this answer. The reason you need to rule out 0 is that for every position in the output of <*>, you need to point to the position in both inputs where the function and its arguments (respectively) come from. You can't pad if you have nothing to pad with.

It's a fun game. Pick a Monoid on numbers and see if you can grow it into an Applicative for lists!

pigworker
  • 43,025
  • 18
  • 121
  • 214
  • 1
    Although every `instance Applicative []` gives rise to a monoid on `[()]`, it is not at all clear to me that the other way is always possible. In particular, the types require that `[] <*> _ = []` and `_ <*> [] = []` in any (total) instance; but there are many monoids on numbers for which `0` is not an annihilator. Indeed, after `Product` (your first proposed example), the obvious next choice would be `Sum`, which does not have this property. So "numbers are monoids in lots of ways" doesn't imply "`[]` is `Applicative` in lots of ways" (even though the latter turns out to be true). – Daniel Wagner Jun 07 '18 at 15:01
  • On the other hand, your observation that any monoid on the positive numbers can be turned into a monoid on the naturals (that *does* have `0` as an annihilator, though you didn't mention it) was quite interesting, and further thought on a variant of `Sum` led me to the following bizarre `Applicative` instance: `pure x = [x]; fs@(f:ft) <*> xs@(x:_) = map f xs ++ map ($x) ft` (+ base cases). The laws do appear to hold (according to QuickCheck, I'm too lazy for the full proof...), but I find its behavior pretty strange, and you were right: it was a fun game! – Daniel Wagner Jun 07 '18 at 15:17
  • 1
    @DanielWagner that sems similar to the applicative instance of this monad discussed in [this reddit post](https://www.reddit.com/r/haskell/comments/7oym07/maybe_i_also_found_a_monad/). – Potato44 Jun 14 '18 at 07:32