Determining if a set of 2d vectors is a valid function

Question

My idea was to take in the function and perform a self cross product so that I could check every pair against every other pair. I'm new to Haskell so this solution is probably rough.

My question is, is there a better way to emulate a nested for loop rather than a cross product? Also, is there any way to collapse my ugly valid and valid' into one clean function?

valid :: [(Int, Int)] -> Bool
valid f = valid' $ [(x,y) | x <- f, y <- f]

valid' :: [((Int,Int),(Int,Int))] -> Bool
valid' [] = True
valid' (((x,y),(x1,y1)):xs) = valid' xs && if x == x1 then (if y == y1 then True else False) else True

Answer 1

[(x,y) | x <- f, y <- f] is certainly inefficient: it constructs a list of all possible pairs of points. To test a set of n points, your function would be O(n²). I would also note that the choice of (x,y) as a name is misleading, as it suggests that the result of this comprehension will be a list of x-y coordinates, rather than a list of (x₁,y₁),(x₂,y₂) pairs.

A better solution would be to sort and group by abscissa, then for each group, ensure that all the ordinates are the same.

import Data.List (sortOn, groupBy)

isFunction :: Ord x => Eq y => [(x, y)] -> Bool
isFunction = all sameSnd . groupBy sameFst . sortOn fst
  where
    sameFst a b = (fst a) == (fst b)
    sameSnd = (\(y:ys) -> all (== y) ys) . map snd

Note that I have broadened the type signature: the abscissas can be any sortable type, and the ordinates only need to be testable for equality.

---

However, I would guess that once you have ascertained that the set of points constitute a function, you would eventually want to perform some lookups. For that, constructing a Data.Map would be beneficial.

Here, I've divided the work into two functions.

• makeFunction takes a list of points, and tries to produce a Just IntMap. If it fails because some x-coordinate maps to two y-coordinates, then the result is Nothing.
• isFunction simply tests whether makeFunction succeeded.

import Data.IntMap (IntMap, empty, insertWithKey, map, traverseWithKey)
import Data.Maybe (isJust)

makeFunction :: Eq y => [(Int, y)] -> Maybe (IntMap (y))
makeFunction = ensureFunction . buildMap . justifyOrdinates
  where
    justifyOrdinates = Prelude.map (\(x, y) -> (x, Just y))
    ensureSame k newV oldV = if (newV == oldV) then oldV else Nothing
    buildMap = foldr (\(k, v) -> insertWithKey ensureSame k v) empty 
    ensureFunction = traverseWithKey (\k v -> if isJust v then v else Nothing)

isFunction :: Eq y => [(Int, y)] -> Bool 
isFunction = isJust . makeFunction

Answer 2

To start, if y == y1 then True else False can be simplified to y == y1:

valid' (((x,y),(x1,y1)):xs) = valid' xs && if x == x1 then y == y1 else True