CODEWITHSUNDEEP
haskellsubstringfind-occurrences
notdodo
notdodo

Reputation: 149

Map of number of occurrences in a list

I'm working with this type of list:

data Elem = Dot | Star

and I've to print a list of tuples, with 2 units, in which the first indicates the length of a sequence of "Star" in the list and the second lists the locations where this sequence appears (the first position is 1). Possibly without using built in function.

The function is:

occ :: [Elem] -> [(Int, [Int])]

EDIT: My idea is: split the problem in two functions, one for find the position of every "Star", one for lists the locations.

EDIT2: Example:

occ [Dot,Star,Dot,Star,Dot,Star,Star,Star]

[(1,[2,4]), (3,[6])]

EDIT3: http://pastebin.com/uvvXBARL

Upvotes: 0

Views: 401

Answers (1)

Mikhail
Mikhail

Reputation: 445

I apologize for complexity, but this work:

import Data.List
data Elem = Dot | Star
occ :: [Elem] -> [(Int, [Int])]
occ list = reduce (occ_hlp list 1 0 0 [])

-- Help function, which find all subsequence of Stars
occ_hlp [] pos cur_pos cur_len result       | cur_len == 0 = result
                                            | otherwise = ((cur_len, [cur_pos]):result)
occ_hlp (Star:t) pos cur_pos cur_len result | cur_len == 0 = occ_hlp t (pos + 1) pos 1 result
                                            | otherwise = occ_hlp t (pos + 1) cur_pos (cur_len + 1) result
occ_hlp (Dot:t) pos cur_pos cur_len result  | pos == 1 = occ_hlp t (pos + 1) 0 0 result
                                            | otherwise = occ_hlp t (pos + 1) 0 0 ((cur_len, [cur_pos]) : result)

-- Reduce obtained subsequence of Stars with same length                                            
reduce list = filter (\x -> not $ (snd x) == []) 
                 $ [(elem, sort $ foldl (\x y -> x ++ (snd y)) [] (filter (\x -> (fst x) == elem) list)) | elem <- [1..max_len]] 
                     where max_len = maximum $ map (fst) list

In this program i have 2 help functions:

1) occ_help, which find all [(Int, [Int])] subsequence of Stars. For your example:

occ_hlp [Dot,Star,Dot,Star,Dot,Star,Star,Star] 1 0 0 []

will returns list of subsequence:

[(3,[6]),(1,[4]),(1,[2])]

2) reduce, which folds list of these elements to required list Example:

reduce [(3,[6]),(1,[4]),(1,[2])]

will returns your result:

[(1,[2,4]),(3,[6])]

Upvotes: 1

Related Questions