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)