列表中出现次数的映射

Question

我正在处理这种类型的列表：

data Elem = Dot | Star

并且我必须打印一个元组列表，有 2 个单位，其中第一个表示列表中 "Star" 序列的长度，第二个列出该序列出现的位置（第一个位置是 1)。可能不使用内置函数。

函数为：

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

编辑：我的想法是：将问题分成两个函数，一个用于查找每个 "Star" 的位置，一个用于列出位置。

编辑2：示例：

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

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

编辑3： http://pastebin.com/uvvXBARL

Answer 1

对于复杂性，我深表歉意，但这项工作：

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

在这个程序中，我有 2 个帮助功能：

1) occ_help，找到 Stars 的所有 [(Int, [Int])] 子序列。例如：

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

将 returns 子序列列表：

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

2) reduce，将这些元素的列表折叠到所需列表示例：

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

将 returns 你的结果：

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

列表中出现次数的映射

Map of number of occurrences in a list

haskell

substring

find-occurrences