Trying to implement elem with a foldl any

user_13601696 0
Viewed 130

I am new in haskell, i am trying right now to implement "elem" with a "foldl any" in Haskell, but it won't work.

My any :

any' p = foldl' (\y x -> p x || y) False

and this is my elem :

elem' y = foldl' (\z x -> x==y || z) False

my first try was this :

elemfa p y = not (any' (\x -> not (p x)) y)

but i am getting an error everytime

haskell
1 Answers

Your elemfa :: Foldable f => (a -> Bool) -> f a -> Bool makes use of any'''', but that function does not exists. If you rewrite this to:

elemfa :: Foldable f => (a -> Bool) -> f a -> Bool
elemfa p y = not (any' (\x -> not (p x)) y)

You can make it more clean with:

elemfa :: Foldable f => (a -> Bool) -> f a -> Bool
elemfa p = not . any' (not . p)

It will at least produce output. This function will check if all elements satisfy the given predicate.

That being said, it is not ideal to use a foldl here for any, elem and elemfa, since that means it will keep iterating over the list, even if it found an element that satisfies the predicate. If you thus work on an infinite list, it will not return True, even if it found an element:

Prelude Data.List> elem' 1 (1 : repeat 2)
… keeps looking …

Here foldr :: Foldable f => (a -> b -> b) -> b -> f a -> b can be used to stop searching once the element has been found, for example:

any' :: Foldable f => (a -> Bool) -> f a -> Bool
any' p = foldr (\x -> (p x ||)) False

elem' :: (Foldable f, Eq a) => a -> f a -> Bool
elem' x = any' (x==)

all' :: Foldable f => (a -> Bool) -> f a -> Bool
all' p = not . any (not . p)
user_675790
Related