Haskell计算满足查询的列表的元素

Question

我正在使用CSV文件,我将它们解析为[[String]]该数组中的第一个[String]是头文件,例如:

["Code","Address","Town"]

其余的是信息阵列

["ABA","12,east road", "London"]

我想创建一个查询系统,其中输入和结果将看起来像这样

>count "Town"="*London*" @1="A*"
14 rows

列名可以作为字符串输入或作为@与列的索引我有一个案例开关来识别第一个单词输入,因为我将扩展我的CSV阅读器以获得不同的功能.当它看到单词计数时,它将转到一个将返回行数的函数.我不知道如何开始解析查询.起初我以为我可能会在单词count之后将结果字符串拆分成每个查询的字符串列表,执行一个并使用满足此查询的列表再次检查下一个,留下一个列表,所有查询都是满意,然后计算条目数量并返回它们.还有一个案例开关来识别第一个输入是字符串还是@符号.*用于表示单词后面的零或任何字符.我不知道如何开始实现这个或者如果我错过了我的解决方案可能遇到的问题.启动我的任何帮助,我都会非常满意.我对Haskell不是很先进(因为我刚开始),所以我也很感激保持简单.谢谢

Answer 1

这是一种可能的方法.

首先,让我们稍微离开您的字符串列表列表,让我们将记录表示为键/值对,这样数据库就只是一个记录列表:

type Field  = (String, String) -- key, value                                    
type Record = [Field]
type Db     = [Record]

在您的表示中读取CSV数据然后变为:

type Csv = [[String]]

fromCsv :: Csv -> Db
fromCsv []         = []
fromCsv (ks : vss) = map (zip ks) vss

现在,让我们谈谈查询.在您的设置中,查询本质上是一个过滤器列表,其中每个过滤器标识一个字段并匹配一组值:

type Query  = [Filter]
type Filter = (Selector, ValueFilter)

字段可以通过名称或基于一个(!)的索引来选择:

data Selector = FieldName String | FieldIndex Int

通过应用一系列简单的解析器来匹配值,其中解析器可识别单个字符,也可识别零个或多个任意字符的序列:

type ValueFilter = [Parser]
data Parser      = Char Char | Wildcard

可以使用成功列表方法来实现解析,其中每个成功表示剩余输入,即解析器未使用的输入部分.剩余输入的空列表表示失败.(因此,请注意之间的差[],并[[]]在下面的情况下,所产生的结果).

parse :: Parser -> String -> [String]
parse (Char c) (c' : cs') | c == c' = [cs']
parse Wildcard []                   = [[]]
parse Wildcard cs@(_ : cs')         = cs : parse Wildcard cs'
parse _ _                           = []

过滤值然后发展为回溯:

filterValue :: ValueFilter -> String -> Bool
filterValue ps cs = any null (go ps cs)
  where
    go [] cs       = [cs]
    go (p : ps) cs = concatMap (go ps) (parse p cs)

价值选择很简单:

select :: Selector -> Record -> Maybe String
select (FieldName s) r                           = lookup s r
select (FieldIndex n) r | n > 0 && n <= length r = Just (snd (r !! (n - 1)))
                        | otherwise              = Nothing

现在应用记录过滤器相当于构建记录的谓词:

apply :: Filter -> Record -> Bool
apply (s, vf) r = case select s r of
  Nothing -> False
  Just v  -> filterValue vf v

最后,为了执行完整的查询,我们有

exec :: Query -> Db -> [Record]
exec = (flip . foldl . flip) (filter . apply)

(我将查询解析自己留作练习:

readQuery :: String -> Maybe Query
readQuery = ...

但我建议使用解析器 - 组合器库,如parsec或uulib.)

现在,让我们来测试吧.首先,我们以CSV格式引入一个小型数据库:

csv :: Csv
csv =
  [ ["Name" , "City"      ]
     -------  ------------                                                      
  , ["Will" , "London"    ]
  , ["John" , "London"    ]
  , ["Chris", "Manchester"]
  , ["Colin", "Liverpool" ]
  , ["Nick" , "London"    ]
  ]

然后,我们构造一个简单的查询:

-- "Name"="*i*" @2="London"                                                     
query :: Query
query =
  [ (FieldName "Name", [Wildcard, Char 'i', Wildcard])
  , (FieldIndex 2,
      [Char 'L', Char 'o', Char 'n', Char 'd', Char 'o', Char 'n'])
  ]

实际上,对数据库运行查询会产生:

> exec query (fromCsv csv)
[[("Name","Will"),("City","London")],[("Name","Nick"),("City","London")]]

或者,如果您只是在计算查询结果之后:

> length $ exec query (fromCsv csv)
2

当然,这只是一种方法,当然可以想到许多替代方案.正如我们上面所做的那样,在小函数中解决问题的一个很好的方面是,您可以轻松地单独测试和试验小块解决方案.