[Haskell-cafe] Applicative but not Monad

[David Menendez]

On Fri, Oct 30, 2009 at 12:59 PM, Luke Palmer <lrpalmer at gmail.com> wrote:
> On Fri, Oct 30, 2009 at 10:39 AM, Tom Davie <tom.davie at gmail.com> wrote:
>> Of note, there is a sensible monad instance for zip lists which I *think*
>> agrees with the Applicative one, I don't know why they're not monads:
>> instance Monad (ZipList a) where
>>   return = Ziplist . return
>>   join (ZipList []) = ZipList []
>>   join (ZipList (a:as)) = zlHead a `zlCons` join (map zlTail as)
>
> IIRC, that doesn't satisfy the associativity law, particularly when
> you are joining a list of lists of different lengths.  2 minutes of
> experimenting failed to find me the counterexample though.

This works fine for infinite lists, since an infinite list is
equivalent to Nat -> a.

With finite lists, this implementation hits problems with calling head
on empty lists. If I rewrite it to avoid that problem, the
associativity law fails.

tail' [] = []
tail' (_:as) = as

diag ((a:_):bs) = a : diag (map tail' bs)
diag _ = []

bind :: [Int] -> (Int -> [Int]) -> [Int]  -- monomorphic for QuickCheck
bind m f = diag (map f m)

Prelude Test.QuickCheck Test.QuickCheck.Function> quickCheck $ \m
(Function _ f) (Function _ g) -> bind (bind m f) g == bind m (\x ->
bind (f x) g)
*** Failed! Falsifiable (after 16 tests and 23 shrinks):
[1,0]
{0 -> [-13,0], 1 -> [0]}
{-13 -> [], 0 -> [0,0]}

The left side is [0,0], the right side is [0].

-- 
Dave Menendez <dave at zednenem.com>
<http://www.eyrie.org/~zednenem/>