代码之家 › 专栏 › 技术社区 › fuz

如何在Haskell中重组列表?

transformation haskell list

fuz · 技术社区 · 14 年前

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

(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的每个成员都是第一个列表的每个子列表中的一个键。

作为一个lazy haskell算法,这个转换怎么可能(列表不需要完全求值就可以返回(部分)结果)?

试验数据

如上图所示:

--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

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

我的(丑陋的)实现

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

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

我不在家,所以无法测试,所以可能会出错。

3 回复 | 直到 14 年前

Jakob Runge 14 年前

我不是百分之百肯定,但从源代码来看Data.List.transpose转置他很懒。 http://www.haskell.org/ghc/docs/6.12.2/html/libraries/base-4.2.0.1/src/Data-List.html#transpose 我认为转置可以帮助你重组指针:

transpose [[1,2,3],[4,5,6],[7,8,9]]
-- results in [[1,4,7],[2,5,8],[3,6,9]]

foo :: [[(a, b)]] -> [(a, [b])]
foo = map (\x -> (fst (head x), map snd x)) . transpose

jrockway 14 年前

一些样本数据会让你的问题更容易理解。我假设给定如下列表:

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"] . 这几乎正是您想要的,但是您想要的不是字符串列表,而是一些枚举/边界的列表。

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

Geoff Reedy 14 年前

所以我假设你从一个q的列表开始,然后映射它们(q->[(k,v)])来提取属性-值对,得到[[(k,v)]],然后你想把它变成一个包含属性和所有存在的值的对的列表。此外,属性键是有界枚举,因此可以枚举所有键。

然后您要做的是遍历所有键并选择值

f :: (Enum k, Bounded k) => [[(k,v)]] -> [(k,[v])]
f kvss = map (\k -> (k, map snd $ filter ((eqenum k).fst) $ kvs)) $ enumFromTo minBound maxBound 
  where kvs = concat kvss
        eqenum e1 e2 = (fromEnum e1) == (fromEnum e2)

这是懒惰的;你可以用

data Foo = Foo1 | Foo2
  deriving (Enum, Bounded, Show, Eq)

infd = map (\x -> [(Foo1, 2*x), (Foo2, x*x)]) [1..]

take 5 $ snd $ (f infd) !! 0
take 5 $ snd $ (f infd) !! 1