haskell - 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値に1を追加し、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モナドで発生しています。

私が試したこと：

1. mapMと再帰ヘルパー関数を使用します。私は両方を見てきました：

   AListのすべての要素がbListのすべての要素に対してチェックされます--mapM（myHelpF1 alist）blistおよびBListのすべての要素がAListのすべての要素に対してチェックされます– mapM（myHelpF2 alist）blist

2. 両方のリストを関数に渡し、複雑なif / then / else＆helper関数呼び出しを使用します（Haskellに反復を強制しているように感じます;厄介な複雑なコード、正しくないと感じます）。

3. フィルタ、AList要素の文字値およびBlistを使用して、Boolの3番目のリストを作成し、True値の数をカウントすることを考えました。Int値を更新します。次に、BListのフィルターを使用して、……（ここでも、Haskellにあまり似ていない、正しく感じられない）BList要素を削除します。

私が問題について知っていると思うこと：

解決策は些細なことを超えている可能性があります。そんなに経験豊富なハスケラーは、彼らが彼らの反応をタイプするとき、彼らの息の下で「なんて初心者」とつぶやくでしょう。

任意のポインタをいただければ幸いです。（つぶやく…。）

Answer 1

いくつかの指針：

[(Char, Int)]「AList」には使用しないでください。探しているデータ構造は有限マップです: Map Char Int. 特に と を見てmemberくださいinsertWith。 toListとfromList、現在の for の表現から変換するためAList、その表現に行き詰った場合でも、Mapこのアルゴリズムの に変換し、最後に元に戻すことができます。(非常に多くのルックアップを行うため、これはリストにとどまるよりも効率的であり、有限マップ API はリストよりも操作が簡単です)

私はこの問題に 2 つのフェーズとしてアプローチします。(1)partition要素がblistマップ内にあるかどうかによって、(2)insertWith既にマップ内にある要素を取り出します。次に、結果のマップと他のパーティションを返すことができます。

また、キーが であるなどの無意味な仮定を取り除きます。必要な制約 ( に入れることができ、それがerableであることを必要とする) を満たすChar任意の型(「キー」の場合) であると言うことができます。 ）。小文字の型変数でこれを行います。kMapOrd

import qualified Data.Map as Map

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

アルゴリズムをより一般的に書くと、必要のない仮定を使用しないようになるため、バグを発見するのに役立ちます。

ああ、このプログラムもIOモナドの中にいることに意味はありません。これは純粋なコードです。

Answer 2

@luquiが指摘しているように、あなたが説明する操作は純粋なので、純粋なHaskell関数として定義するだけです。（または）を使用して、モナド（を含む）内で使用できます。IOfmapdo

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

テスト走行：

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

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

---

編集：あなたはおそらくそれを逆にしたいと思うでしょう、blist更新しながら転がり、結果（私のコードでalist）の要素を生成する（または生成しない）。そうすれば、アルゴリズムは長い入力ストリームに対してよりローカルな方法で動作します（あなたがそれを言わなかったとしても、あなたが長いと仮定します）。上で書いたように、スペースの問題があり、入力ストリームを数回消費します。イラスト、思考の糧としてそのままにしておきます。blistb4blistblist

したがって、2番目のルートに進むことにした場合は、最初にalistマップに変換します（重複に注意してください！）。次に、をスキャンして（を使用してscanl）、カウントマップを更新すると同時に、の各メンバーについて、出力するかどうかを1つずつ決定します。したがって、アキュムレータのタイプは、要素タイプ（）である必要があります。blistupdateLookupWithKeyblist(Map a Int, Maybe a)ablist :: [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

Answer 3

私は決して Haskell の専門家ではありませんが、操作の結果を 1 回返す部分的な試みがあります。解決策を得るために、それを残りの上にマッピングする方法を見つけることができるかもしれません。lista 内の要素の最初の出現のみを更新したいので、addwhile は賢いです。要素が 2 回存在する場合は、それに 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)]

Answer 4

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 について無知すぎてそれを知ることができません。