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

Think about what the type of such a function should be (if you implement it on normal lists)! — yatima2975
– yatima2975, Commented Jul 10, 2011 at 14:46
Sick or not, you're on the right track! It's easy enough to write a family of functions nullRec2 :: [[a]] -> Bool, nullRec3 :: [[[a]]] -> Bool and so on (try a couple!), but you can't get them to fit a single type signature easily. You either need a tree type like data Tree a = Branch [Tree a] | Node a or maybe there's something possible with typeclasses (haven't thought much about this approach yet). — yatima2975
– yatima2975, Commented Jul 10, 2011 at 14:58
@FUZxxl's answer will work. I consider the need to solve this problem a red flag -- if it were more than just an experiment, I would suggest rethinking the architecture. — luqui
– luqui, Commented Jul 10, 2011 at 16:21
To reinforce luqui's point, think about what the values of nullRec [""] and nullRec [empty :: ByteString] should be. You shall see that there is no good answer. — Rotsor
– Rotsor, Commented Jul 10, 2011 at 16:30

fuz · Accepted Answer · 2011-07-10 15:34:52Z

5

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 $ ([[[[()]]]] :: [[[[()]]]])

answered Jul 10, 2011 at 15:34

fuz

94.8k27 gold badges216 silver badges391 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Tsuyoshi Ito Over a year ago

More precisely, you are using not only a type class but also the GHC extension OverlappingInstances. Without this extension, even using a type class cannot achieve what is required in the question. This strongly suggests that if anyone has to implement this (other than as an experiment), the program is probably not designed in the right way.

Rotsor · Accepted Answer · 2011-07-10 23:33:42Z

4

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)

edited Jul 10, 2011 at 23:33

answered Jul 10, 2011 at 16:03

Rotsor

13.8k6 gold badges46 silver badges58 bronze badges

3 Comments

luqui Over a year ago

I find that argument fairly convincing.

Rotsor Over a year ago

I feel like null1 . (:[]) :: a -> Bool brings us closer to formal proof, but I still don't know how to make the last step (showing that a -> Bool is the same as Bool).

yatima2975 Over a year ago

It's sort of a free theorem in reverse, but the largest lower bound of Int and Double (on the lattice of Haskell context-free types, with substition as the relationship) is a, as you can't substitute type variables in both of them (there aren't any!) and end up with the same type. Or am I getting my up & down directions mixed up?

Collectives™ on Stack Overflow

haskell - nested empty lists

2 Answers 2

1 Comment

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related