Geek Answers Handbook

Haskell - Nested Empty Lists

Hi, Haskellers and Haskellettes,

while reading http://learnyouahaskell.com/ my friend had a problem:

Is it possible in Haskell to write a recursive function that returns True if all sub-sub-signatures are empty. My first guess was - it should be - but I have a big problem, just writing a 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 does not work - :-)

I came up with something like

  • folding with concat - to get one long list
    (giving me implementation problems)
  • or creating an infinite tree data type - and do it from a list
    (not yet implemented)

but the latter sounds a bit like overkill for this problem. what are your ideas - on a sunny Sunday, for example :-)

Thanks in advance

as a reaction to all comments - this is a bad style, which I would add is just an experiment !
Do not try to do it at home! ; -)

+7
source share
2 answers

How about class?

 {-# 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 $ ([[[[()]]]] :: [[[[()]]]])
+5
source

This is not possible using parametric polymorphism, due to the following.

Consider the following values:

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

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

Now, if you have this type, then null1 z will be equal to null1 x , because they differ only in the values ​​of the list items that are abstracted from. (Still not close to formal evidence :()

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

+4
source

More articles:


All Articles