Haskell 元组列表与元组比较

Question

我正在尝试用 Haskell 进行我的第一次（在我看来）不平凡的尝试。我可能会问每个部分的问题，以将我与类似 C 语言的长期关系的尝试与经验丰富的函数式程序员可能会做的事情进行比较。幸运的是，Haskell 使得很难依靠直接的 C 到 Haskell 代码转换。你必须学会如何正确地做事——我也想这么做。

对于这部分，我有一个 [2uple] 和一个 2uple。我想知道 2uple 中的任何项目是否属于 [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

我更愿意返回一个普通的 Bool 但没什么大不了的。

我确信还有另一种方法，我需要花一段时间才能理解。那很好。寻找接受者。

谢谢

Answer 1

让我们从您的代码开始。

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

既然你说你更喜欢布尔结果，我们可以改用它。事实上，布尔值会更好，因为在上面的代码中我们永远不会返回

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

现在，

if x then True else y

就是

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

如果您想知道，当我们找到匹配项时，

||

不会评估

acc

。这与 C 短路具有相同的惰性语义。与 C 相比，主要区别在于布尔变量

acc

可以表示 未评估的 布尔结果，而在 C 中它始终是完全评估的布尔值。

现在，

tmatch

使用相同的第二个参数

tupm

，所以我们可以内联它，并尽早进行模式匹配：

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

我们甚至可以将

let

移到外面以提高可读性。

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

我们还可以在这里使用

where

：

hasmatch tlst (c,d) = foldr (\tup acc -> tmatch tup || acc) False tlst
   where tmatch (a,b) = a==c || b==c || a==d || b==d

最后，我们可以利用一个库函数：

any

。当且仅当

any p list

中存在满足属性

True

的元素时，调用

list

的计算结果为

p

。我们的代码变成：

hasmatch tlst (c,d) = any tmatch tlst
   where tmatch (a,b) = a==c || b==c || a==d || b==d

就是这样。

请注意，上述方法还有其他选择。人们可以将元组列表

[(a,b), (c,d), ...

转换为所有组件

[a,b,c,d,...

的列表，并使用它。

hasmatch tlst (c,d) = any tmatch [ x | (a,b) <- tlst, x <- [a,b]]
   where tmatch x = x==c || x==d

Answer 2

根据 chi 的答案，您可能最好定义具有这种等式的数据类型？

{-# 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 $ liftA2 (==) [a1, b1] [a2, b2]

那么您寻找的函数就是标准库函数，例如

elem

或

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