代码之家 › 专栏 › 技术社区 › Evgeny

在Haskell中的元组列表中累积值计数

iteration count haskell list

Evgeny · 技术社区 · 6 年前

我试图使用一个模式字符串来解析一个列表,该字符串指示值的类型(年度和季度)。我需要在结果输出中累积季度数。到目前为止,我得出了以下结论:

row = [100, 10, 40, 25, 25]
fmt = "aqqqq"
expected = [('a',1,100),('q',1,10),('q',2,40),('q',3,25),('q',4,25)]

count :: Char -> String -> Int
count letter str = length $ filter (== letter) str

split :: String -> [a] -> [(Char, Int, a)]
split fmt row = [(freq, count freq (fmt' i), x)   
               | (freq, x, i) <- zip3 fmt row [0..]]
               where fmt' i = take (i+1) fmt

-- split "aqqqq" [100, 10, 40, 25, 25]
-- [('a',1,100),('q',1,10),('q',2,40),('q',3,25),('q',4,25)]

我想应该有一些更可读性和性能更好的代码,甚至是一个很棒的单行程序。

"aqqqq" 进入元组列表 [('a',1),('q',1),('q',2),('q',3),('q',4)] 然后增加价值;也许这是一种更好的方法,因为我需要为几行指定一次格式。

3 回复 | 直到 6 年前

Mark Seemann 6 年前

如果你已经有了一个函数 expand 扩大 "aqqqq" 在元组列表中,您可以使用 zipWith :

Prelude> zipWith (\(p, ix) x -> (p, ix, x)) (expand fmt) row
[('a',1,100),('q',1,10),('q',2,40),('q',3,25),('q',4,25)]

这个函数生成该类型的元组 Num t => (Char, t) . 我调用了元组中的值 p 时期 )及 ix (用于 ).用 row 也会产生值,在lambda表达式中,我简单地称之为 x

assembly.jc 6 年前

这里的主要问题是如何转换字符串,比如 "aqqqq"

"aqqqq" => [1, 1, 2, 3, 4]

一旦构建了频率列表,我们就可以使用 zip3

[('a',1,100),('q',1,10),('q',2,40),('q',3,25),('q',4,25)]

显然,我们不能使用 map 生成所需频率列表,因为该值需要累积。要解决这个问题,我建议使用 Data.Map O(n) 到 O(log n) .

使用计算机计算频率很简单 insertWith 作为:

countFreq  c m = insertWith (+) c 1 m

并使用 lookup

accumValue c m = fromMaybe 0 (Map.lookup c m) + 1

现在,直接构建所需列表如下:

mkAccumList (c:cs) m = accumValue c m : mkAccumList cs (countFreq c m)

import Data.Map as Map (empty, lookup, insertWith)
import Data.Maybe (fromMaybe)

countFreq  c m = insertWith (+) c 1 m
accumValue c m = fromMaybe 0 (Map.lookup c m) + 1

split::String -> [a] -> [(Char, Int, a)]
split fmt row = zip3 fmt (mkAccumList fmt Map.empty) row
    where mkAccumList (c:cs) m = accumValue c m : mkAccumList cs (countFreq c m)
          mkAccumList [] _ = []

要使用无限列表,请执行以下操作:

take 8 $ split (cycle "aqqqq") (cycle [100, 10, 40, 25, 25])

给予

[('a',1,100),('q',1,10),('q',2,40),('q',3,25),('q',4,25),('a',2,100),('q',5,10),
('q',6,40)]

Evgeny 6 年前

根据@Mark Seemann的建议,这里有一个完整的清单和一个解决方案。为了更易于阅读,我将lambda改为命名函数,并引入了行格式类型。

count :: Char -> String -> Int
count letter str = length $ filter (== letter) str

type RowFormat = [Char]
expand :: RowFormat -> [(Char, Int)]
expand pat = [(c, count c (take (i+1) pat)) | (c, i) <- zip pat [0..]]

split' :: RowFormat -> [a] -> [(Char, Int, a)]
split' fmt values = zipWith merge (expand fmt) values
      where merge (freq, period) value = (freq, period, value)

结果如预期:

*Main> split' "aqqqq" [100, 10, 40, 25, 25]
[('a',1,100),('q',1,10),('q',2,40),('q',3,25),('q',4,25)]

事后考虑-每次解析行时,我仍然会扩展格式字符串,甚至可能会使用curry parse = split' "aqqqq" 只会延迟计算。下面是我制作专用阅读器功能的尝试:

makeSplitter fmt = \values -> zipWith merge pos values
      where 
        merge (freq, period) value = (freq, period, value)
        pos = expand fmt 
splitRow = makeSplitter "aqqqq" 
a = splitRow [100, 10, 40, 25, 25]

a 是预期结果,同上

[('a',1,100),('q',1,10),('q',2,40),('q',3,25),('q',4,25)]