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')
CodePudding user response:
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
filter
ing the list so to keep only the elements you want to count. Then, usedrop (n-1) xs
to dropn-1
elements (if any), and check if the resulting list is not empty (usenull
). Note thatdrop
ping more elements than those in the list is not an error, and it will result in an empty list.
CodePudding user response:
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 ==)