Determining whether (x,y) points in the input constitute a function

Question

I'm learning Haskell, and I've finally gotten around to coding up some Haskell. This code passed my tests.

This code takes a line from standard in which tells it how many cases it's going to have (1 to 5), and for each case, it takes a line telling it how many pairs (max of 100) of x's and y's it will get (integers from 0 to 500), and it should print YES if x to y is a function, and NO otherwise.

e.g. with a file called input:

2  
2
1 1
2 1
2
1 1
1 2

The following command should work like this:

$ runhaskell main.hs < input
YES
NO

In my source code the only difference is I have two blank lines for style instead of one between each group of code. My main.hs:

import Control.Monad (replicateM_, replicateM, forM)
import Data.String (words)

main = do
  times <- readLn :: IO Int
  replicateM_ times input_is_a_function

input_is_a_function = do
  n_inputs <- readLn :: IO Int
  inputs <- replicateM n_inputs getLine
  if (null inputs) || (is_function inputs) then
    putStrLn "YES"
  else
    putStrLn "NO"

is_function inputs = is_func ([map read $ words i | i <- inputs] :: [[Int]])

is_func (x_y : rest)
  | rest == [] = True
  | otherwise  = (no_other_y x_y rest) && (is_func rest)

no_other_y [x1, y1] rest
  | rest == [] = True
  | otherwise  = this_y_ok && (no_other_y [x1, y1] (tail rest))
      where
        this_y_ok = not (x_is_target && y_not_equal)
        x_is_target = x1 == head (head rest)
        y_not_equal = y1 /= ((head rest) !! 1)
        -- if target is false, y is ok.
        -- if target is True, y must be equal

The algorithm starts with the first pair of x and y, and does a search for a repetition of x and determines if it matches y or not. Any found x with a mismatch on y should stop the algorithm.

I come from a Python background, so I tend to use snake-case and idioms I am more immediately familiar with (list comprehensions FTW!), but I want to learn idiomatic Haskell.

I also value readability. I could probably have better names. Perhaps more typing would improve readability, but I tried to take as much advantage of Hindley-Milner type inference as I could.

Please address efficiency, typing, style, naming, or any other important issues you identify.

On my workflow: I've been using a basic ghc (7.10.3) from the Ubuntu repos with a test file and that command mentioned above.

Is there a better approach? e.g. a way to watch the file and run tests as I code and save? In Haskell?

Answer 1

Let's condense this down. What you're trying to check is that for any given x, the y values you're told are all the same.

Now let's try to express this as succinctly as possible:

Let's start with a few simplifying assumptions. All your x and y values are going to be integers. Furthermore, let's assume we handle them as Tuples and not as Lists. This enables a somewhat cleaner signature for our types

We start with a list of points and in the end we want a boolean to drop out. Our type signature accordingly looks like this:

isFunction :: [(Int, Int)] -> Bool

This function can be decomposed into a few steps. First we need to group by the x values.

isFunction points = -- we'll fill this in later
   where
   grouped = groupWith fst points -- fst accesses the first item in a tuple

now that we have all points grouped, we need to examine their y values

   ys = map (map snd) grouped -- snd gets the second item in a tuple

And now we want to make sure that every group of y values is always the same value. For this I'll use a bit of a hack

   areEqual = map (\l -> all (== (head l)) (tail l)) ys

What this does is a bit hard to grasp at first glance, but types will help us understand.

Let's fill back the types for all the stuff we had until now:

grouped :: [[(Int, Int)]]  -- List of List of Points
ys :: [[Int]]  -- List of List of Integers

Now let's examine what this does in areUnique. We know that none of the lists in ys are empty. That's very useful for accessing the first element in the list and setting it as baseline for the rest of the list we're examining. All items in a single list (and accordingly belonging to a single x) must be pairwise equal. This explicitly means they must be equal to the first item.

That's how we can use all (== (head l)). That line could also be written as the following:

   areEqual = map (\yGroup -> all (== yGroup!!0) yGroup)

Now we have in areUnique a [Bool], each of them indicating, whether the group is consistent.

That allows us to formulate the final result of isFunction we omitted above:

isFunction points = all id areEqual

So now we have a pretty function that will do the work of your is_func, including all the work of no_other_y. We need to import GHC.Exts for it to work, because it provides groupWith. If you don't have GHC on your system, you will need to write a replacement, but that's probably a good exercise in itself. Only that much: sorting before grouping helps a lot.

A nice sideeffect of this is that we're reducing the time-complexity from \$\mathcal{O}(n^2)\$ to \$\mathcal{O}(n \log n)\$

---

Now aside from this move away from list comprehension into a more explicit model that should additionally be quite a bit faster, there's not that many things to say about your code.

Granted, you largely ignore types (which is something that I personally do exactly the opposite of) and you're using python naming conventions, which only clashes with readLn, getLine and replicateM_.

This is what we got for now:

import GHC.Exts  (groupWith) 

isFunction :: [(Int, Int)] -> Bool
isFunction points = all id areEqual
   where
   grouped = groupWith fst points
   ys = map (map snd) grouped
   areEqual = map (\l -> all (== l!!0) l) ys

Now let's get a bit fancier. We can inline a few of these definitions:

areEqual = map (\l -> all (== l!!0) l) (map (map snd) grouped)

notice the repeated use of map. We can get around that by using function composition (.):

areEqual = map ((\l -> all (== l!!0) l) . (map snd)) grouped

interestingly it's not necessary to map to the y value alone. While semantically appropriate, the x values already should be the same. This allows us to drop the mapping:

areEqual = map (\l -> all (== l!!0) l) grouped

Now we can inline grouped to obtain (which uses $, the self closing parenthesis):

areEqual = map (\l -> all (== l!!0) l) $ groupWith (fst) points

And to top it off, this can be inlined into our all, which gets us to:

isFunction points = all id $ (map (\l -> all (== l!!0) l)) $ groupWith fst points

At this point we replace our fancy self-closing braces with function composition to obtain

isFunction points = (all id) . (map (\l -> all (== l!!0) l)) . (groupWith fst) points 

which can then be reduced to:

isFunction = (all id) . (map (\l -> all (== l!!0) l)) . (groupWith fst)

That in turn can be simplified to (hat tip to @Gurkenglas):

isFunction = all (\l -> all (== l!!0) l) . groupWith fst