3

我有一个定义如下的结构：

type P = [(Int, Int)]

我需要从该结构的列表中创建一个函数，如果满足以下条件，则添加位于元组中第一个位置的项目：元组的第二个元素相同。

add :: [P] -> P
add lists = ......

例如

add [[(1,2), (3,0)], [(3,1), (7,0)]]

结果将是[(1,2), (3,1), (10.0)]。

因为只会将元组 (3.0) 与 (7.0) 添加，因为它与 0 匹配。

4

4 回答 4

7

这是一个“键控”操作，在标准库的帮助下很容易解决。 

import qualified Data.Map as M

Data.Map实现有限关联映射——即M.Map k a有一组类型的键k，并且它与每个键关联一个类型的值a。

对这类问题非常有用的功能是fromListWith：

M.fromListWith :: (a -> a -> a) -> [(k,a)] -> M.Map k a

第二个参数，(k,a)元组列表，只是简单的关联，将给定的键与给定的值相关联。第一个参数是一个组合函数，它说明如果重复键出现在列表中，如何处理这些值。

您还必须使用M.toList :: M.Map k a -> [(k,a)] which 为您返回存储在 Map 中的关联列表。这是一个例子：

ghci> M.toList (M.fromListWith (+) [(1,2), (2,3), (1,4), (3,5)])
[(1,6),(2,3),(3,5)]

请注意键是元组的第一个元素，这与您陈述问题的方式相反。我们已经合并(1,2)到. 我们添加是因为我们提供了组合功能。(1,4)(1,6)(+)

这一个功能解决了您的问题——剩下的只是一个小管道，我将留给你。

于 2013-05-31T17:07:54.847 回答
4

让我们分解这个问题。

所以你有一个列表列表

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

如果第二个元素全部（全部？或一些？）相同，您想要垂直第一个元素的总和，否则第一个列表中的元组（根据您的示例判断，您的规范实际上并没有说明会发生什么） .

你应该做的第一件事是transpose这个列表，以获得更适合我们计算的东西。

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

现在问题本质上是对这些子列表中的每一个的折叠。因此，您编写了一个函数来为这些列表之一执行此操作：

collapse :: [(Int, Int)] -> (Int, Int)

然后你map在整个转置列表上使用这个函数：

add lists = map collapse $ transpose lists
// or point-free
add = map collapse . transpose

现在您只需要编写collapse.

于 2013-05-31T11:48:21.760 回答
1

合并和排序后（在第二个元素上），您可以使用变体group(By)来组合具有相同第二个元素的元组。

import Data.List
import Data.Ord

add :: [P] -> P
add = combine . sortBy (comparing snd) . concat
  where
    combine []     = []
    combine (x:xs) = (fst x + foldr ((+) . fst) 0 ys, snd x) : combine zs
      where
        (ys, zs) = span ((snd x ==) . snd) xs

或者您可以使用groupBy为每个不同的snd值获取一个列表并折叠每个列表：

import Data.Function

add' :: [P] -> P
add' = map sumFst . groupBy ((==) `on` snd) . sortBy (comparing snd) . concat
  where
    sumFst = foldr1 $ \(a, b) (x, _) -> (a+x, b)
    -- or, importing Data.Biapplicative from bifunctors package:
    --sumFst = foldr1 $ (+) `biliftA2` const
于 2013-05-31T18:04:33.097 回答
1

据我了解，您想要获取一个类型列表[[(Int, Int)]]并将具有相同第二个元素的任何元组的第一个元素相加。您可以完全忽略它是一个列表列表，并且concat马上就可以了，除非列表的结构可以帮助您确定应该添加哪些元素（但我似乎没有任何证据表明这一点）。然后你得到 minimum snd，按值对列表进行排序snd，并通过列表递归，调用span :: (a -> Bool) -> [a] -> ([a], [a])它接受一个谓词并在满足谓词的最后一个元素处拆分一个列表。由于列表已排序，这将捕获所有具有相同的元组snd。然后我们折叠那个元组列表。

add :: [[(Int, Int)]] -> [(Int, Int)]
add list = addT (minBound :: Int) $ sortBy sortF (concat list)
    where sortF (_,x) (_,y)
                | x < y  = LT
                | x > y  = GT
                | x == y = EQ
          addT n list = sumFunc $ span (sndIs n) list
              where sndIs n (_,y) = y == n 
                    sumFunc ([],b)= addT (n+1) b
                    sumFunc (a,[])= [(foldr (\(x,y) (w,v) -> (x+w,y)) (0,0) a)]
                    sumFunc (a,b) = (foldr (\(x,y) (w,v) -> (x+w,y)) (0,0) a):(addT (n+1) b)

然后 ：

> add [[(1,2), (3,0)], [(3,1), (7,0)]]
> [(10,0),(3,1),(1,2)]

唯一的问题是复杂性非常糟糕（尝试add [[(43, minBound :: Int), (10, maxBound :: Int)]]）。如果你想让它更快，你应该snd首先得到所有的 s 并且只调用 addT 那些，如果你可能在值上使用这个函数有很大的不同。

于 2013-05-31T16:30:42.130 回答