Count non-empty lists in a lists of lists

user_12118780 0
Viewed 458

I am trying to count the number of non-empty lists in a list of lists with recursive code. My goal is to write something simple like:

prod :: Num a => [a] -> a
prod [] = 1
prod (x:xs) = x * prod xs

I already have the deifniton and an idea for the edge condition:

nonEmptyCount :: [[a]] -> Int
nonEmptyCount [[]] = 0

I have no idea how to continue, any tips?

list haskell
3 Answers

I think your base case, can be simplified. As a base-case, we can take the empty list [], not a singleton list with an empty list. For the recursive case, we can consider (x:xs). Here we will need to make a distinction between x being an empty list, and x being a non-empty list. We can do that with pattern matching, or with guards:

nonEmptyCount :: [[a]] -> Int
nonEmptyCount [] = 0
nonEmptyCount (x:xs) = -- …

That being said, you do not need recursion at all. You can first filter your list, to omit empty lists, and then call length on that list:

nonEmptyCount :: [[a]] -> Int
nonEmptyCount = length . filter (…)

here you still need to fill in ….

user_675790

Old fashion pattern matching should be:

import Data.List

nonEmptyCount :: [[a]] -> Int
nonEmptyCount []     = 0
nonEmptyCount (x:xs) = if null x then 1 + (nonEmptyCount xs) else nonEmptyCount xs
user_71280340

The following was posted in a comment, now deleted:

countNE = sum<$>(1<$)<<<(>>=(1`take`))

This most certainly will look intimidating to the non-initiated, but actually, it is equivalent to

        = sum <$> (1 <$) <<< (>>= (1 `take`))
        = sum <$> (1 <$) . (take 1 =<<)
        = sum . fmap (const 1) . concatMap (take 1)
        = sum . map (const 1) . concat . map (take 1)

which is further equivalent to

countNE xs  =  sum . map (const 1) . concat $ map (take 1) xs
            =  sum . map (const 1) $ concat [take 1 x | x <- xs]
            =  sum . map (const 1) $ [ r | x <- xs, r <- take 1 x]
            =  sum $ [const 1 r | (y:t) <- xs, r <- take 1 (y:t)]   -- sneakiness!
            =  sum   [const 1 r | (y:_) <- xs, r <- [y]]
            =  sum   [const 1 y | (y:_) <- xs]
            =  sum   [ 1        | (_:_) <- xs]    -- replace each
                         --   non-empty list
                         --             in 
                         --                xs
               -- with 1, and
           --  sum all the 1s up!
            =  (length . (take 1 =<<)) xs
            =  (length . filter (not . null)) xs

which should be much clearer, even if in a bit sneaky way. It isn't recursive in itself, yes, but both sum and the list-comprehension would be implemented recursively by a given Haskell implementation.

This reimplements length as sum . (1 <$), and filter p xs as [x | x <- xs, p x], and uses the equivalence not (null xs) === (length xs) >= 1.

See? Haskell is fun. Even if it doesn't yet feel like it, but it will be. :)

user_8498910
Related