5 Replies - 1162 Views - Last Post: 19 April 2015 - 06:06 PM

#1 case1001  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 26-March 15

Haskell: Check if a number appears in a list 0 or 1 times

Posted 26 March 2015 - 06:42 AM

There are different ways i approached this but since i started using Haskell just yesterday i am in the beginer stage and not sure if that is the way to do it. This is not my homework or anything but it will help me for a solution on a question i am stuck on.

atmostonce:: [Int] -> Int -> Bool

atmostonce [] y = True

atmostonce (x:lx) y 

 | (x==y) && (atmostonce lx y) = False

 | otherwise = True




atmostonce:: [Int] -> Int -> Bool

atmostonce y 1

 | y`elem` 1 = True

 | y`elem` 0 = True

 | otherwise = False




These are the 2 ways i have tried and i have looked online as well but no result.

This post has been edited by sepp2k: 26 March 2015 - 07:03 PM
Reason for edit:: Added language to title


Is This A Good Question/Topic? 0
  • +

Replies To: Haskell: Check if a number appears in a list 0 or 1 times

#2 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2506
  • View blog
  • Posts: 3,959
  • Joined: 21-June 11

Re: Haskell: Check if a number appears in a list 0 or 1 times

Posted 26 March 2015 - 07:16 PM

It would help if you specified in what way your attempts did not do what you want (and what error message you're getting if any), but let's take a look at your first attempt:

  • If the list is empty, the result is True. That seems correct.
  • When it is not empty, the first element is equal to y and y appears at most once in the remaining elements, the result is False. That seems wrong. What if x appears zero times in the remaining elements? That'd mean that y appeared one time in total, meaning the function should be true, but it's not because the condition (x==y) && (atmostonce lx y) is met and you thus produce False as the result.
  • When the first element is not equal to y, the result is True. That also seems incorrect. That means you'd get True for the list [notY, y, y, y] even though y appears three times in it. You have to keep looking at the remaining items in the list until you find more than one or you've reached the end of the list.


Your second attempt is clearly a type error. The first argument of elem should be the item you're looking for and the second argument should be the list. You supplied the list first, so that will not compile. Your usage of elem also doesn't seem helpful as finding out whether the list contains the number 1 or the number 0 does not seem relevant to the problem at hand. Unless I completely misunderstood your problem description, you want to whether x appears 1 or 0 times - not whether 1 or 0 appear in the list. Lastly you only provided a pattern for when the second argument is 1, so you'd get an exception when you call the function with any argument other than 1.
Was This Post Helpful? 0
  • +
  • -

#3 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon


Reputation: 6966
  • View blog
  • Posts: 14,572
  • Joined: 16-October 07

Re: Haskell: Check if a number appears in a list 0 or 1 times

Posted 27 March 2015 - 11:41 AM

Well, if you're not looking to avoid standard functions, then I bet a couple of dropWhile and a drop would do the trick.

Consider:
Prelude> let xs = [1..8] ++ [1..3]
Prelude> xs
[1,2,3,4,5,6,7,8,1,2,3]
Prelude> dropWhile (/=3) xs
[3,4,5,6,7,8,1,2,3]
Prelude> dropWhile (/=13) xs
[]
Prelude>



If you're looking to roll your own, consider more functions. A "atmostn" is actually a more useful and clearly written function. Then your function becomes:
atmostonce xs x = atmostn xs x 1



You see, if you have a counter to deplete....

Hope this helps.

This post has been edited by baavgai: 27 March 2015 - 11:42 AM

Was This Post Helpful? 0
  • +
  • -

#4 gonzaw  Icon User is offline

  • New D.I.C Head

Reputation: 7
  • View blog
  • Posts: 46
  • Joined: 18-December 12

Re: Haskell: Check if a number appears in a list 0 or 1 times

Posted 18 April 2015 - 01:41 PM

How about this?:

atMostOnce :: Eq a => a -> [a] -> Bool
atMostOnce x xs = (<= 1) $ length $ filter (== x) xs



Or for a "neater" point-free version:

atMostOnce :: Eq a => a -> [a] -> Bool
atMostOnce x = (<= 1) . length . filter (== x)



Like someone said, it's also easy to abstract over the number of times you can repeat it:

atMostN :: Eq a => Int -> a -> [a] -> Bool
atMostN n x = (<= n) . length . filter (== x)


Was This Post Helpful? 0
  • +
  • -

#5 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon


Reputation: 6966
  • View blog
  • Posts: 14,572
  • Joined: 16-October 07

Re: Haskell: Check if a number appears in a list 0 or 1 times

Posted 18 April 2015 - 05:59 PM

Nice. Short, sweet, but not good at scaling. Using length means that everything gets read, even if you already have the answer. While slightly longer, a lazy solution is preferable.

e.g.
atMostN :: Eq a => Int -> a -> [a] -> Bool
atMostN n x = (<= n) . length . filter (== x)
atMostOne x = atMostN 1 x

atMostNLazy :: Eq a => Int -> a -> [a] -> Bool
atMostNLazy n x xs = null $ atMostNLazy' n xs
    where
        atMostNLazy' 1 xs = f xs
        atMostNLazy' n xs = atMostNLazy' (n - 1) $ f xs
        f = drop 1 . dropWhile (/=x)
atMostOneLazy x xs = atMostNLazy 1 x xs

testSize = 10000000
tester fMostOne 1 = fMostOne ( testSize + 1 ) $ [1..testSize]
tester fMostOne 2 = fMostOne testSize $ [1..testSize]
tester fMostOne 3 = not $ fMostOne testSize $ [1..testSize] ++ [1..testSize]
tester fMostOne 4 = not $ fMostOne testSize $ [1..testSize] ++ [1..]
testa = tester atMostOne
testb = tester atMostOneLazy



Test time:
Prelude> :set +s
Prelude> :l oneor
[1 of 1] Compiling Main             ( oneor.hs, interpreted )
Ok, modules loaded: Main.
(0.03 secs, 8960364 bytes)
*Main> testa 1
True
(1.62 secs, 403237112 bytes)
*Main> testb 1
True
(1.51 secs, 400927184 bytes)
*Main> testa 2
True
(1.54 secs, 401182084 bytes)
*Main> testb 2
True
(1.54 secs, 401420708 bytes)
*Main> testa 3
True
(3.18 secs, 1081315544 bytes)
*Main> testb 3
True
(1.71 secs, 680633224 bytes)
*Main> testa 4
^CInterrupted.
*Main> testb 4
True
(1.77 secs, 680561148 bytes)
*Main> 



We expect test 1 and test 2 to be about the same, which they are. Test 3 could also be close, but lazy is significantly faster. Or, rather, dropping as you go is more efficient than storing until the end.

It's test 4 that we're really after; handling those wonderful haskell infinite series. With test 4 we find that length simply causes an infinite execution. Here, we clearly see where lazy is good.

Anyway, the dropWhile solution was what I was pointing toward and it still seems the better bet.
Was This Post Helpful? 0
  • +
  • -

#6 gonzaw  Icon User is offline

  • New D.I.C Head

Reputation: 7
  • View blog
  • Posts: 46
  • Joined: 18-December 12

Re: Haskell: Check if a number appears in a list 0 or 1 times

Posted 19 April 2015 - 06:06 PM

Yes you are right, I didn't stop to think about the way it'd work with laziness.

But I still think that's the best way to work with haskell. First, try to compose simple functions that do what you intuitively want your function to do. After you got it and it works, try to reason a little bit more about it and improve it (so that it works with infinite lists, doesn't waste more memory/time, etc).
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1