logo标签列表

Haskell如何检查两个元组列表是否相等并取并集

listtuples
5
我是一个新的Haskell自学者。首先，我想编写一个函数来检查两个元组列表是否相等。每个元组都有一个键和值。
其次，我想要一个函数来合并两个元组列表。
我尝试了几种方法，多次尝试，但好像无法满足我的需求。有人能帮忙吗？提前致谢。
参见：如何使用Haskell将列表中的相似项分组？ - Daniel Wagner
为了进一步解答Wilem的问题：也许给我们一个不展示你想要的行为的例子会更容易——在这种情况下，有两个成对列表，你当前的解决方案返回true时应该返回false（或反之亦然）。从那里开始，我们可以努力修复你的代码。 - lambda.xy.x
@lambda.xy.x 用于测试相等性，[('a',2),('b',1)] 和 [('b',1),('a',2)] 显示为 False，但实际应该为 True。 - cynn
我只是想在我的机器上加载你发布的代码。它有多个错误信息 - 首先是lisLength未定义。将你发布的内容加载到一个新的ghci实例中是否有效？（第一步是让你的代码编译通过，然后我们可以看看行为） - lambda.xy.x
顺便提一句，我刚刚意识到，您可能只想修改“itemInLis”为“itemCount :: Eq a => a -> Lis a -> Times”，返回元组的第二个参数而不仅仅是真/假。如果您正在处理元组“(x,n)”，则只需要检查“n == itemCount x lis2”（以及错误条件）。 - lambda.xy.x
显示剩余8条评论
4个回答
5

由于a只是Eq的成员，所以无法进行排序或分组。

import Data.List(nub, (\\))
import Data.Monoid(getSum)

type Times = Int
type Lis a = [(a,Times)]

lisEqual :: Eq a => Lis a -> Lis a -> Bool
lisEqual xs xs' = length xs == length xs' && xs \\ xs' == []

lisSum :: Eq a => Lis a-> Lis a-> Lis a
lisSum xs xs' = fmap f $ getKeys l 
  where
    f x = (,) x (getSum . foldMap (pure . snd) . filter ((x ==) . fst) $ l)                         
    l = xs ++ xs'
    getKeys = nub . fst . unzip
2
我的建议：从提取两个列表中的组合键的函数开始：
allKeys :: Eq a => Lis a -> Lis a -> [a]

所以allKeys [('a',2),('b',2),('c',3)] [('b',2),('a',1),('d',3)]是['a','b','c','d']。 提示：从两个列表中提取所有键，将它们合并为一个列表，然后从该列表中删除重复项（有标准函数可执行所有这些任务）。
该函数对于检查相等性和计算总和都很有用：
- 要检查相等性，只需检查在第一个列表中查找每个键是否给出与在第二个列表中查找它相同的结果。 - 要计算总和，只需将每个键与原始列表中的查找总和配对。
需要考虑一件事：列表[('a',0)]是否与[]相同？否则，您应该使用返回Maybe Int的查找函数，在第一种情况下为键'a'提供Just 0，在第二种情况下提供Nothing。
如果这不是作业，请告诉我，我可以给您代码。
编辑：代码！
以下代码与我通常编写的代码相比稍微简化了一些，但差别不大。您可能不熟悉几个库函数，包括从Data.List导入的nub（用于删除重复项）。
import Data.List(nub)

type Times = Int
type Lis a = [(a,Times)] 

count :: Eq a => Lis a -> a -> Times
count xs x = case lookup x xs of
  Nothing -> 0 -- x is not in the list
  Just n  -> n -- x is in the list associated with n

-- Extract all keys by taking the first value in each pair
keys :: Lis a -> [a]
keys xs = map fst xs 

-- Extract the union of all keys of two lists
allKeys :: Eq a => Lis a -> Lis a -> [a]
allKeys xs ys = nub (keys xs ++ keys ys)

lisEquals :: Eq a=> Lis a -> Lis a -> Bool
lisEquals xs ys = all test (allKeys xs ys) 
  where
    -- Check that a key maps to the same value in both lists
    test k = count xs k == count ys k

