So I'm trying to define a function in Haskell that if given an integer and a list of integers will give a 'true' or 'false' whether the integer occurs only once or not.
So far I've got:
let once :: Eq a => a -> [a] -> Bool; once x l =
But I haven't finished writing the code yet. I'm very new to Haskell as you may be able to tell.
Here's a solution that doesn't use pattern matching explicitly. Instead, it keeps track of a Bool which represents if a occurance has already been found.
As others have pointed out, this is probably a homework problem, so I've intentionally left the then and else branches blank. I encourage user3482534 to experiment with this code and fill them in themselves.
once :: Eq a => a -> [a] -> Bool
once a = foldr f False
where f x b = if x == a then ??? else ???
Edit: The naive implementation I was originally thinking of was:
once :: Eq a => a -> [a] -> Bool
once a = foldr f False
where f x b = if x == a then b /= True else b
but this is incorrect as,
λ. once 'x' "xxx"
True
which should, of course, be False as 'x' occurs more than exactly once.
However, to show that it is possible to write once using a fold, here's a revised version that uses a custom monoid to keep track of how many times the element has occured:
import Data.List
import Data.Foldable
import Data.Monoid
data Occur = Zero | Once | Many
deriving Eq
instance Monoid Occur where
mempty = Zero
Zero `mappend` x = x
x `mappend` Zero = x
_ `mappend` _ = Many
once :: Eq a => a -> [a] -> Bool
once a = (==) Once . foldMap f
where f x = if x == a then Once else Zero
main = do
let xss = inits "xxxxx"
print $ map (once 'x') xss
which prints
[False,True,False,False,False]
as expected.
The structure of once is similar, but not identical, to the original.
I'll answer this as if it were a homework question since it looks like one.
Read about pattern matching in function declarations, especially when they give an example of processing a list. You'll use tools from Data.List later, but probably your professor is teaching about pattern matching.
Think about a function that maps values to a 1 or 0 depending on whethere there is a match ...
match :: a -> [a] -> [Int]
match x xs = map -- fill in the thing here such that
-- match 3 [1,2,3,4,5] == [0,0,1,0,0]
Note that there is the sum function that takes a list of numbers and returns the sum of the numbers in the list. So to count the matches a function can take the match function and return the counts.
countN :: a -> [a] -> Int
countN x xs = ? $ match x xs
And finally a function that exploits the countN function to check for a count of only 1. (==1).
Hope you can figure out the rest ...
For counting generally, with import Data.List (foldl'), pointfree
count pred = foldl' (\ n x -> if pred x then n + 1 else n) 0
applicable like
count (< 10) [1 .. 10] == 9
count (== 'l') "Hello" == 2
gives
once pred xs = count pred xs == 1
Efficient O(n) short-circuit predicated form, testing whether the predicate is satisfied exactly once:
once :: (a -> Bool) -> [a] -> Bool
once pred list = one list 0
where
one [] 1 = True
one [] _ = False
one _ 2 = False
one (x : xs) n | pred x = one xs (n + 1)
| otherwise = one xs n
Or, using any:
none pred = not . any pred
once :: (a -> Bool) -> [a] -> Bool
once _ [] = False
once pred (x : xs) | pred x = none pred xs
| otherwise = one pred xs
gives
elemOnce y = once (== y)
which
elemOnce 47 [1,1,2] == False
elemOnce 2 [1,1,2] == True
elemOnce 81 [81,81,2] == False
