Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why does 'Data.List.null' use a 'foldr'?

Tags:

haskell

In my beginner perception, one could implement Data.List.null as:

null [] = True
null _ = False

Looking up the actual source in Hackage, I see:

null = foldr (\_ _ -> False) True

I find this curious, surely I'm missing something I should learn about, but what?

like image 870
metaleap Avatar asked Dec 05 '16 16:12

metaleap


1 Answers

null is a method of the Foldable class:

GHCi> :t null
null :: Foldable t => t a -> Bool

The implementation you quote is the default one, meant to work for all instances of Foldable even if they do not define a specific implementation:

class Foldable t where
    -- etc.
    null :: t a -> Bool
    null = foldr (\_ _ -> False) True
    -- etc.

The list instance, though, overrides the default implementation:

instance Foldable [] where
    -- etc.
    null    = List.null
    -- etc.

List.null, in turn, is defined in GHC.List in the simpler way that you expected:

null                    :: [a] -> Bool
null []                 =  True
null (_:_)              =  False
like image 110
duplode Avatar answered Sep 17 '22 08:09

duplode