Haskell - Checking if a list contains an element atleast N times

user_17119512 0
Viewed 132

I am writing a function that checks if a list containts an element at least N times

atLeastNtimes :: Eq a => Int -> a -> [a] -> Bool
atLeastNtimes n a l = n <= (sum [1 | x <- l, (x == a)])

It is working fine with finite list, but I am struggling to make this work for infinite lists, for example:

atLeastNtimes 100 'a' (repeat 'a')
list-comprehension functional-programming haskell
2 Answers

Here are a few possible alternative approaches:

  • Define your function recursively, without ever trying to inspect the full list but only the needed prefix.

  • Start by filtering the list so to keep only the elements you want to count. Then, use drop (n-1) xs to drop n-1 elements (if any), and check if the resulting list is not empty (use null). Note that dropping more elements than those in the list is not an error, and it will result in an empty list.

user_32349590

We can separate the problem into two parts. The first just checks whether a list is long enough.

-- | Check whether the length of a list
-- is at least a certain value.
lengthAtLeast :: Int -> [a] -> Bool
lengthAtLeast n0 xs0 = foldr go stop xs0 n0
  where
    stop n = n <= 0

    go _ _ n | n <= 0 = True
    go _ r n = r (n - 1)

The second is filtering, which filter does for you. So

atLeastNtimes :: Eq a => Int -> a -> [a] -> Bool
atLeastNtimes n a = lengthAtLeast n . filter (a ==)
user_14776670
Related