Why can (Cons i (q i)) -> (Cons o (q o)) have an arrow instance, but not [i] -> [o]

Learn
1

I’m reading Arrows and Computation by Ross Paterson (2003), and in it he has a couple exercises where you need to produce Arrow instances for peculiar types (in fact, in 2026 you also need to make a Category instance to complete the exercise).

In one case, the type he provides is so,

newtype ListMap i o = LM ([i] -> [o])

and he claims that one cannot make an Arrow instance for this type. I did, though maybe it violates an Arrow or Category law.

instance Category ListMap where
  id = LM $ id
  (LM f) . (LM g) = LM $ f . g

instance Arrow ListMap where
  arr = LM . fmap
  first (LM f) = LM $ \bsAndDs -> zip (f (fmap fst bsAndDs)) (fmap snd bsAndDs)

However, he then asks for an instance of StreamMap.

data Stream a = Cons a (Stream a)
newtype StreamMap i o = SM (Stream i -> Stream o)

My question is, how is StreamMap different from ListMap that Paterson expects it should have an Arrow instance, but ListMap should not? [] and Stream are (as far as I’m aware) both cons lists and so I’m surprised that they’re different enough to not allow this instance.

2

The difference is that ListMap is not necessarily length-preserving. Consider

f = LM (const [])
g = LM (const [0])

Then

ghci> run (LM h) = h
ghci> f = LM (const [])
ghci> g = LM (const [0])
ghci> run (first (f >>> g)) [(1,'x')]
[(0,'x')]
ghci> run (first f >>> first g) [(1,'x')]
[]

This violates the law that first (f >>> g) = first f >>> first g.