Как реструктуризировать список в 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,...])]

Что я хочу сделать с данными

IВы хотите использовать его в такой функции:

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

Функция должна работать с большими объемами данных (~ 10 000 записей на перечисление), список должен собираться мусором системой времени выполнения (Список создается adhoc другой частью программы)

Моя (некрасивая) реализация

Я так и реализовал, но, очевидно, он не соответствует требованиям, так каксписок просматривают несколько раз:

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.

Answer 2

Я не уверен на 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

Answer 3

Итак, я предполагаю, что вы начали со списка q, затем сопоставили их (q -> [(k, v)]), чтобы извлечь пары значений атрибута, чтобы получить [[(k, v)]] иВы хотите превратить его в список пар, которые содержат атрибут и все значения, которые присутствовали.Кроме того, ключами атрибута являются Bounded Enum, так что вы можете перечислить все ключи.

Затем вам нужно перебрать все ключи и выбрать значения

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