Haskell中的列表处理

Question

我是一位自学 Haskell 的学习者，遇到了问题需要帮助。

背景：

type AInfo  =  (Char, Int)
type AList  =  [AInfo]       (let’s say [(‘a’, 2), (‘b’,5), (‘a’, 1), (‘w’, 21)]

type BInfo  =  Char
type BList  =  [BInfo]      (let’s say [‘a’, ‘a’, ‘c’, ‘g’, ‘a’, ‘w’, ‘b’]

一个快速的编辑： 以上信息仅供参考。实际列表元素要复杂一些。此外，这些列表是动态的（因此需要使用IO单子），我需要在程序运行期间保留/传递/“返回”/访问和更改这些列表。

我想要做以下事情： 对于AList的所有元素，检查是否与BList的所有元素相等，并且如果AList元素（对）的字符等于Blist中的字符，则将一个添加到AList元素（对）的Int值并从BList中删除该字符。

因此，这意味着在第一个AList元素针对BList的所有元素进行检查之后，列表的值应为：

AList [(‘a’、5)、（‘b’、5）、（‘a’、1）、（‘w’、21）]

BList ['c'、'g'、'w'、'b']

最后，列表值应为：

AList [(‘a’、5)、（‘b’、6）、（‘a’、1）、（‘w’、22）]

BList ['c'、'g']

当然，所有这些都发生在IO单子中。

我尝试过的事情：

使用mapM和一个递归的帮助函数。我已经看了两者： 对AList的每个元素检查对BList的每个元素 - mapM（myHelpF1 alist）blist和 对BList的每个元素进行检查，以检查AList - mapM（myHelpF2 alist）blist

将两个列表传递给函数并使用复杂的if / then / else和helper函数调用（感觉就像我强制Haskell成为迭代的一样；混乱的复杂代码，不正确感觉好。）

我考虑使用filter，AList元素和Blist的字符值来创建第三个Bool列表，并计算True值的数量。更新Int值。然后在BList上使用过滤器来删除那些...的BList元素（再次不感觉正确，不太像Haskell）。

我认为我知道有关该问题的事情：

解决方案可能超出了基本。因此，更有经验的Haskellers将在打字时低声自语“什么新手”。任何指针都将不胜感激。（抱怨...）

- user1872391

---

请发布（一些/大部分）您的IO代码。 - Will Ness

为什么你的alist中显示了重复的条目（对于“'a'”）？这是必要的吗？ - Will Ness

Answer 1

一些提示：

不要使用 [(Char, Int)] 来实现 "AList"。你需要的数据结构是有限映射：Map Char Int。特别是要看 member 和 insertWith。toList 和 fromList 可以将当前 AList 的表示转换为 Map，因此即使你被困在该表示法中，也可以在算法过程中进行转换并在最后转换回来。（这比维护一个列表更有效，因为你要执行很多查找操作，并且有限映射API比列表更易于使用）

我会将问题分为两个阶段：(1) partition出blist中的元素是否在映射表中，(2) 对已经在映射表中的元素进行insertWith操作。然后你可以返回结果映射表和其他分区。

我还会摒弃一些无意义的假设，比如键是Char类型--你可以说它们是任何满足必要约束条件（可以放入Map中、需要Ord排序）的类型k（表示“键”）。你可以使用小写字母的类型变量实现这一点。

import qualified Data.Map as Map

sieveList :: (Ord k) => Map.Map k Int -> [k] -> (Map.Map k Int, [k])

编写更通用的算法有助于捕获错误，因为它确保您不会使用不必要的假设。

哦，还有这个程序不应该在IO单子中。这是纯代码。

- luqui

---

谢谢回复。我认为你说的有道理……使用不同的数据结构（Map而不是List）。这可能会起作用……给我一天左右的时间，我会告诉你我的进展如何…… - user1872391

Luqui，感谢您指向Data.Map。我改变了我的逻辑，使得AList和BList只包含唯一的元素，并且能够使用现有的Haskell方法来操作/转换/序列化这些列表。话虽如此，随着列表长度的增加，当前性能迅速下降，因此我又回到了研究Data.Map。 - user1872391

Answer 2

虽然我不是Haskell专家，但我有一个部分尝试，可以返回一次操作的结果。也许你可以找出如何映射其余部分来获得解决方案。addwhile很聪明，因为您只想更新列表中元素的第一次出现（如果存在两次，它将只添加0）。欢迎进行代码评审。

import Data.List
type AInfo = (Char, Int)
type AList = [AInfo]

type BInfo = Char
type BList = [BInfo]

lista = ([('a', 2), ('b',5), ('a', 1), ('w', 21)] :: AList)
listb = ['a','a','c','g','a','w','b']

--step one, get the head, and its occurrences
items list = (eleA, eleB) where
        eleA = length $ filter (\x -> x == (head list)) list
        eleB = head list

getRidOfIt list ele = (dropWhile (\x -> x == ele) list) --drop like its hot

--add to lista
addWhile :: [(Char, Int)] -> Char -> Int -> [(Char,Int)]    
addWhile [] _ _ = []
addWhile ((x,y):xs) letter times = if x == letter then (x,y+times) : addWhile xs letter times 
                                   else (x,y) : addWhile xs letter 0

--first answer
firstAnswer = addWhile lista (snd $ items listb) (fst $ items listb)
--[('a',5),('b',5),('a',1),('w',21)]

- The Internet

Answer 3

import Data.List

type AInfo  =  (Char, Int)
type AList  =  [AInfo]

type BInfo  =  Char
type BList  =  [BInfo]

process :: AList -> BList -> AList
process [] _ = []
process (a:as) b = if is_in a b then (fst a,snd a + 1):(process as (delete (fst a) b)) else a:process as b where
        is_in f [] = False
        is_in f (s:ss) = if fst f == s then True else is_in f ss

*Main> process [('a',5),('b',5),('a',1),('b',21)] ['c','b','g','w','b']
[('a',5),('b',6),('a',1),('b',22)]
*Main> process [('a',5),('b',5),('a',1),('w',21)] ['c','g','w','b']
[('a',5),('b',6),('a',1),('w',22)]

可能一个重要的免责声明：我对Haskell很生疏，甚至有些无能为力，但作为一种放松的午夜运动，我写了这个东西。它应该能做你想要的事情，尽管它不返回BList。通过一些修改，你可以让它返回一个(AList，BList)元组，但我认为如果需要那种操作，最好使用命令式语言。

或者，有一个优雅的解决方案，我对Haskell太无知了，不知道它是什么。

- Father Deus

---

谢谢您的回复。您遇到了我正在面临的同样问题；我需要“返回”修改后的两个列表。 - user1872391

Answer 4

你所描述的操作是纯的，正如@luqui所指出的那样，因此我们只需将其定义为一个纯的Haskell函数。它可以通过fmap（或do）在单子内（包括IO）中使用。

import Data.List

combine alist blist = (reverse a, b4) where

首先，我们对B列表进行排序和计数：

  b = map (\g->(head g,length g)) . group . sort $ blist

我们需要导入group和sort以便可用。接下来，我们遍历alist并执行我们的操作：

  (a,b2) = foldl g ([],b) alist
  g (acc,b) e@(x,c) = case pick x b of 
                        Nothing -> (e:acc,b)
                        Just (n,b2) -> ((x,c+n):acc,b2)
  b3 = map fst b2
  b4 = [ c | c <- blist, elem c b3 ]

现在，pick（挑选）的用法必须是

  pick x [] = Nothing
  pick x ((y,n):t) 
     | x==y = Just (n,t)
     | otherwise = case pick x t of Nothing -> Nothing
                                    Just (k,r) -> Just (k, (y,n):r)

当然，pick 执行线性搜索，因此如果性能（速度）成为问题，则应更改 b 以允许二进制搜索（树等，类似于 Map）。计算 b4（即 filter (`elem` b3) blist）是另一个潜在的性能问题，它需要反复检查是否存在于 b3 中。同样，在树中检查存在性要比在列表中快，一般而言。

测试运行：

> combine [('a', 2), ('b',5), ('a', 1), ('w', 21)] "aacgawb"

([('a',5),('b',6),('a',1),('w',22)],"cg")

---

编辑：你可能希望反过来，沿着blist滚动，同时更新alist并在结果中产生（或不产生）blist的元素（我的代码中的b4）。这样算法将更加“局部”地处理长输入流（假设你的blist很长，尽管你没有说）。如上所述，它会有一个空间问题，多次使用输入流blist。我会将其保留为一种思路的示例。

所以如果你决定走第二条路，首先将你的alist转换成一个Map（注意重复项！）。然后，使用scanl扫描blist，利用updateLookupWithKey更新计数映射表，并同时逐个决定是否输出blist中的每个成员。因此，累加器的类型必须是(Map a Int, Maybe a)，其中a是你的元素类型（blist :: [a]）：

scanl :: (acc -> a -> acc) -> acc -> [a] -> [acc]

scanning = tail $ scanl g (Nothing, fromList $ reverse alist) blist
g (_,cmap) a = case updateLookupWithKey (\_ c->Just(c+1)) a cmap of
                 (Just _, m2) -> (Nothing, m2)   -- seen before
                 _            -> (Just a, cmap)  -- not present in counts 
new_b_list = [ a | (Just a,_) <- scanning ]
last_counts = snd $ last scanning

如果你需要保留原来的重复项（为什么呢？），则需要将 toList last_counts 与原始的 alist 结合起来。

- Will Ness

---

Will，感谢您的回复。我确实尝试过使用Data.Map，但最终得出结论，我在逻辑上存在一个基本错误，需要让BList只包含唯一元素。这样可以让我使用现有的Haskell列表方法。话虽如此，我目前正在多次按顺序遍历AList和BList，如果将它们作为映射（哈希表、字典）而不是列表，可能会有性能提升。 - user1872391

你的意思是，AList只包含BList中每个唯一元素的计数？根据你的描述，你的算法可以针对BList进行在线处理（生成并忘记），就像我的第二种变体一样。如果你的BList只包含唯一元素，那么你不需要对它们进行计数（而且它也不会很长，对吧？）。 - Will Ness