Comparing lists in Haskell

Question

I have to define a function called zeros which takes input of two lists and returns a boolean which returns True if the number 0 appears the same amount of times in each list and false otherwise.

This is the last question in my homework and and I have managed to solve the question get it to work but I wondered if anybody can spot ways in which to reduce the amount of code. Any ideas are appreciated.
My code so far is as follows:

x :: Int
x = 0 
instances::[Int]->Int
instances [] = 0
instances (y:ys)
    | x==y = 1+(instances ys)
    | otherwise = instances ys



zeros :: [Int] -> [Int] -> Bool
zeros [] [] = False
zeros x y
       | ((instances x) == (instances y)) = True
       | otherwise = False

Seems to me that zeros [] [] should equal True? At least it doesn't seem any more false than zeros [1] [], which your code would consider True. I'm not sure you even need to handle the case zeros [] []... — sblom
– sblom, Commented Apr 23, 2012 at 23:49
no i don't think it should be because if the lists were empty then they would contain no zeros at all hence it would be false — blane clorley
– blane clorley, Commented Apr 23, 2012 at 23:51
I'm having trouble convincing myself that "no zeros" and "zero zeros" aren't the same thing. For example, zeros [1] [] would return True the way you have written things (both have zero zeros). Whereas zeros [] [] would return False (despite that both have zero zeros). — sblom
– sblom, Commented Apr 23, 2012 at 23:54

senderle · Accepted Answer · 2012-04-24 00:26:39Z

Without giving too much away, since this is homework, here are a few hints.

Do you know about list comprehensions yet? They would be useful in this case. For example, you could combine them with an if expression to do something like this:

*Main> let starS s = [if c == 's' then '*' else ' ' | c <- s]
*Main> starS "schooners"
"*       *"

You can even use them to do filtering. For example:

*Main> let findFives xs = [x | x <- xs, x == 5]
*Main> findFives [3,7,5,6,3,4,5,7,5,5]
[5,5,5,5]

Neither of these is a complete answer, but it shouldn't be hard to see how to adapt these structures to your situation.

You should also think about whether you actually need a guard here! For example, here's a function written with a guard in the same style as yours:

lensMatch [] [] = True
lensMatch xs ys
             | ((length xs) == (length ys)) = True
             | otherwise = False

Here's a function that does the same thing!

lensMatch' xs ys = length xs == length ys

You can see that they are the same; testing the first:

*Main> lensMatch [1..4] [1..4]
True
*Main> lensMatch [1..4] [1..5]
False
*Main> lensMatch [] [1..5]
False
*Main> lensMatch [] []
True

And testing the second:

*Main> lensMatch' [1..4] [1..4]
True
*Main> lensMatch' [1..4] [1..5]
False
*Main> lensMatch' [] [1..5]
False
*Main> lensMatch' [] []
True

Finally, I agree very strongly with sblom's comment above; zeros [] [] should be True! Think about the following statement: "For each item x in set s, x > 0". If set s is empty, then the statement is true! It's true because there are no items in s at all. This seems to me like a similar situation.

Abizern · Accepted Answer · 2012-04-23 23:59:30Z

1

Have you thought of doing this in one pass by filtering each list to get just the zeroes and then comparing the length of the lists to see if they are equal?

zeroCompare xs ys = cZeroes xs == cZeroes ys
  where
    cZeroes as = length $ filter (== 0) as

edited Apr 23, 2012 at 23:59

answered Apr 23, 2012 at 23:51

Abizern

152k41 gold badges209 silver badges260 bronze badges

4 Comments

blane clorley Over a year ago

I did consider that and i actually think thats what my tutor will be looking for but i was unsure to implement the filter and guard in one sweep

blane clorley Over a year ago

what is the significance of 'as' ?

Abizern Over a year ago

What's the significance of xs and ys? None. It's just a way of stating an input parameter. I could have written in it points free style as cZeroes = length . filter (== 0), but I thought it would be easier for you to understand it with a parameter.

blane clorley Over a year ago

ah i actually understood it in a points free style. thanks a lot though dude!

Luis Casillas · Accepted Answer · 2012-04-24 01:00:19Z

1

I can't believe nobody has suggested to use foldr yet. Not the shortest or best definition, but IMO the most educational:

instances :: Eq a => a -> [a] -> Int
instances n = foldr incrementIfEqual 0
    where incrementIfEqual x subtotal
              | x == n = subtotal + 1
              | otherwise = subtotal

zeros :: Num a => [a] -> [a] -> Bool
zeros xs ys = instances 0 xs == instances 0 ys

Though for a really brief definition of instances, what I came up with is basically the same as Abizern:

instances :: Eq a => a -> [a] -> Int
instances x = length . filter (==x)

answered Apr 24, 2012 at 1:00

Luis Casillas

30.3k7 gold badges51 silver badges103 bronze badges

Comments

Landei · Accepted Answer · 2012-04-24 08:33:45Z

0

Instead of length and filter, you can take the result of a predicate p, convert it to 0 or 1, and sum the result:

count p = sum . map (fromEnum.p)

--or

import Data.List
count p = foldl' (\x -> (x+).fromEnum.p) 0

In your case, p is of course (==0). Converting Bool to Int using fromEnum is a very useful trick.

answered Apr 24, 2012 at 8:33

Landei

54.6k13 gold badges105 silver badges195 bronze badges

Comments

Landei · Accepted Answer · 2012-04-24 08:47:01Z

0

Another idea would be to deal with both list simultaneously, which is a little bit lengthy, but easy to understand:

zeros xs ys = cmp xs ys == 0 where
  cmp (0:xs) ys = cmp xs ys + 1
  cmp xs (0:ys) = cmp xs ys - 1
  cmp (_:xs) ys = cmp xs ys
  cmp xs (_:ys) = cmp xs ys
  cmp [] []     = 0

answered Apr 24, 2012 at 8:47

Landei

54.6k13 gold badges105 silver badges195 bronze badges

Comments

Brooke · Accepted Answer · 2018-02-17 21:33:54Z

I would break the problem down into smaller problems involving helper functions.

This is how I would break it down:

Main function to compare two counts
Count helper function

First: You need a way to count the amount of zeroes in a list. For example, I would approach this by doing the following if searching for the number of 0 in an integer list:

count :: [Int] -> Int
count xs = foldl (\count num -> if num == 0 then (count + 1) else count) 0 xs

Second: You need a way to compare the count of two lists. Essentially, you need a function that takes two lists in as parameters, calculates the count of each list, and then returns a boolean depending on the result. For example, if each list is an int list, corresponding with my count example above:

    equalZeroes :: [Int] -> [Int] -> Bool
    equalZeroes x y = (count x) == (count y)

You could also define count under the where keyword inside the equalZeroes function like so:

equalZeroes :: [Int] -> [Int] -> Bool
equalZeroes x y = (count x) == (count y)
    where
        count :: [Int] -> Int
        count xs = foldl (\count num -> if num == 0 then (count + 1) else count) 0 xs

When running this code, calling the function as so would get the desired boolean values returned:

equalZeroes [0,1,4,5,6] [1,4,5,0,0]
-> False

 equalZeroes [0,1,4,5,6] [1,4,5,0]
 -> True

Collectives™ on Stack Overflow

Comparing lists in Haskell

6 Answers 6

Comments

4 Comments

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

Comments

4 Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related