如何在 Haskell 中重构列表？

发布于 2024-09-19 22:35:03 字数 1413 浏览 3 评论 0原文

我有一个这样的列表：（伪符号）

(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

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

原文

I have a list like this: (Pseudo notation)

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

Type is (Enum a, Bounded a) => [[(a,x)]]. But I need something like this:

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

Type is like (Enum a, Bounded a) => [(a,[x])]

x has an arbitrary number of elements. It can be assumed, that each Member of x is a key in each sublist of the first list.

How is this transformation possible as a lazy haskell algorithm (List doesn't needs to be evaluated completely to return (partitially) result)?

Test data

See above, something like this:

--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,...])]

What I want to do with the data

I want to use it in a function like this:

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

The function has to work on large amounts of data (~10'000 entries per enum), the list should be garbage collectable by the runtime system (The list is adhoc build by another part of the program)

My (uggly) implementation

This is the way, I implemented it, but obviously it doesn't fits the requirements, as the list is traversed multiple times:

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

I'm not at home so can't test it, so there may be a mistake.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

笑梦风尘 2024-09-26 22:35:03

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

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

现在我们有了一个从 key 到 ["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。

Some sample data would have made your question much easier to understand. I assume that given a list like:

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

You want to get

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

If so, the first thing that springs to mind is Data.Map.insertWith. This is like creating a map from keys to values, except if the value already exists, a function you specify is applied to the current value and the new value, and the result is inserted.

For example, if we write:

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

Then step0 is just a map that maps key to value. But if we call it again:

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

Now we have a map from key to ["value","OH HAI"]. This is almost exactly what you want, but instead of lists of strings, you want a list of some Enum/Boundeds.

So, the first step is to take one "row" of your data, and add that to a 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)

Given the first element of input from the very top, you get:

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

Now we just need to accumulate into this map for every row, instead of just the first one. That's just another fold:

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

Now you can write:

toMap2 input

and get:

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

A simple M.toList turns this back into a regular list, which yields output.

回复收藏 0 原文

各自安好 2024-09-26 22:35:03

我不是 100% 确定，但从源代码来看，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

I'm not a 100% sure, but from the sourcecode it looks like Data.List.transpose is lazy.
http://www.haskell.org/ghc/docs/6.12.2/html/libraries/base-4.2.0.1/src/Data-List.html#transpose is my source for it.
I think that transpose can help you to restructure the pointers:

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

So I'd think of something like

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

回复收藏 0 原文

心是晴朗的。 2024-09-26 22:35:03

所以我假设您从 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

So I'm assuming that you started out with a list of q, then mapped them (q -> [(k,v)]) to extract attribute value pairs to give [[(k,v)]] and you want to turn it into a list of pairs that contain the attribute and all the values that were present. Additionally the attribute keys are Bounded Enum so you can enumerate all the keys.

Then what you want to do is iterate over all the keys and select the values

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)

This is lazy; you can test that with

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

回复收藏 0 原文

~没有更多了~