在Haskell中从列表中删除共轭元组

Question

在Haskell中从列表中删除共轭元组

3

我有一个元组列表，每个元组也是一个元组。对于每个外部元组，我都有一个共轭元组。我的意思是，如果列表中有(a,b)，那么也会有(b,a)。我的目标是从列表中删除共轭元组。

以下是我的列表的具体示例：

[((1,2,1,0),(5,2,1,0)),((2,4,4,0),(2,5,4,0)),((2,5,4,0),(2,4,4,0)),((3,1,1,0),(3,3,2,0)),((3,3,2,0),(3,1,1,0)),((5,1,7,0),(8,1,7,0)),((5,2,1,0),(1,2,1,0)),((5,5,8,0),(8,5,8,0)),((5,6,6,0),(8,6,8,0)),((5,9,9,0),(8,9,9,0)),((6,3,5,0),(6,8,9,0)),((6,8,9,0),(6,3,5,0)),((7,7,6,0),(9,7,6,0)),((8,1,7,0),(5,1,7,0)),((8,5,8,0),(5,5,8,0)),((8,6,8,0),(5,6,6,0)),((8,9,9,0),(5,9,9,0)),((9,7,6,0),(7,7,6,0))]

从列表中删除共轭元组后的结果应该是：

[((1,2,1,0),(5,2,1,0)),((2,4,4,0),(2,5,4,0)),((3,1,1,0),(3,3,2,0)),((5,1,7,0),(8,1,7,0)),((5,5,8,0),(8,5,8,0)),((5,6,6,0),(8,6,8,0)),((5,9,9,0),(8,9,9,0)),((6,3,5,0),(6,8,9,0)),((7,7,6,0),(9,7,6,0))]

我已经尝试了几个小时，但没有成功。任何帮助将不胜感激。

- Hassan Shahin

每个元组本身也是一个元组。你的意思是每个元组也由元组组成。 - Julia Path

这是一道作业练习吗？你想要提示还是想要解决方案？ - Julia Path

是的。也许我发布的示例比我的措辞更好 :) - Hassan Shahin

2

@jpath：不，这不是家庭作业 :) 我将近60岁了。我正在尝试解决拼图数独，并且需要去除重复项。 - Hassan Shahin

@jpath：如果我的列表看起来很神秘，那么它们代表数独拼图中的单元格。每个单元格都是(Int,Int,Int,Int)类型，表示单元格的行、列、区域和值。我编写了一个函数，可以给定一个网格，找到具有相同潜在值的单元格。这个例子就是这样一组单元格的列表。 - Hassan Shahin

2个回答

2

"元组的每个元素也是一个元组。"

removeConj xs = foldl f [] xs
  where f b a = if (elem (snd a, fst a) b) then b else (a:b)

- ja.

好的，谢谢。但我已经尝试过了，它给了我相同的列表，即它没有去除掉动词的变位形式。 - Hassan Shahin

是的，它起作用了。谢谢。有趣的是，结果列表的顺序与jpath解决方案生成的列表相反。我认为可以通过应用reverse函数来保留顺序。 - Hassan Shahin

顺便提一下，在Haskell中有没有办法测量两个函数执行任务所需的时间。例如，我如何比较ja解决方案和jpath解决方案哪个更快或更慢？ - Hassan Shahin

我知道使用ghci对函数进行基准测试不够准确。不过，我使用了:set +s来比较我得到的解决方案。结果如下：(0.06秒，272,840字节) -- 对于removeConj (0.07秒，277,416字节) -- 对于nubTuples附言：我在样本上使用了这个方法，它并不能提供真正的指标。 - Hassan Shahin

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Julia Path · Accepted Answer

首先，我们可以将类型概括为以下内容：

nubTuples :: Eq a => [(a,a)] -> [(a,a)]

然而，为了使事情更加高效和方便，让我们也为a请求一个Ord实例。这样做为什么会更容易呢？因为现在我们可以将元组转换为有序的标准形式。然后我们可以简单地使用 nub . sort。下面的实现实际上是基于该表示对其进行排序和去重处理，因此 nubTuples [(2,1)] = [(2,1)] 而不是 [(1,2)]。

import Data.List (sortOn, nubBy)
import Data.Tuple (swap)

nubTuples :: Ord a => [(a,a)] -> [(a,a)]
nubTuples = nubBy unorderedCompare . sortOn orderTuple
  where orderTuple (x,y)
          | x < y = (x,y)
          | otherwise = (y,x)
        unorderedCompare x y = x == y || swap x == y

请注意，这会更改顺序并删除重复项：

nubTuples [(3,4),(1,2),(1,2)] = [(1,2),(3,4)]

如果要改变顺序，我们可以使用 Data.Discrimination 中的 nubWith 函数来修复。这个函数在 discrimination 包中。然后我们的代码将变为以下内容：

 import Data.Discrimination (nubWith, Grouping)

 nubTuples :: (Ord a, Grouping a) => [(a,a)] -> [(a,a)]
 nubTuples = nubWith orderTuple
   where orderTuple (x,y)
           | x < y = (x,y)
           | otherwise = (y,x)

这不需要排序，保持原有顺序并且最大限度地偷懒（对于性能通常非常重要）。然而，它仍然会删除重复项。

您可以像这样为任何类型简单地导出一个 Grouping 实例:

{-# LANGUAGE DeriveGeneric #-}
import Data.Discrimination
import GHC.Generics

data A = A deriving Generic
instance Grouping A

请注意，4元组中不存在Grouping的实例。以下是解决此问题的方法：

nubFourTuples :: (Grouping a, Ord a, Grouping b, Ord b,
                  Grouping c, Ord c, Grouping d, Ord d)
              => [((a,b,c,d),(a,b,c,d))] -> [((a,b,c,d),(a,b,c,d))]
nubFourTuples = (fmap . both) reassociate . nubTuples . (fmap . both) associate
   where associate (w,x,y,z) = ((w,x),(y,z))
         reassociate ((w,x),(y,z)) = (w,x,y,z)
         both f (x,y) = (f x, f y)