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

[Brent Yorgey]

Ah, yes, having a nonempty AltList and moving Empty to BiList is a
good idea.  You still do need two different constructors BA and BB,
but yes, overall this seems like a nice way to encode things.

Exercise: write a conversion function

  fromList :: [Either a b] -> Maybe (BiList a b)

which returns Just when the input list really is alternating, and
Nothing otherwise.

-Brent

On Thu, Apr 03, 2014 at 10:04:04PM -0400, Jacek Dudek wrote:
> 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
> >
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners