0

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

4

1 回答 1

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，查找所有 [(Int, [Int])] 星子序列。对于您的示例：

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

将返回子序列列表：

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

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

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

将返回您的结果：

[(1,[2,4]),(3,[6])]
于 2015-03-20T21:51:12.650 回答