lisSum :: Eq a => Lis a -> Lis a -> Lis a
lisSum xs ys = map countBoth (allKeys xs ys)
  where
    -- Build a new list element from a key
    countBoth k = (k,count xs k + count ys k)
这不是作业。我是一个自学者，只是尝试编写一些函数。你能给我代码，这样我就可以和我的代码进行比较，非常感谢。 - cynn
@cynn 代码已添加。一个初学者编写这段代码时会使用更多的模式匹配和显式递归（这对于学习来说是好的，但从长远来看，你应该学会使用库函数）。另外，由于您是新贡献者，请记得标注有用的答案。 - Jonas Duregård
我得到了lisSum [('a',1), ('a',2)] [('a',3)] == [('a',4)]，但应该是[('a',6)]（请参见问题的注释）。 - lambda.xy.x
@lambda.xy.x 答案中已经提到了与 0 相关的情况，解决方案忽略了它，这在计数语义上是明智的。 - Jonas Duregård
是的，我忽略了关于中立性的评论。 - lambda.xy.x
显示剩余3条评论
2
这是我在评论中提出的版本。首先检查列表是否存在重复键和等长，以确保我们只需要检查l1的所有键是否为l2的键。然后进行查找并检查计数是否相等：
lisEqual l1 l2 =
  (nodups $ map fst l1) &&
  (nodups $ map fst l2) &&
  length l1 == length l2 &&
  and (map (\ (x,k) -> case (occOfA x l2) of
                    Just n -> n == k
                    Nothing -> False
                  ) l1)

查询返回Maybe b，表示没有找到对应的结果，返回Nothing。
occOfA :: Eq a => a -> [(a,b)] -> Maybe b
occOfA a []   = Nothing
occOfA a ((x,n):xs) =
  if a == x then Just n
            else occOfA a xs

重复检查只是一个递归。
nodups :: Eq a => [a] -> Bool
nodups [] = True
nodups (x:xs) = not (x `elem` xs) && (nodups xs)

一些测试用例

t :: Int -> Bool
t 0 = lisEqual [(2,3), (1,2)] [(1,2), (2,3)] == True
t 1 = lisEqual [(2,3), (1,2)] [(1,3), (2,3)] == False
t 2 = lisEqual [(2,3), (1,2), (1,3)] [(1,3), (2,3)] == False
t 3 = lisEqual [(2,3)] [(1,3), (2,3)] == False

可以作为检查

*Main> and $ map t [0..3]
True

我有点懒得计算总和，所以我定义了一个名为lisSum1的函数，该函数收集列表中的所有键并相应地对值求和。对于lisSum，我只需要连接这两个列表：

lisSum l1 l2 = lisSum1 $ l1 ++ l2

lisSum1 :: Eq a => [(a,Int)] -> [(a,Int)]
lisSum1 list =
   reverse $ foldl (\acc k ->  (k, sumList $ map snd (select k list) ) : acc ) -- create pairs (k, ksum) where ksum is the sum of all values with key k
   [] (rdups $ map fst list)

使用一些辅助函数：

rdups :: Eq a => [a] -> [a]
rdups [] = []
rdups (x:xs) = x : rdups (filter (/= x) xs)

sum l = foldl (+) 0 l

select k list = filter (\ (x,_) -> k == x) list

再次进行一些测试：

s :: Int -> Bool
s 0 = lisSum [('a',1), ('a',2)] [('a',3)] == [('a',6)]
s 1 = lisSum [(1,2), (2,3)] [(2,4),(3,1)] == [(1,2),(2,7),(3,1)]
s 2 = lisSum [(1,2), (2,3), (2,4), (3,1)] [] == [(1,2),(2,7),(3,1)]
s 3 = lisSum [(1,2), (2,3), (3,1)] [] == [(1,2),(2,3),(3,1)]


*Main> map s [0..3]
[True,True,True,True]
< p > 编辑：函数lisEqual不是自反的，因为我们最初定义了一个版本，该版本在输入中不需要重复项。这样做的问题是lisEqual不是等价关系：

*Main> lisEqual [(1,1),(1,2)] [(1,1),(1,2)]
False

如果我们解决了自反性问题，我们可以删除原始重复限制并定义如下：

