I'm trying to create my own version of elem
function, which returns True
or False
based on if the element x is inside the given array.
elem' :: Eq(t)=>t->[t]->Bool
elem' x xs = or [foldl (\acc -> \a -> if a == x then True else False) [] xs]
What I'm trying to do here is to fill the array using foldl with True/False values and then make or
function, which returns True if at least one of them is True (so what I want to get). However, this code results in the following compilation error:
main.hs:11:71: error:
* Couldn't match expected type `Bool' with actual type `[a0]'
* In the second argument of `foldl', namely `[]'
In the expression:
foldl (\ acc -> \ a -> if a == x then True else False) [] xs
In the first argument of `or', namely
`[foldl (\ acc -> \ a -> ...) [] xs]'
|
11 | elem' x xs = or [foldl (\acc -> \a -> if a == x then True else False) [] xs]
|
^^
The idea of using a foldl
is not to make a list of elements, and thus not to use or
.
If you make use of foldl
, then in case a == x
fails, you look if the elem
on the previous elements was succesful, so we return acc
in that case. Furthermore you can not use []
as the "start value" for the accumulator, since the foldl
is supposed to return a Bool
, not a list:
elem' :: (Foldable f, Eq t) => t -> f t -> Bool
elem' x xs = foldl (\acc a -> if a == x then True else acc) False xs
Here it is however not a good idea to use foldl
, since that means we will enumerate over the entire list. If we make use of foldr
, we can stop from the moment we have found an element, so we can rewrite this to:
elem' :: (Foldable f, Eq t) => t -> f t -> Bool
elem' x = foldr (\e -> if x == e then const True else id) False
If we thus check:
elem' 1 ([1,4,2,5] ++ repeat 3)
It will return True
for the foldr
approach, whereas it will loop for the foldl
approach.