list - 如何在 Haskell 中重构列表？

Question

我有一个这样的列表:(伪符号)

(X,...) -> (X,...) -> (X,...) -> ...
   |          |          |
   V          V          V
(Y,...)    (Y,...)    (Y,...)
   |          |          |
   V          V          V
(Z,...)    (Z,...)    (Z,...)

类型为(Enum a, Bounded a) => [[(a,x)]]。但我需要这样的东西:

(X, ... -> ... -> ... -> ...
   |
   V
(Y, ... -> ... -> ... -> ...
   |
   V
(Z, ... -> ... -> ... -> ...

类型类似于(Enum a, Bounded a) => [(a,[x])]

x 具有任意数量的元素。可以假设，x 的每个成员都是第一个列表的每个子列表中的键。

这种转换如何作为惰性 Haskell 算法实现(List 不需要完全评估即可返回(部分)结果)？

测试数据

参见上面，类似这样的内容:

--Input
[[(Foo,1),(Bar,1),(Baz,1)],[(Foo,2),(Bar,2),(Baz,2)],...]

--Output
[(Foo,[1,2,3,...]),(Bar,[1,2,3,...),(Baz,[1,2,3,...])]

我想用数据做什么

我想在这样的函数中使用它:

myFunc :: [(MyEnum,[Int])]
myFunc x@((_,(_:[])):_) = x
myFunc x            = foldTheListRecursively

该函数必须处理大量数据(每个枚举约 10'000 个条目)，该列表应该可由运行时系统进行垃圾收集(该列表是由程序的另一部分临时构建的)

我的(丑陋的)实现

是这样的，我实现了，但是显然不符合要求，因为列表被遍历了多次:

restructList :: [[(a,x)]] -> [(a,[x])]
resturctList list = (\x -> (x,listFor x)) <$> keys where
  keys = fst <$> head list
  listFor x = snd <$> any ((==x).fst) <$> list

我不在家，无法测试，所以可能会有错误。

Answer 1

一些示例数据会让您的问题更容易理解。我假设给定一个如下列表:

input = [[("foo", 1), ("foo", 2)], [("bar", 3), ("bar", 4)]]

你想要得到

output = [("foo",[1,2]), ("bar",[3,4])]

如果是这样，首先想到的是 Data.Map.insertWith。这就像创建从键到值的映射，除非该值已存在，您指定的函数将应用于当前值和新值，并插入结果。

例如，如果我们写:

import qualified Data.Map as M
step0 = M.insertWith (++) "key" ["value"] M.empty

那么step0只是一个将键映射到值的映射。但如果我们再次调用它:

step1 = M.insertWith (++) "key" ["OH HAI"] step0

现在我们有了一个从键到["value","OH HAI"]的映射。这几乎正​​是您想要的，但是您需要一些枚举/有界列表，而不是字符串列表。

因此，第一步是获取数据的一个“行”，并将其添加到 map 中:

import qualified Data.List as L
toMap1 :: M.Map a b -> [(a,b)] -> M.Map a b
toMap1 = L.foldr (λ(k,v) m → M.insertWith (++) k [v] m)

给出从最顶部开始的 input 的第一个元素，您将得到:

toMap M.empty (head input)
    ==> [("foo",[1,2])]

现在我们只需要将每一行累积到该映射中，而不仅仅是第一行。这只是另一种折叠:

toMap2 :: [[(a,b)]] -> Map a b
toMap2 = L.foldr (flip toMap1) M.empty

现在你可以写:

toMap2 input

并得到:

fromList [("bar",[3,4]),("foo",[1,2])]

一个简单的M.toList将其转换回常规列表，从而产生输出。