[Haskell-beginners] Data type definition for a list of elements of alternating types?
Brent Yorgey
byorgey at seas.upenn.edu
Fri Apr 4 16:19:20 UTC 2014
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
More information about the Beginners
mailing list