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

[Denis Kasak]

On 3 April 2014 22:58, Brent Yorgey <byorgey at seas.upenn.edu> wrote:
>
> 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.)

You could move the Empty constructor to BiList while making AltList a
non-empty list, i.e.

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

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

-- 
Denis Kasak