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