Блог

Я ищу способ преобразовать список в n-кортеж с одним списком для каждого из n конструкторов в непересекающемся объединении. Стандартная библиотека определяет аналогичную функцию специально для Either s:

 partitionEithers :: [Either a b] -> ([a], [b])
 

Я ищу методы решения обобщенной проблемы со следующими требованиями:

• удобно писать
• как можно меньше шаблонных шаблонов
• обрабатывает список за один проход
• тип данных-генераторы, метапрограммирование, существующие библиотеки и т. Д.-Все это разрешено

Пример

Вот пример спецификации с двумя предлагаемыми решениями:

 partitionSum :: [MySum] -> ([A], [B], [C], [D])

data MySum
  = CaseA A
  | CaseB B
  | CaseC C
  | CaseD D

data A = A deriving Show
data B = B deriving Show
data C = C deriving Show
data D = D deriving Show

-- expect "([A,A],[B,B,B],[],[D])"
test :: IO ()
test = print . partitionSum $
  [CaseD D, CaseB B, CaseA A, CaseA A, CaseB B, CaseB B]
 

Первая попытка: n понимания списка, которые пересекают список n раз.

 partitionSum1 :: [MySum] -> ([A], [B], [C], [D])
partitionSum1 xs =
  ( [a | CaseA a <- xs]
  , [b | CaseB b <- xs]
  , [c | CaseC c <- xs]
  , [d | CaseD d <- xs]
  )
 

Вторая попытка: один обход входного списка. Мне приходится вручную пропускать состояние через сгиб, что делает решение немного повторяющимся и раздражающим при написании.

 partitionSum2 :: [MySum] -> ([A], [B], [C], [D])
partitionSum2 = foldr f ([], [], [], [])
  where
    f x (as, bs, cs, ds) =
      case x of
        CaseA a -> (a : as, bs, cs, ds)
        CaseB b -> (as, b : bs, cs, ds)
        CaseC c -> (as, bs, c : cs, ds)
        CaseD d -> (as, bs, cs, d : ds)
 

В дополнение к Representable ответу:

То, что пришло мне в голову, когда я увидел foldr f ([], [], [], []) , состояло в том, чтобы определить моноид, где нулевой случай mempty

 {-# DerivingVia #-}
..
import GHC.Generics (Generically(..), ..)

type Classify :: Type
type Classify = C [A] [B] [C] [D]
  deriving
  stock Generic

  deriving (Semigroup, Monoid)
  via Generically Classify

-- mempty = C [] [] [] []
-- C as bs cs ds <> C as1 bs1 cd1 ds1 = C (as    as1) (bs    bs1) (cs    cs1) (ds    ds1)
 

Generically будет экспортироваться из GHC.Generics в будущем. Он определяется Classify как полугруппа и моноид посредством общего точечного подъема.

С помощью этого все, что вам нужно, — это функция классификатора, которая классифицирует MySum Classify объект и которую вы можете определить partition в терминах foldMap

 classify :: MySum -> Classify
classify = case
  SumA a -> C [a] [] [] []
  SumB b -> C [] [b] [] []
  SumC c -> C [] [] [c] []
  SumD d -> C [] [] [] [d]

partition :: Foldable f => f MySum -> Classify
partition = foldMap classify
 

Поскольку ваша функция представляет собой преобразование сумм в продукты, используется довольно простая реализация generics-sop . Это библиотека, которая расширяет универсалии GHCs более специализированными типами, которые упрощают индукцию по типу алгебры (т. Е. суммы продуктов).

Во-первых, прелюдия:

 {-# LANGUAGE DeriveGeneric, StandaloneDeriving #-}

import Generics.SOP hiding ((:.:))
import qualified GHC.Generics as GHC
import GHC.Generics ((:.:)(..))


partitionSum :: (Generic t) => [t] -> NP ([] :.: NP I) (Code t)
 

Это метод, который вы хотите написать. Давайте рассмотрим его тип.

• единственный аргумент — это список некоторого универсального типа. Довольно прямолинейно. Обратите внимание , что Generic это тот, который от generics-sop , а не от GHC
• возвращаемое значение представляет собой n-арный продукт (n-кортеж), где каждый элемент представляет собой список, состоящий из NP I (сам по себе n-арный продукт, поскольку, как правило, конструкторы алгебраических типов данных могут иметь более одного поля)
• Code t является представлением типа суммы продуктов t . Это список списков типа. например Code (Either a b) ~ '[ '[a], '[b] ] . Общее представление значений t SOP I (Code t) -это сумма продуктов по «коду».

Чтобы реализовать это, мы можем преобразовать каждый t из них в его общее представление, а затем свернуть полученный список:

 
partitionSum = partitionSumGeneric . map from

partitionSumGeneric :: SListI xss => [SOP I xss] -> NP ([] :.: NP I) xss
partitionSumGeneric = foldr ((SOP x) -> classifyGeneric x) emptyClassifier
 

partitionSumGeneric в значительной степени то же partitionSum самое , что и, но оперирует общими представлениями значений.

А теперь самое интересное. Давайте начнем с базового случая нашей складки. Это должно содержать пустые списки в каждой позиции. generics-sop обеспечивает удобный механизм для создания типа продукта с одинаковым значением в каждой позиции:

 emptyClassifier :: SListI xs => NP ([] :.: NP I) xs
emptyClassifier = hpure (Comp1 [])
 

Рекурсивный случай выглядит следующим образом: если значение имеет тег в индексе k , добавьте это значение в список в индексе k в накопителе. Мы можем сделать это с одновременной рекурсией как для типа суммы (сейчас он общий, поэтому значение типа NS (NP I) xs — сумма продуктов), так и для аккумулятора.

 classifyGeneric :: NS (NP I) xss -> NP ([] :.: NP I) xss -> NP ([] :.: NP I) xss
classifyGeneric (Z x)  (Comp1 l :* ls) = (Comp1 $ x : l) :* ls
classifyGeneric (S xs) (      l :* ls) =              l  :* classifyGeneric xs ls
 

Ваш пример с некоторыми дополнительными данными, чтобы сделать его немного более интересным:

 data MySum
  = CaseA A
  | CaseB B
  | CaseC C
  | CaseD D

-- All that's needed for `partitionSum' to work with your type
deriving instance GHC.Generic MySum
instance Generic MySum

data A = A Int deriving Show
data B = B String Int deriving Show
data C = C deriving Show
data D = D Integer deriving Show

test = partitionSum $
  [CaseD $ D 0, CaseB $ B "x" 1, CaseA $ A 2, CaseA $ A 3, CaseB $ B "y" 4, CaseB $ B "z" 5]
 

в результате получается:

 Comp1 {unComp1 = [I (A 2) :* Nil,I (A 3) :* Nil]} :* Comp1 {unComp1 = [I (B "x" 1) :* Nil,I (B "y" 4) :* Nil,I (B "z" 5) :* Nil]} :* Comp1 {unComp1 = []} :* Comp1 {unComp1 = [I (D 0) :* Nil]} :*Nil