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

Jacek Dudek jzdudek at gmail.com
Thu Apr 3 01:52:21 UTC 2014

-- 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

-- There are two things that I don't like about this implementation.

-- (1) The BA and BB constructors that must be applied on top of
instances of (AList a b) and (BList a b) to lift them to be of type
(BiList a b).

-- (2) Having three different constructors for an empty list: Empty,
EmptyA, EmptyB, where ideally I would just have one.

-- Is it possible to get around either of these annoyances with some
type theory gymnastics? Maybe something like the function fromIntegral
(the mechanics of which I don't really understand at this point)?

More information about the Beginners mailing list