Warm tip: This article is reproduced from serverfault.com, please click

haskell Own version of Elem function using Foldl

发布于 2020-11-29 13:37:55

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]
   |            

                                                       ^^
Questioner
enneenne
Viewed
0
Willem Van Onsem 2020-11-29 21:45:34

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.