Haskell list of tuples vs tuple comparrison
I'm playing with my first non-trivial (in my eyes) attempt at something in Haskell. I'm probably going to ask questions about each part to compare my coming-from-long-term-relationship-with-c-like-languages attempt to what you-as-seasoned-functional-programmer might do. Luckily Haskell makes it hard to fall back on straight c-to-haskell code conversion. You have to learn how to do it right - and I want to.
For this part, I have a [2uple] and a 2uple. I want to know if any item in the 2uple is in any of the items in the [2uple].
hasmatch tlst tupm = foldr (\tup acc ->
let tmatch (a,b) (c,d) = a==c || b==c || a==d || b==d in
if tmatch tup tupm
then (Just True) -- short out
else acc -- do nothing, keep looping
) Nothing tlst
-- hasmatch [(1,2), (3,4), (5,6)] (5,3) ==> Just True
-- hasmatch [(1,2), (9,4), (7,6)] (5,3) ==> Nothing
I'd prefer to return a plain Bool but no biggie there.
I'm sure there is another way that I would have to grok at for a while to understand. That is good. Looking for takers.
Thanks
Let's start from your code.
hasmatch tlst tupm =
foldr (\tup acc ->
let tmatch (a,b) (c,d) = a==c || b==c || a==d || b==d in
if tmatch tup tupm
then (Just True) -- short out
else acc -- do nothing, keep looping
) Nothing tlst
Since you say you prefer a boolean result, we can switch to that. Indeed, a boolean would be better since in the above code we never return Just False
.
hasmatch tlst tupm =
foldr (\tup acc ->
let tmatch (a,b) (c,d) = a==c || b==c || a==d || b==d in
if tmatch tup tupm
then True -- short out
else acc -- do nothing, keep looping
) False tlst
Now, if x then True else y
is simply x || y
.
hasmatch tlst tupm =
foldr (\tup acc ->
let tmatch (a,b) (c,d) = a==c || b==c || a==d || b==d in
tmatch tup tupm || acc
) False tlst
If you wonder, ||
will not evaluate acc
when we find a match. This is the same lazy semantics as C short-circuiting. Compared to C, the main difference is that a boolean variable acc
can represent the unevaluated boolean result, while in C it's always a fully evaluated boolean value.
Now, tmatch
uses the same second argument, tupm
, so we can inline that, and pattern-match early:
hasmatch tlst (c,d) =
foldr (\tup acc ->
let tmatch (a,b) = a==c || b==c || a==d || b==d in
tmatch tup || acc
) False tlst
We can even move the let
outside to improve readability.
hasmatch tlst (c,d) =
let tmatch (a,b) = a==c || b==c || a==d || b==d
in foldr (\tup acc -> tmatch tup || acc) False tlst
We can also use a where
here:
hasmatch tlst (c,d) = foldr (\tup acc -> tmatch tup || acc) False tlst
where tmatch (a,b) = a==c || b==c || a==d || b==d
Finally, we can exploit a library function: any
. Calling any p list
evaluates to True
iff there is any element in list
that satisfies property p
. Our code becomes:
hasmatch tlst (c,d) = any tmatch tlst
where tmatch (a,b) = a==c || b==c || a==d || b==d
That's it.
Note that there are alternatives to the above approach. One could be turning the list of tuples [(a,b), (c,d), ...
into a list of all the components [a,b,c,d,...
, and working with that.
hasmatch tlst (c,d) = any tmatch [ x | (a,b) <- tlst, x <- [a,b]]
where tmatch x = x==c || x==d
Based on chi's answer you may be better off defining a datatype with this equality?
{-# Language DerivingStrategies #-}
{-# Language InstanceSigs #-}
{-# Language StandaloneKindSignatures #-}
import Data.Kind (Type)
type AnyTuple :: Type -> Type
data AnyTuple a = a :×: a
deriving stock Show
instance Eq a => Eq (AnyTuple a) where
(==) :: AnyTuple a -> AnyTuple a -> Bool
a1:×:b1 == a2:×:b2 = or [ x == y | x <- [a1, b1], y <- [a2, b2] ]
Then the function you seek is a standard library function like elem
or find
>> 5:×:3 `elem` [1:×:2, 3:×:4, 5:×:6]
True
>> 5:×:3 `elem` [1:×:2, 9:×:4, 7:×:6]
False
>> find (== 5:×:3) [1:×:2, 3:×:4, 5:×:6]
Just (3 :×: 4)
>> find (== 5:×:3) [1:×:2, 9:×:4, 7:×:6]
Nothing