时间戳

首页 > 解决方案 > 用其他列表过滤自定义数据类型列表的最佳方法是什么（迭代它）

haskell - 用其他列表过滤自定义数据类型列表的最佳方法是什么（迭代它）

问题描述

我有一个关于用我自己的类型与另一个过滤列表的问题。

我来自python，所以haskell对我来说很难理解。

type PersonId = Integer
type PersonName = String
type InfectionId = Integer
type InfectionName = String

data TerminationType = Recovered | Dead
                       deriving (Eq, Show)

data Person = Person PersonId PersonName
              deriving Show

data Infection = Infection InfectionId PersonId InfectionName
                 deriving Show

data Termination = Termination InfectionId TerminationType
                   deriving Show

type Persons = [Person]
type Infections = [Infection]
type Terminations = [Termination]

pers :: Persons
pers = [Person 1 "Augustin"
       ,Person 2 "Baltazar"
       ,Person 42 "Ctirad"
       ,Person 128 "Zdenek"
       ,Person 5 "Drahoslav"
       ]

infs :: Infections
infs = [Infection 2020 1 "COVID"
       ,Infection 2019 42 "COVID"
       ,Infection 1 5 "COVID"
       ,Infection 5 128 "rymicka"
       ,Infection 3 5 "astma"
       ,Infection 2 1 "astma"
       ,Infection 128 5 "zapal plic"
       ]

ters :: Terminations
ters = [Termination 2020 Dead
       ,Termination 2 Recovered
       ,Termination 2019 Recovered
       ,Termination 128 Dead
       ]

我正在尝试创建一个可以找到所有活动案例的功能。因此，它将根据当前感染列出已记录的感染列表并删除所有终止。

我的想法是使用地图从 Terminations 获取所有 ID，然后使用来自 python 的“in”之类的东西从 Infections 过滤具有该 ID 的项目，但该解决方案似乎太“OOP”了。

类似的东西。

activeCases :: Infections -> Terminations -> [InfectionId]
activeCases infec term = filter (infec.id in (map getId term)) infec
    where getId (Termination y _) = y

我预定义的“pers，infs”和“ters”的最终结果是

activeCases infs ters ~>* [Infection 1 5 "COVID",Infection 5 128 "rymicka",Infection 3 5 "astma"]

有人可以告诉我解决此类问题的正确方法是什么吗？

标签： haskellfunctional-programming

解决方案

我的想法是使用地图从 Terminations 获取所有 ID，然后使用来自 python 的“in”之类的东西从 Infections 过滤具有该 ID 的项目，但该解决方案似乎太“OOP”了。

一点也不，事实上，你有正确的想法！看起来你只需要一些帮助来表达它。

您可以更改代码以使用该elem函数，该函数类似于 Python 的in运算符，但适用于任何具有相等元素的可折叠容器：

elem :: (Foldable t, Eq a) => a -> t a -> Bool

在这里，您将使用t ~ []and a ~ InfectionId，因此它将具有专门的类型elem :: InfectionId -> [InfectionId] -> Bool。

如果您只想返回 ID，而不是整个Infection值，您可以先使用map.

activeCases :: Infections -> Terminations -> [InfectionId]
activeCases infections terminations

  -- Select the IDs that are *not* found in the list of termination IDs.
  = filter (\ i -> not (i `elem` terminationIds))

    -- Extract the ID from each Infection.
    (map infectionId infections)
  where
    terminationIds = map terminationId term
    terminationId (Termination y _) = y
    infectionId (Infection i _ _) = i

回想一下，filter条件指示要保留哪些元素，而不是要过滤掉哪些元素，因此对于活动案例，您要添加一个not. 我的记忆是“咖啡过滤器让咖啡通过”（所以filter even让even价值观通过）。

不过，您可以通过几种方式简化它。首先，您可以将data类型制作成记录并为每个字段命名，以便您可以更方便地提取（或更新）它：

data Person = Person
  { personId :: PersonId
  , personName :: PersonName
  }
  deriving (Show)

data Infection = Infection
  { infectionId :: InfectionId
  , infectionPerson :: PersonId
  , infectionName :: InfectionName
  }
  deriving (Show)

data Termination = Termination
  { terminationInfection :: InfectionId
  , terminationType :: TerminationType
  }
  deriving (Show)

映射和过滤可以用列表推导来表示，并且为了方便可以将notandelem函数组合成。notElem把这些放在一起：

activeCases :: Infections -> Terminations -> [InfectionId]
activeCases infections terminations =
  [ infectionId infection
  | infection <- infections
  , infectionId infection `notElem` terminationIds
  ]
  where
    terminationIds =
      [ terminationInfection termination
      | termination <- terminations
      ]

如果您愿意，您仍然可以在理解中使用模式匹配：

-- Positional matching:

[ i
| Infection i _ _ <- infections
, i `notElem` terminationIds
]

-- Named matching:

[ i
, Infection { infectionId = i } <- infections
, i `notElem` terminationIds
]

还有更高层次的方法。Termination对每个ID的 ID 列表进行线性扫描Infection是 O(n 2 )，但您真正想要的是一个集合差异，可以使用 map & set 数据结构更有效地计算，例如Data.Mapand Data.Set(or Data.IntMapand Data.IntSet) from containers。例如，如果您将数据存储为从 ID 到该 ID 记录的映射：

import Data.Map (Map)
import Data.Set (Set)

type Persons = Map PersonId Person
type Infections = Map InfectionId Infection
type Terminations = Map InfectionId Termination

infs :: Infections
infs = Map.fromList
  [ (i, infection)
  | infection <-
    [ Infection 2020 1 "COVID"
    , Infection 2019 42 "COVID"
    , Infection 1 5 "COVID"
    , Infection 5 128 "rymicka"
    , Infection 3 5 "astma"
    , Infection 2 1 "astma"
    , Infection 128 5 "zapal plic"
    ]
  , let i = infectionId infection
  ]

那么活动病例集是感染的关键集减去终止病例集，可以在 O( n log n ) 时间内计算：

import qualified Data.Map as Map
import qualified Data.Set as Set

activeCases :: Infections -> Terminations -> Set InfectionId
activeCases infections terminations
  = infectionIds `Set.difference` terminatedInfections
  where
    infectionIds = Map.keysSet infections
    terminatedInfections = Set.fromList
      $ map terminationInfection
      $ Map.elems terminations

或者由于 aTermination也由 a 标识InfectionId，因此只是键集的差异：

Map.keysSet infections `Set.difference` Map.keysSet terminations

推荐阅读