Prevent inadvertently using different type class instance

Question

I expect the following behavior from the applicative instance of my ZipList':

zipListApplyTest = fs <*> xs
  where fs = ZipList' [negate, id]
        xs = ZipList' [1..5]

-- Result: ZipList' [-1,2]

This was my first attempt:

newtype ZipList' a = ZipList' [a]
                   deriving (Eq, Show)

instance Functor ZipList' where
  fmap f (ZipList' xs) = ZipList' $ fmap f xs

instance Applicative ZipList' where
  pure x = ZipList' [x]

  ZipList' (f:fs) <*> ZipList' (x:xs) =
     ZipList' $ f x : (fs <*> xs) -- <-- the bug is here
  ZipList' [] <*> _ = ZipList' []
  _ <*> ZipList' []  = ZipList' []

-- Unexpected result: ZipList' [-1,2,3,4,5]

After some head scratching, I realized that inside the applicative instance of ZipList' I accidentally used the wrong <*>:

In the line marked with the bug is here, I applied the <*> that belongs to the built-in list type [] instead of applying <*> of ZipList' recursively.

This is why the second function id was applied to the entire rest of the list, instead of only the second element, 2.

This yielded the expected result:

ZipList' fs <*> ZipList' xs = ZipList' $ zipApply fs xs
  where zipApply :: [(a -> b)] -> [a] -> [b]
        zipApply (f:fs) (x:xs) = f x : zipApply fs xs
        zipApply _ _           = []

Is there a compiler flag, language idiom, or other technique that would have prevented this bug or would have made it easier to spot?

I'm on GHC 8.2.2.

I am not really sure what you mean with "I applied the <*> that belongs to the built-in list type?" — willeM_ Van Onsem
– willeM_ Van Onsem, Commented Apr 12, 2018 at 20:20
@WillemVanOnsem: In the line where it says the bug is here the apply method (<*>) of []'s applicative type class instance is called. With "built-in" I meant the list type from base. — Matthias Braun
– Matthias Braun, Commented Apr 12, 2018 at 20:23
On a tangential note, pure for ZipList should be repeat, and not (:[]) -- to see why, try to verify the applicative laws. (Great question, by the way!) — duplode
– duplode, Commented Apr 13, 2018 at 2:43

HTNW · Accepted Answer · 2018-04-13 02:53:59Z

12

We can do this:

{-# LANGUAGE PatternSynonyms, ViewPatterns #-}
-- at very top of file ^
-- ...
-- pick whatever names/operators you want
-- synonym signatures are given in GADT-like syntax
-- ZCons decomposes a ZipList' a into an a and a ZipList' a
-- (assuming it succeeds). This is the syntax even for pattern synonyms that
-- can only be used as patterns
-- (e.g. pattern Fst :: a -> (a, b); pattern Fst a <- (a, _)).
pattern ZCons :: a -> ZipList' a -> ZipList' a
-- xs needs to be a ZipList', but it's only a [a], so we uglify this synonym
-- by using the newtype wrapper as a view
pattern ZCons x xs <- ZipList' (x:(ZipList' -> xs))
-- views aren't in general invertible, so we cannot make this an automatically
-- bidirectional synonym (like ZNil is). We can give an explicit version
  where ZCons x (ZipList' xs) = ZipList' $ x:xs
-- simple enough that we can use one definition for both pattern and expression
pattern ZNil :: ZipList' a
pattern ZNil = ZipList' []
{-# COMPLETE ZNil, ZCons #-}
-- ZNil and ZCons cover all ZipLists

instance Applicative ZipList' where
  pure x = ZipList' $ repeat x
  -- these are bidirectional
  (ZCons f fs) <*> (ZCons x xs) = ZCons (f x) (fs <*> xs)
  _ <*> _ = ZNil

edited Apr 13, 2018 at 2:53

answered Apr 12, 2018 at 20:57

HTNW

29.7k2 gold badges37 silver badges63 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

chi Over a year ago

Ohh, I did not know about COMPLETE ! Very useful, thanks.

chi · Accepted Answer · 2018-04-12 21:06:07Z

As a variant of AJFarmar's answer, you can keep your definition of ZipList' exploiting a [a] list inside, and instead declare pattern synonyms to pretend the type was declared as

data ZipList' a = ZipCons a (ZipList' a) | ZipNil

In that way, if you limit yourself in using these "pretend" constructors when you write your instances, you can not inadvertently involve a list.

{-# LANGUAGE PatternSynonyms, ViewPatterns #-}
{-# OPTIONS -Wall #-}
module ZipList where

newtype ZipList' a = ZipList' { unZipList' :: [a] }
                   deriving (Eq, Show)

Here are the pattern synonyms. We need to be a bit careful here since we need to convert lists to zip-lists as needed.

pattern ZipCons :: a -> ZipList' a -> ZipList' a
pattern ZipCons x xs <- ZipList' (x : (ZipList' -> xs))
  where ZipCons x xs = ZipList' (x : unZipList' xs)

pattern ZipNil :: ZipList' a
pattern ZipNil = ZipList' []

We can leave the functor instance as it was, exploiting the Functor [] instance. Here, we do want to call the list fmap. Otherwise, we could use the "pretend" constructors, but we'd have to re-implement it.

instance Functor ZipList' where
  fmap f (ZipList' xs) = ZipList' $ fmap f xs

Finally, the applicative instance can use only the pretend constructors.

instance Applicative ZipList' where
  pure x = ZipCons x ZipNil

  ZipCons f fs <*> ZipCons x xs = ZipCons (f x) (fs <*> xs)
  _            <*> _            = ZipNil

To me a major downside of using the pattern synonyms is that the exhaustiveness checker gets easily confused, triggering spurious warnings. Above, if we replace the _ <*> _ case with the two obvious cases involving ZipNil, we trigger a warning.

(Update: HTNV used a COMPLETE pragma to silence the warning, which looks very nice! I did not know about that.)

Apart from that, pattern synonyms allow to offer a quite elegant interface. I wish they were used more often in the Haskell ecosystem.

AJF · Accepted Answer · 2018-04-12 20:28:07Z

1

No, you cannot prevent this in general. You must simply write your instances carefully.

That being said, one quick way to work around this problem would be to redefine your datatype; instead of putting it in terms of lists, make a new list type:

data Ziplist a = Nil | Cons a (Ziplist a)
-- (Instances etc follow)

This avoids the possibility for this kind of error. However, this isn't necessarily the best idea, since this requires function rewrites and so on.

You could just write tests. Which is best. So write tests. HSpec is the most used test framework as far as I'm aware, so that would be a good place to start.

answered Apr 12, 2018 at 20:28

AJF

11.9k2 gold badges41 silver badges64 bronze badges

Comments

dfeuer · Accepted Answer · 2018-04-15 02:52:58Z

1

This isn't really a general answer, but in this particular case I think by far the best and easiest thing is to just use zipWith, which is what the base library does.

instance Applicative ZipList where
  pure x = ZipList (repeat x)
  ZipList fs <*> ZipList xs = ZipList (zipWith ($) fs xs)

answered Apr 15, 2018 at 2:52

dfeuer

48.8k5 gold badges69 silver badges171 bronze badges

Collectives™ on Stack Overflow

Prevent inadvertently using different type class instance

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related