如何重构Haskell中的List？

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不需要完全评估返回(partitially)结果)？

测试数据

见上文,如下所示:

--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个条目),该列表应该是运行时系统可以垃圾收集的(该列表是由程序的另一部分构建的adhoc)

我的(uggly)实施

这是我实现它的方式,但显然它不符合要求,因为列表遍历了多次:

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"].这几乎就是你想要的,但是你需要一些Enum/Boundeds列表而不是字符串列表.

因此,第一步是获取数据的一行"行",然后将其添加到地图中:

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将其转换为常规列表,从而产生output.