CODEWITHSUNDEEP
listhaskell
Alessandro
Alessandro

Reputation: 75

How can I count occurencies of each string in a list with position of each of them?

I need to make something like this:

func ["a","bb","c","aa","bb","c"] ⟼
  [("a",[0]), ("bb",[1,4]),("c",[2,5]),("aa",3)]

with this function:

func :: [String] -> [(String, [Int])]

I was thinking something like this:

func :: [String] -> [(String, [Int])]
func (xs) = func1 (reverse xs)
  where
    func1 [] = []
    func1 (x:xs)
      | notElem x xs = func1 (xs) ++ [(x, [0])]
      | otherwise = func1 (xs)

0 is just a placeholder, how can I put the indices in that position?

Upvotes: 0

Views: 97

Answers (4)

user5772563
user5772563

Reputation:

I don't know if this will help but this was what I did to solve the problem

zipPos :: [String] -> [(String, Int)]
zipPos xs = zip xs [0..]

singleHead :: ([String], [Int]) -> (String, [Int])
singleHead (x,y) = (head x, y)

filterFstTuple :: (String -> String -> Bool) -> [(String, Int)] -> [(String, Int)]
filterFstTuple _ [] = []
filterFstTuple con xss@(x:_) = filter (con (fst x).fst) xss

getPos :: [(String, Int)] -> [(String, [Int])]
getPos [] = []
getPos xss = singleHead (unzip (filterFstTuple (==) xss)) : getPos  (filterFstTuple (/=) xss)

main :: IO()
main = print . getPos $ zipPos ["a", "b", "c", "c", "d", "a"]

Upvotes: 0

chepner
chepner

Reputation: 531055

Here's an example of how to use Data.Map to solve this. (I'm not sure if there's a better way to handle the zipWith.)

import Data.Map (Map)
import qualified Data.Map as Map

func :: [String] -> [(String, [Int])]
func xs = Map.toList .                          -- [("a", [0]), ("bb", [1,4]), ...]
           (Map.map reverse) .                   -- fromList [("a", [0]), ("bb", [1,4]), ...]
           (Map.fromListWith (++)) $             -- fromList [("a", [0]), ("bb", [4,1]), ...]
           zipWith (\c i -> (c, [i])) xs [0..]   -- [("a", [0]), ("bb", [1]), ...]

This starts with a list of tuples pairing each string to a singleton list of its position in the input, then builds a map where each key is mapped to an accumulated list of positions. The accumulated positions are built up in reverse order, which Map.map reverse fixes, then the desired list is extracted from the map.

Here is an optimized version, courtesy of dfeuer.

func = map (\(a,b) -> (a, reverse b)) .
       Map.toList .
       Map.fromListWith (++) .
       zipWith (\i c -> (c, [i])) [0..]

Upvotes: 1

Levi Pearson
Levi Pearson

Reputation: 4984

In order to have the index, your helper function just needs an extra parameter that you pass a 0 to initially and increment at each recursive call. You may have to change when you call reverse in order to get the indices in the right order, though!

A second part you'll have to consider is the best way to manage the list of pairs you're creating as output. Lists of pairs like this are sometimes called "association lists" and there is a lookup function in the Prelude that you can use to get the value associated with a key in such a structure. You might study that function and write a update helper to go with it in order to update the value at an existing key.

There is another general approach to problems, however, which @Chad Gilbert is hinting at in his answer. Instead of using recursion directly, you can often define your solution as a composition of transformation and combining operations over the problem structure. Solutions in this form often combine mapping, filtering, zipping, and folding. I would recommend practicing with both kinds of solutions.

Upvotes: 0

Chad Gilbert
Chad Gilbert

Reputation: 36375

zip [0..] xs will give you a list of tuples where the first item is the zero-based index and the second item is the string at that index.

Upvotes: 1

Related Questions