Skip to main content
added 127 characters in body
Source Link
Vogel612
  • 25.3k
  • 7
  • 58
  • 141

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

isFunction = all (\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
Source Link
Vogel612
  • 25.3k
  • 7
  • 58
  • 141

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)