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

[(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(n2). 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 (x1,y1),(x2,y2) 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
    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
    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
  • 1
    \$\begingroup\$ Remark: Ord b => Eq a => ... is usually written as (Ord b, Eq a) => .... \$\endgroup\$ – Zeta Jun 30 '18 at 9:46

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

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.