CODEWITHSUNDEEP
haskellrecursioncount
Steven
Steven

Reputation: 1173

Haskell recursive counting

I just started learning Haskell (I'm trying to make a mastermind solver).

I have to count how many times one color from a lists occurs in another list:

reaction [Green, Purple, Green, Green] [Purple, Green, Blue, Yellow] 0

Would have to give me the result "2", Because "Green" from list 1 occurs 1 time in list 2, and the same goes for "Purple". So I've written a little piece of code:

reaction [] ys n = n
reaction (x:xs) ys n = foldr (\y _ -> if x == y then reaction (filter' x xs) ys n + 1 else reaction xs ys n + 0) n ys

filter' c xs = filter(\x -> x /= c) xs

It takes the head X from list 1 and compares it to every element in list 2, if it is the same it will filter all the values from list 1 which are corresponding to X (so it won't count any duplicates) and add + 1 to "N". However it gives me the result "1", and I really can't seem to find out why... I hope anyone can help me! Steven

Upvotes: 1

Views: 1150

Answers (2)

jub0bs
jub0bs

Reputation: 66404

In your code, you throw away the second argument (the accumulator) of the function that you pass to foldr:

foldr (\y _ -> ...

I can't think of a use case of foldr where you would want to do that.

Your question seems to stem from a misunderstanding of foldr. Are you sure you understand what this function does? If you have any doubt, read, for instance, this section of the Wikipedia page on folds; you should find the diagram explaining what a right fold is particularly illuminating.

If I correctly understand what you want to do, the following approach should do the job:

import Data.List

data Color = Blue | Green | Purple | Yellow
  deriving Eq

reaction :: Eq a => [a] -> [a] -> Int -> Int
reaction xs ys n = foldr (\x acc -> length (filter (== x) ys) + acc) n $ nub xs

For information, the nub function takes a list and returns a list formed by removing all duplicates element from it; it is exported by the Data.List module.

Test in GHCi:

λ> reaction [Green, Purple, Green, Green] [Purple, Green, Blue, Yellow] 0
2

Upvotes: 1

crockeea
crockeea

Reputation: 21811

First, filter' is just filter (/= x).

From your description of the problem, a clearer way to write this (at least initially) is

reaction [] ys n = n
reaction (x : xs) ys n | x `elem` ys = reaction (filter (/= x) xs) ys (n+1)
                       | otherwise = reaction xs ys n

This doesn't appear to be a simple fold to me because the list you are iterating over (xs) changes as you iterate over it.

Upvotes: 1

Related Questions