[(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
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