3

我正在自学 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 monad），我需要在程序运行期间保留/传递/“返回”/有权访问和更改列表。

我希望执行以下操作：

对于 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 monad 中。

我尝试过的事情：

  1. 使用 mapM 和递归辅助函数。我看过两个：

    AList 的每个元素都检查 bList 的每个元素 -- mapM (myHelpF1 alist) blist 和 BList 的每个元素都检查 AList 的每个元素 - mapM (myHelpF2 alist) blist

  2. 将两个列表都传递给一个函数并使用复杂的 if/then/else 和辅助函数调用（感觉就像我在强迫 Haskell 进行迭代；混乱的复杂代码，感觉不对。）

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

我想我知道的关于这个问题的事情：

解决方案可能非常简单。如此之多，更有经验的 Haskeller 会在他们输入回复时低声咕哝“真是个菜鸟”。

任何指针将不胜感激。（喃喃自语……）

4

4 回答 4

3

几点建议：

不要[(Char, Int)]用于“AList”。您正在寻找的数据结构是一个有限映射：Map Char Int. 特别看member和insertWith。 toList并fromList从您当前拥有的表示转换为AList，因此即使您坚持使用该表示，您也可以转换Map为该算法的 a 并在最后转换回来。（这将比留在列表中更有效，因为您要进行大量查找，并且有限映射 API 比列表更易于使用）

我将这个问题分为两个阶段：（1）partition根据blist它们是否在地图中，（2）insertWith已经在地图中的元素。然后您可以返回结果映射和另一个分区。

我还将摆脱无意义的假设，例如键是Char-您可以说它们是k满足必要约束的任何类型（对于“键”）（您可以将其放在 a 中Map，这要求它是可Ord擦除的）。您可以使用小写类型变量执行此操作：

import qualified Data.Map as Map

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

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

哦，这个程序在IOmonad 中也没有任何关系。这是纯代码。

于 2013-01-25T06:07:32.703 回答
0

正如@luqui 指出的那样，您描述的操作是纯的，所以我们只是将它定义为纯 Haskell 函数。它可以通过(or )在monad (包括IO) 中使用。fmapdo

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为地图（当心重复！）。然后，扫描 (with scanl) over blist，利用updateLookupWithKey更新counts map，同时为 的每个成员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（您为什么要这样做？）。

于 2013-01-25T10:11:05.297 回答
0

虽然我绝不是 Haskell 专家，但我有部分尝试返回一次操作的结果。也许您可以了解如何将其映射到其余部分以获得您的解决方案。addwhile 很聪明，因为你只想更新 lista 中第一次出现的元素，如果它存在两次，它只会给它加 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)]
于 2013-01-25T06:36:23.513 回答
0 
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 太一无所知了。

于 2013-01-25T06:37:48.957 回答