[Haskell-beginners] Data type definition for a list of elements of alternating types?

[Brent Yorgey]

On Wed, Apr 02, 2014 at 09:52:21PM -0400, Jacek Dudek wrote:
> -- As an exercise I wanted to define a datatype that is an alternating
> list of elements of two different types. The best that I could do are
> the type definitions below:
> 
> module BiList
>     ( BiList (..)
>     , AList (EmptyA)
>     , BList (EmptyB)
>     ) where
> 
> data BiList a b
>     = Empty
>     | BA (AList a b)
>     | BB (BList a b)
> 
> data AList a b
>     = EmptyA
>     | AL a (BList a b)
> 
> data BList a b
>     = EmptyB
>     | BL b (AList a b)
> 
> (<#) :: a -> (BList a b) -> (AList a b)
> a <# bs = AL a bs
> 
> (<@) :: b -> (AList a b) -> (BList a b)
> b <@ as = BL b as
> 
> infixr 5 <#
> infixr 5 <@
> 
> example :: BiList Int Char
> example = BA $ 1 <# 'a' <@ 2 <# 'b' <@ 3 <# 'c' <@ 4 <# 'd' <@ EmptyA

As David McBride noted, AList and BList are isomorphic (up to the
order of their arguments) so you don't need both.  Unfortunately you
do still need BiList; but you don't need its Empty.  So:

data BiList a b
  = BA (AltList a b)
  | BB (AltList b a)

data AltList a b
  = Empty
  | Cons a (AltList b a)

So this addresses (2) but not (1).  I don't think there is any way
around the need for (1).  (Note, however, that you do still have two
distinct representations of the empty list: BA Empty and BB Empty.  I
can't see any way around that either.)

-Brent