Search code examples
listhaskelltypestype-parameterrecursive-datastructures

Is it possible to make a recursive datatype in haskell that accepts more than one specific type?

Say for instance I want to make a list type that allows for flexible nesting like so:

[[['a'],'a'],'a']

Would it be possible to implement this in haskell? How would I go about writing it's type signature? Any help would be awesome!!!

Solution

  • This isn't a list so much as a tree. As such you can represent it with a tree data type. One example is the rose tree in containers, whose definition is approximately:

    data Tree a = Node a [Tree a]

    But maybe more suitable tree type in this case would be something like this (which is incidentally the free monad of []; the rose tree is the cofree comonad):

    data Tree a = Leaf a | Node [Tree a]

    Using this type you could represent your "list" like this, for example:

    Node [Node [Node [Leaf 'a'], Leaf 'a'], Leaf 'a']