2
\$\begingroup\$

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 𝚈𝙴𝚂 if the set of ordered pairs represent a valid function, or 𝙽𝙾 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
\$\endgroup\$
4
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Josiah Apr 4 '16 at 15:41
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Gurkenglas Apr 5 '16 at 3:07
0
\$\begingroup\$

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."
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.