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

Question

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

Answer 1

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

Answer 2

You need to define your own datatype with different value constructors.

From ghci:

Prelude> data Val a = Val a | List [Val a] deriving (Show)
Prelude> [List [List [Val 'a']], Val 'a']
[List [List [Val 'a']],Val 'a']

And its type:

Prelude> :t [List [List [Val 'a']], Val 'a']
[List [List [Val 'a']], Val 'a'] :: [Val Char]

Also, checkout how JSON is represented in Real World Haskell: http://book.realworldhaskell.org/read/writing-a-library-working-with-json-data.html (search for data JValue to find the relevant data type)