Identifying recursive/nested types in Haskell (like type synonyms)

Question

Short Question (edited):

Is it possible to define a function's type signature so that it accepts nested types with arbitrary depth? I am looking for the behaviour of type synonyms (NOT newtype) but identifying nested/recursive types.

For example a function defined as f :: NestedList a -> b should be able to be called with [a], [[a]], [[[a]]]... and so on.

Long Question (original):

Since it is impossible to use type synonyms in Haskell with recursive types, is there a solution for the following problem?

I need a synonym like NestedList a that would identify [a], [[a]], [[[a]]]... and so on, in function type definitions. An example of function needed to be implemented is:

   flatten :: NestedList a -> [a]

This post shows a solution for flatten using the MultiParamTypeClasses language extension, but it does not particularly solve my problem. I need to define functions outside of a class.

EDIT:

flatten is just an example for a function definition, I am not interested in the function as such. I need a mechanism to define a function with NestedList a and call it with a parameter like [[a]] or [[[a]]], without the need of an additional type constructor, get methods, etc. As suggested in the title, I need something that behaves like a type synonym on nested lists, mainly for giving type signatures for functions that work on [...[a]...] while making sure the base type is a.

According to Haskell's strong-typed system this is impossible and this post sheds some light on the reasons why. I am just asking if there is a macro/synonym like mechanism or workaround, or a language extension that permits me to do that.

Answer 1

Are you looking for something like this?

data NestedList a = List [NestedList a] | Element a

flatten :: NestedList a -> [a]
flatten (Element x) = [x]
flatten (List xs)   = concatMap flatten xs

EDIT

As user2407038 has suggested, if you are interested in using the Foldable (include {-# LANGUAGE DeriveFoldable #-} at the top of your file and import Data.Foldable) GHC extension, you can just do this

data NestedList a = List [NestedList a] | Element a deriving (Foldable)

And then there is a function called toList already defined in Foldable which will produce the same output as flatten from above.

EDIT 2

Here is something else of interest concerning the updated question. Ideally, it would be nice to be able to define an instance of Foldable with

instance (Foldable t, Functor t, Foldable t') => Foldable (t . t')

where (t . t') a is a type synonym for t (t' a) (a sort of type level composition). This obviously doesn't work, and I'm inclined to think there is a logical explanation as to why introducing this would break Haskell in some fundamental way, but I can't think of it. However, there is a package called Control.Compose which defines something almost like that (except for the fact we would like a type synonym as opposed to a newtype).

newtype (g :. f) a = O { unO :: g (f a) }

This lets us write the following:

toList $ (O) [[1,2,3,4],[4,5,6]]
toList $ (O . O) [[[1],[2,3,4]],[[4],[5,6]]]
toList $ (O . O . O) [[[[1]],[[2,3],[4]]],[[[4]],[[5,6]]]]

Which is also of interest.