List processing in Haskell

A few pointers:

Don't use [(Char, Int)] for "AList". The data structure you are looking for is a finite map: Map Char Int. Particularly look at member and insertWith. toList and fromList convert from the representation you currently have for AList, so even if you are stuck with that representation, you can convert to a Map for this algorithm and convert back at the end. (This will be more efficient than staying in a list because you are doing so many lookups, and the finite map API is easier to work with than lists)

I'd approach the problem as two phases: (1) partition out the elements of blist by whether they are in the map, (2) insertWith the elements which are already in the map. Then you can return the resulting map and the other partition.

I would also get rid of the meaningless assumptions such as that keys are Char -- you can just say they are any type k (for "key") that satisfies the necessary constraints (that you can put it in a Map, which requires that it is Orderable). You do this with lowercase type variables:

import qualified Data.Map as Map sieveList :: (Ord k) => Map.Map k Int -> [k] -> (Map.Map k Int, [k]) 

Writing algorithms in greater generality helps catch bugs, because it makes sure that you don't use any assumptions you don't need.

Oh, also this program has no business being in the IO monad. This is pure code.

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

Probably an important disclaimer: I'm rusty at Haskell to the point of ineptness, but as a relaxing midnight exercise I wrote this thing. It should do what you want, although it doesn't return a BList. With a bit of modification, you can get it to return an (AList,BList) tuple, but methinks you'd be better off using an imperative language if that kind of manipulation is required.

Alternately, there's an elegant solution and I'm too ignorant of Haskell to know it.

While I am by no means a Haskell expert, I have a partial attempt that returns that result of an operation once. Maybe you can find out how to map it over the rest to get your solution. The addwhile is clever, since you only want to update the first occurrence of an element in lista, if it exists twice, it will just add 0 to it. Code critiques are more than welcome.

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 operation you describe is pure, as @luqui points out, so we just define it as a pure Haskell function. It can be used inside a monad (including IO) by means of fmap (or do).

import Data.List combine alist blist = (reverse a, b4) where 

First we sort and count the B list:

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

We need the import for group and sort to be available. Next, we roll along the alist and do our thing:

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

Now pick, as used, must be

 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) 

Of course pick performs a linear search, so if performance (speed) becomes a problem, b should be changed to allow for binary search (tree etc, like Map). The calculation of b4 which is filter (`elem` b3) blist is another potential performance problem with its repeated checks for presence in b3. Again, checking for presence in trees is faster than in lists, in general.

Test run:

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

edit: you probably want it the other way around, rolling along the blist while updating the alist and producing (or not) the elements of blist in the result (b4 in my code). That way the algorithm will operate in a more local manner on long input streams (that assuming your blist is long, though you didn't say that). As written above, it will have a space problem, consuming the input stream blist several times over. I'll keep it as is as an illustration, a food for thought.

So if you decide to go the 2nd route, first convert your alist into a Map (beware the duplicates!). Then, scanning (with scanl) over blist, make use of updateLookupWithKey to update the counts map and at the same time decide for each member of blist, one by one, whether to output it or not. The type of the accumulator will thus have to be (Map a Int, Maybe a), with a your element type (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 

You will have to combine the toList last_counts with the original alist if you have to preserve the old duplicates there (why would you?).