Creating higher order functions using Haskell

Question

I have recently been teaching myself Haskell, and one of my exercises was to implement a function that takes two arguments: a list and a single value. The function would check if the value is in the list twice or more. I cannot use the function element or member.

I tried removing the values that are not equal to the value. Then checking for the size of the new list if its more than 1 then it outputs True if not it outputs False. I having problem trying to use a function inside a function.

remove2 val [] = []
remove2 val (x:xs) = if ( not (x == val))
                         then remove2 val xs 
                         else x:remove2 val xs

isMemberTwice :: (Eq val) => val -> [val] -> Bool 
isMemberTwice val [] = False
isMemberTwice val (x:xs) 
     | ( >= (length (remove2 val [val])) 2) = True
         | otherwise = a `isMemberTwice’` xs

Answer 1

There's an easier way really:

isMemberTwice needle haystack = n >= 2
  where n = length $ filter (== needle) haystack

However, the downside with this approach is that, if you pass it a really long list, it'll evaluate the entire list, which is unnecessary: you only need to see if there are at least 2 occurrences of needle.

So a better solution is to avoid using length on the filtered list and instead just use pattern match: if it matches (_:_:_), there must be at least 2 occurrences:

isMemberTwice needle haystack = case occurrences of (_:_:_) -> True
                                                    _       -> False
  where occurrences = filter (== needle) haystack

Answer 2

I will add to Daniel Jour's answer starting from its final note:

One could rewrite this using higher order functions such as fold though I'm not sure how one could implement the short circuit behaviour (stopping as soon as two instances have been found) then.

Let's transform the original code:

memtwice value list = scan value list False
 where scan _ [] _ = False
       scan v (x:xs) True =
         if v == x then True
          else scan v xs True
       scan v (x:xs) False =
         scan v xs (v == x)

Moving to boolean operators we get:

memtwice value list = scan value list False
 where scan _ [] _ = False
       scan v (x:xs) True  = v == x || scan v xs True
       scan v (x:xs) False = scan v xs (v == x)

Now, the parameter v is always value, so let's remove the parameter.

memtwice value list = scan list False
 where scan [] _ = False
       scan (x:xs) True  = value == x || scan xs True
       scan (x:xs) False = scan xs (value == x)

Introducing an explicit lambda for the last argument (not really needed, but helps readability):

memtwice value list = scan list False
 where scan [] = (\_ -> False)
       scan (x:xs) = \found -> if found 
                                 then value == x || scan xs True
                                 else scan xs (value == x)

We now see that the last recursion pattern is a foldr: indeed we have a base-case definition for scan [], and the recursive case scan (x:xs) is defined only in terms of scan xs.

memtwice value list = foldr go (\_ -> False) list False
 where go x next = \found -> if found 
                                 then value == x || next True
                                 else next (value == x)

Note that foldr seems to be called with four parameters. This is because go x next produces a function, hence foldr go (\_ -> False) list does as well. We can now revert the explicit lambda.

memtwice value list = foldr go (\_ -> False) list False
 where go x next True  = value == x || next True
       go x next False = next (value == x)

Finally, note that since || has short-circuiting behaviour, we did achieve an equivalent foldr to the original code.

Answer 3

Every function on a list can be written in this form:

f     [] = ...   -- also called the "base case"
f (a:as) = ...   -- also called the recursive case

Let's apply this idea to writing a function which determine the number 3 appears in a list at least once:

hasA3 :: [Int] -> Bool
hasA3  []     = ...
hasA3  (a:as) = ...

Clearly hasA3 [] = False. I'll leave you to figure out how to write the recursive case. Hint: the function might have to check if a == 3.

Now let's write a function which determines if a list contains two or more threes. Again we start with the two cases:

hasTwo3s :: [Int] -> Bool
hasTwo3s []     = ...
hasTwo3s (a:as) = ...

Again, the base case is easy. Hints for the recursive case: you might have to check if a == 3 and then you might want to use the hasA3 function.

Answer 4

A higher order function is a function that takes another function as argument or returns another function.

Your problem at hand is easily solvable using a short recursive function:

memtwice :: (Eq a) => a -> [a] -> Bool
memtwice value list = scan value list False
 where scan _ [] _ = False
       scan v (x:xs) True =
         if v == x then True
          else scan v xs True
       scan v (x:xs) False =
         scan v xs (v == x)

The scan is a function that carries state information (whether there has already been found one instance) as additional parameter.

One could rewrite this using higher order functions such as fold though I'm not sure how one could implement the short circuit behaviour (stopping as soon as two instances have been found) then.