Ziplists with longest-style applicative behaviour

Question

Is it possible in Haskell do define a type similar to ziplist, in which operation a <*> b will produce list which is as long as the longest of a and b.

It is clear that in this case we must assume that a and b are lists over something like Monoid, so tentative declaration is:

   instance Monoid a => Applicative (ZList a) where ...

which clearly will not typecheck. Another tentative approach is to use GADTs with constrained constructors, something like

   data ZList a where 
     Z:: ZList a
     S:: Monoid a => a-> (ZList a) -> (ZList a)

but then I stuck on a stage of making it Functor because we cannot guarantee that in fmap::(a -> b) -> f a -> f b, b will be Monoid.

Clearly, this question extends to wider class of algebraic datatypes for which we want to define "pointwise" applicative behavior in which we produce output with shape similar to the union of shapes of the arguments.

Answer 1

First, what you really want is probably Default, not Monoid - you have no use for mappend.

I don't think anything useful is possible in Applicative itself. That said, I can define a version of (<*>) (called (<#>)) with extra constraints that lets me do what I think you have in mind.

Why there is no point in making a new data type

First, suppose we were to take the ExistentialQuantification route in hopes of pushing our constraints into the data and having legitimate instances of Functor and Applicative. That blows up as soon as we try to define fmap:

{-# LANGUAGE ExistentialQuantification #-}
data ZipMonList a = Default a => ZipMonList [a]

-- Woops, we still need a constraint for `Default b`
fmap :: Default b => (a -> b) -> ZipMonList a -> ZipMonList b
fmap f (ZipMonList xs) = ZipMonList (f xs)

So, with that settled, let's stick to the ZipList type (since we want the same (<$>) anyways) and just define our new constrained version of (<*>), called (<#>).

Make (<#>) for ZipList

Underlying ZipLists (<*>) is the zipWith function. We need something similar for (<#>), but that extends lists. Then, (<#>) looks a lot like (<*>):

import Control.Applicative (ZipList(..))
import Data.Default

-- Like 'zipWith', but has maximum length
zipWith' :: (Default a, Default b) => (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' f []     []     = []
zipWith' f (x:xs) []     = f x   def : zipWith' f xs []
zipWith' f []     (y:ys) = f def y   : zipWith' f [] ys
zipWith' f (x:xs) (y:ys) = f x   y   : zipWith' f xs ys

-- same fixity as <*>
infixl 4 <#> 

-- like '(<*>)', but uses 'zipWith'' instead of 'zipWith'
(<#>) :: (Default a, Default b) => ZipList (a -> b) -> ZipList a -> ZipList b
ZipList fs <#> ZipList xs = ZipList (zipWith' id fs xs)

And I can do a test run on tuples:

ghci> (,,) <$> ZipList [1.2,3.4,5.6,7.8,9.1] <#> ZipList [[(),()],[()],[(),(),()]] <#> ZipList [1,2,3,4]
ZipList {getZipList = [(1.2,[(),()],1),(3.4,[()],2),(5.6,[(),(),()],3),(7.8,[],4),(9.1,[],0)]}

Key takeaway point: this is not an Applicative, but still doable.

Answer 2

I just have a few notes for you, things to think about.

The definition of the typeclass that will allow this is known as the Constrained Typeclass Problem, and there have been a few approaches.

I notice that you have only specified that the resulting list should be as long as the longer of the two lists, but you haven't said what the remaining elements should be. At that point you might as well use the applicative

ZipList :*: Const (MaxPos Int)

(where :*: is functor product, and MaxPos is a monoid I just made up taking the maximum on nonnegative numbers) which keeps track of the "length" separately, because the remaining elements will be meaningless.

Rather, I suspect you mean something where the remaining elements are preserved in some sense, i.e. so

(*) <$> [2,3,4] <*> [4] = [8,3,4]

and also

(+) <$> [2,3,4] <*> [4] = [6,3,4]

So if we were to "fill in" missing elements in the former case we should fill them in with 1, and in the latter we should fill them in with 0. This starts to show us a different aspect of the problem; we need to pick identity elements based on the operation, or just "leave alone" the remaining elements (which constrains the operations to type a -> a -> a). This is looking less possible, it'd be interesting to explore more. That's all I've got for now, sorry.