CODEWITHSUNDEEP
haskelloptimization
J-S
J-S

Reputation: 1023

Checking for empty list in Haskell: Is (length list == 0) or (list == []) more efficient?

Say I want to check if a list is empty in a guard in Haskell there are two options:

  1. length list == 0
  2. list == []

Which of these two logical tests are more efficient? I'm inclined to say the empty list test because relies on more basic constructs rather than the prelude function length but I'm not sure.

Upvotes: 30

Views: 64582

Answers (3)

dfeuer
dfeuer

Reputation: 48611

As others have indicated, the best way to check if a list is empty (and nothing more) is to use

null :: Foldable f => f a -> Bool

which can be used at type

null :: [a] -> Bool

If you want to check if a list is empty because you want to look at its elements otherwise, you generally should be using pattern matching instead:

f [] = something
f (x : xs) = something using x and/or xs

If you want to compare the lengths of two lists (and no more), the best way is usually something like

compareLength :: [a] -> [b] -> Ordering
compareLength [] [] = EQ
compareLength [] (_ : _) = LT
compareLength (_ : _) [] = GT
compareLength (_ : xs) (_ : ys) =
  compareLength xs ys

The best way to check how the length of a list compares to a certain number is

compareToLength :: Foldable f
                => f a -> Int -> Ordering
compareToLength = foldr go (compare 0) where
  go _ r n | n <= 0 = GT
           | otherwise = r $! n - 1

Upvotes: 13

manonthemat
manonthemat

Reputation: 6251

You can check if your list is empty in constant time with null list, which returns a boolean.

Prelude> null []
True
Prelude> null [1]
False
Prelude> null ""
True
Prelude> null "Test"
False

Upvotes: 23

Cactus
Cactus

Reputation: 27636

length list == 0 needs to traverse the whole list to get its length, which means it is O(n). list == [] yields an Eq constraint on the element type. null list runs in constant time and has no typeclass constraints.

However, there is a neat trick to do something like length list == 0 which has the advantage that it generalizes nicely to length list1 == length list2 without going through the longer list: you can use genericLength with a sufficiently lazy representation of natural numbers so that comparison will only force traversing the shorter of the lists.

One example is to use the Natural type:

import Data.Number.Natural
import Data.List (genericLength)

nats :: [Int]
nats = iterate succ 0

areThereTenNats :: Bool
areThereTenNats = genericLength nats >= (10 :: Natural)

Upvotes: 26

Related Questions