如果我们解决了自反性的问题，我们可以删除对重复项的原始限制并定义：

lisEqualD [] []    = True
lisEqualD (_:_) [] = False
lisEqualD [] (_:_) = False
lisEqualD (x:xs) ys =
    case (remFirst x ys) of
        Nothing -> False
        Just zs -> lisEqualD xs zs

remFirst x [] = Nothing
remFirst x (y:ys) =
  if x == y then Just ys
            else case (remFirst x ys) of
                    Just zs -> Just (y:zs)
                    Nothing -> Nothing

让我们扩展测试用例：

t :: Int -> Bool
t 0 = lisEqualD [(2,3), (1,2)] [(1,2), (2,3)] == True
t 1 = lisEqualD [(2,3), (1,2)] [(1,3), (2,3)] == False
t 2 = lisEqualD [(2,3), (1,2), (1,3)] [(1,3), (2,3)] == False
t 3 = lisEqualD [(2,3)] [(1,3), (2,3)] == False
t 4 = lisEqualD [(2,3), (1,2), (2,3)] [(1,2), (2,3),(2,3)] == True
t 5 = lisEqualD [(1,1),(1,2)] [(1,1),(1,2)] == True


*Main> map t [0..5]
[True,True,True,True,True,True]
为什么带有重复元素的列表lisEqual函数应该返回false？这意味着它不是自反的，因为对于某些（无效）列表，lisEqual x x将会是false。也许它应该抛出一个错误（或者忽略重复元素，因为查找函数就是这样做的）。 - Jonas Duregård
要求已添加在评论中。你关于反射性的想法是正确的，这会很丑陋 - 我在考虑如果我可以在没有错误的情况下挽救该属性，但如果 lisEq [(1,2),(1,3)] [(1,3),(1,2)] 返回 false，而 lisEq [(1,2),(1,3)] [(1,2),(1,3)] 抛出一个错误，这也不是一个好的行为。 - lambda.xy.x
我添加了一个更好的版本，考虑到了重复项。 - lambda.xy.x
我期望 lisSum [] == id (加入一个空的 map 不会做任何事情)。 - Jonas Duregård
该属性通常不成立，例如 lisSum [] [(1,2),(1,3)]。我添加了一个 reverse 来恢复每个列表中键都不同的情况。 - lambda.xy.x
1
我的解决方案非常简单。为了比较这样的列表，你需要先对它们进行排序。通过关键字将两个列表相加可以递归地完成，只要关键字是 Ord 类型，并且你按照关键字对两个列表进行排序。为了保持原始性，我没有使用你的别名，但你可以很容易地适应它。
eqList xs vs = xs' == vs' 
                 where xs' = sortOn fst xs
                       vs' = sortOn fst vs

sumKeyValue' :: [(Char, Integer)] -> [(Char, Integer)] -> [(Char, Integer)]
sumKeyValue' [] v  = v
sumKeyValue' x  [] = x
sumKeyValue' x@((a, c):xs) v@((b,d):vs) 
  | a == b = (a, c + d):sumKeyValue xs vs
  | a < b  = (a,c):sumKeyValue xs v
  | a > b  = (b,d):sumKeyValue x vs

sumKeyValue xs vs = sumKeyValue' xs' vs' 
  where xs' = sortOn fst xs
        vs' = sortOn fst vs
你的代码与问题中所需的函数具有不兼容的类型。而且你无法轻松地进行适应，因为没有 Ord 约束条件，你无法进行排序。 - Jonas Duregård
没那么糟糕，你可以从列表中删除重复项，将其与 [1.. length dups] 压缩起来，并使用此映射作为排序，但这会使解决方案不太优雅。 - lambda.xy.x
@lambda.xy.x 这种排序有什么帮助吗？ - Jonas Duregård
您可以对元素使用任意顺序进行排序。只需随意为元素分配数字，并将其用于排序即可。 - lambda.xy.x
我认为Ord条件并不是@lamda.x.y.x所指出的问题。此外，根据问题（和修改），实际类型似乎是[(Char, Int)]而不是任意a的[(a, Int)]，但也许我过于假设了。 - lsmor
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接