Determine whether input-output pairs represent something that could be a proper math function

Question

The input is read in line by line from stdin.

Input Format

The first line contains an integer, T, denoting the number of test cases. The subsequent lines describe T test cases, and the input for each test case is as follows:

The first line contains an integer, N, the number of (x,y) pairs in the test case. The N subsequent lines each contain two space-separated integers describing the respective x and y values for each ordered pair.

Constraints

• \1ドル \le T \le 5\$
• \2ドル \le N \le 100\$
• \0ドル \le x, y \le 500\$

x and y are both integers.

Output Format

On a new line for each test case, print YES if the set of ordered pairs represent a valid function, or NO if they do not.

Sample Input

2 
3 
1 1 
2 2 
3 3 
4 
1 2 
2 4 
3 6 
4 8 

Sample Output

YES 
YES

Full problem statement

I'm looking for feedback regarding ways this could be: more concise/clean, more idiomatic Haskell, or if there are algorithmic/mathematical tricks I missed that could further simplify the computation.

import System.IO (readLn, getLine)
import Control.Monad (replicateM, mapM_, liftM)
import Data.List (nub)
import qualified Data.Map.Strict as M
data YesNo = YES | NO deriving Show
boolToYesNo :: Bool -> YesNo
boolToYesNo x = if x then YES else NO
readInt :: IO Int
readInt = readLn
tuplefy :: [a] -> (a, a)
tuplefy xs = case xs of [a, b] -> (a, b)
 _ -> error "each item must consist of 2 values."
readPair :: [String] -> [(Int, Int)]
readPair = map $ tuplefy . map (read :: String -> Int) . words
getPairs :: Int -> IO [String]
getPairs = flip replicateM getLine
readTestCase :: Int -> IO [(Int, Int)]
readTestCase = fmap readPair . getPairs
readTestCases :: Int -> IO [[(Int, Int)]]
readTestCases = flip replicateM $ readInt >>= readTestCase
printAnswers :: Show a => [a] -> IO ()
printAnswers = mapM_ print
isSingletonSet :: Eq b => [b] -> Bool
isSingletonSet xs = case nub xs of [x] -> True
 _ -> False
listToMultiMap :: (Ord k, Eq k, Eq v) => [(k, v)] -> M.Map k [v]
listToMultiMap ((k, v):vs) = toMap (M.fromList [(k, [v])]) vs
 where toMap m xs = case xs of [] -> m
 (k0, v0):ys ->
 case M.lookup k0 m of Nothing -> toMap (M.insert k0 [v0] m) ys
 Just v0s -> toMap (M.insert k0 (v0:v0s) m) ys
functionOrNot :: [(Int, Int)] -> YesNo
functionOrNot tuples = boolToYesNo $ foldl1 (&&) $ M.elems $ M.map isSingletonSet $ listToMultiMap tuples
main :: IO ()
main = getAnswers >>= printAnswers
 where getAnswers = (liftM . map) functionOrNot $ readInt >>= readTestCases

Answer 1

Your monadic helper functions are all one-offs and even if they were well-named (no worries, naming just gets harder as you get more experienced, there's a reason Adam was told to do it), I'd still think it better to inline them. Then the main ends up cluttered with pointfreed binds and I turned that into a do block.

(I did reorder the monadic effects a little, moving the output of each answer in front of the reading of the next question, but I found that sacrifice worthy.)

I'm not sure you need to try your hand at error-handling in tuplefy - a badly formated input file should be as likely to have a typo in its number of words in a line as in its stated number of pairs in a function.

listToMultiMap - (k, v) is no different from the other elements of vs, so you could go listToMultiMap = toMap M.empty. toMap is folding left, bad style. You can fold right like:

toMap [] = []
toMap ((k0, v0):ys) = case M.lookup k0 m of
 Nothing -> M.insert k0 [v0] $ toMap ys
 Just v0s -> M.insert k0 (v0:v0s) $ toMap ys

and won't need to carry a parameter into the recursive calls. And of course this can be written in terms of foldr:

listToMultiMap = foldr foo M.empty where
 foo (k0, v0) m = case M.lookup k0 m of
 Nothing -> M.insert k0 [v0] m
 Just v0s -> M.insert k0 (v0:v0s) m

And we could reduce the duplication in the last two lines there, but then again this whole thing is already handled by Data.Maps fromListWith.

import System.IO (readLn, getLine)
import Control.Monad (replicateM)
import qualified Data.Map.Strict as M
import Data.Bool (bool)
noDuplicates :: Ord a => [a] -> Bool
noDuplicates = all (==1) . M.fromListWith (+) . map (,1)
-- = all ((==1) . length) . M.fromListWith (++) . map (,["Why are you looking at the ordinate?"])
-- = and . M.fromListWith (\_ _ -> False) . map (,True)
main :: IO ()
main = do
 functioncount <- readLn
 replicateM functioncount $ do
 paircount <- readLn
 abscissae <- replicateM paircount $ read . head . words <$> getLine
 putStrLn $ bool "NO" "YES" $ noDuplicates abscissae

It is unfortunate for pointfreedom that the first parameter of replicateM indeed should be Int. There must be a better way than flip. Perhaps a new infix operator, semantically id, that has highest precedence to the left, and lowest to the right, to simulate enclosing brackets around its entire right side and disappearing?

• Josiah: Wow, much simpler. I would still make a small modification and use the nub function before passing the list to map (,1) to handle the case where the test cases might test the same input twice but get back the same result. For instance, the set [(1, 2), (2, 3), (1, 2), (3, 1)] is still a valid function because both times I got back the same value when the input '1' was tested.
• Gurkenglas: If getting the same point twice is actually a thing that can happen (from the task description I would have assumed not), okay, but nub is quadratic time, and if you don't care about that, then noDuplicates can be replaced with on (==) length =<< nub without involving Data.Map at all. If you do care, something like the first commentline variant of noDuplicates can be used to collect the actual ordinates, and then you check those per abscissa with e.g. (== (1:Natural)) . genericLength.

Answer 2

In several places you can substitute case ... of with pattern matching to make the code a little more clear. One such place is the tuplefy function:

tuplefy :: [a] -> (a, a)
tuplefy [a, b] = (a, b)
tuplefy _ = error "each item must consist of 2 values."