haskell - nested empty lists

Question

Hello Haskellers and Haskellettes,

when reading http://learnyouahaskell.com/ a friend of mine came up with a problem:

Is it possible in Haskell to write a recursive function that gives True if all sub-sub-_-sublists are empty. My first guess was - should be - but i have a big problem just writing the type annotation.

he tried something like

nullRec l = if null l
               then True
               else if [] `elem` l
                    then nullRec (head [l]) && nullRec (tail l)
                    else False

which is - not working - :-)

i came up with something like

• folding with concat - to get a a single long list
  (giving me problems implementing)
• or making an infinite treelike datatype - and making this from the list
  (haven't implemented yet)

but the latter sound a bit like overkill for this problem. what is your ideas - on a sunny sunday like this ;-)

Thanks in advance

---

as a reaction to all the comments - this being bad style i'd like to add this is just an experiment!
DO not try this at home! ;-)

Answer 1

How about a typeclass?

{-# LANGUAGE FlexibleInstances, OverlappingInstances #-}

class NullRec a where
  nullRec :: a -> Bool

instance NullRec a => NullRec [a] where
  nullRec [] = True
  nullRec ls = all nullRec ls

instance NullRec a where
  nullRec _  = False

main = print . nullRec $ ([[[[()]]]] :: [[[[()]]]])

Answer 2

This is not possible using parametric polymorphism only, because of the following.

Consider these values:

x = [8] :: [Int]
y = [3.0] :: [Double]
z = [[]] :: [[Int]]

Obviously, you want your function to work with both x and y, thus its type must be null1 :: [a] -> Bool. (Can someone help me make this argument look formal? How can I show that this is the unique most specific context-less type unifiable with [Int] -> Bool and [Double] -> Bool? Is there a name for that relation between types?)

Now, if you have this type, then null1 z will be equal to null1 x because they differ only in values of the list elements, which are abstracted away from. (Not even close to formal proof again :()

What you want for z is null2 :: [[a]] -> Bool, which will differ in behaviour, and thus giving null1 and null2 the same name will require overloading. (see the FUZxxl's answer)