Накапливать количество значений в списке кортежей в Haskell - PullRequest
Новая
       26

Накапливать количество значений в списке кортежей в Haskell

0 голосов
/ 05 января 2019

Я пытаюсь проанализировать список, используя строку шаблона, в которой указаны типы значений (годовые и квартальные). Мне нужно накапливать номера кварталов в полученном результате. До сих пор я придумал это: 

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 ]

0 голосов
/ 05 января 2019

По предложению @Mark Seemann приведен полный список решений. Я изменил лямбду на именованную функцию для большей читабельности и ввел тип для формата строки. 

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)]

Запоздалая мысль - я все еще расширяю строку формата каждый раз, когда анализирую строку, возможно, даже карри 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)]
0 голосов
/ 05 января 2019

Основная проблема здесь заключается в том, как преобразовать строку, скажем, "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)]
0 голосов
/ 05 января 2019

Если у вас уже есть функция 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)]

Функция expand создает кортежи типа Num t => (Char, t). Я назвал значения внутри этого кортежа p (для period ) и ix (для index ). Сжатие этого списка кортежей с row также приводит к значениям, которые I в лямбда-выражении просто называют x.

...