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

Jacek Dudek jzdudek at gmail.com
Fri Apr 4 02:04:04 UTC 2014

Thanks David, that's really clever! I was trying to do it without any
auxiliary data types, but couldn't see how I could use an instance of
(BiList a b) in the constructor expression for (BiList a b) without
losing the property that the list elements alternate from one type to
the other with each new element.

But now I see that when you write (BiList b a) in the constructor
expression, that's written in the context provided by the (data BiList
a b) line, so having the type variables in the opposite order makes
all the difference.

Brent, David's definition actually solved both (1) and (2), try it out!

On 4/3/14, Denis Kasak <denis.kasak at gmail.com> wrote:
> 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
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners

More information about the Beginners mailing list