1

我编写了下面的代码来列出列表列表的子序列频率（结果包括子序列和出现子序列的列表的索引）。有没有人有任何建议如何使它更简洁和/或高效？

样本输出：

*Main> combFreq [[1,2,3,5,7,8],[2,3,5,6,7],[3,5,7,9],[1,2,3,7, 9],[3,5,7,10]]
[([3,5],[0,1,2,4]),([2,3],[0,1,3]),([ 3,5,7],[0,2,4]),([5,7],[0,2,4]),([2,3,5],[0,1]),([ 1,2],[0,3]),([1,2,3],[0,3]),([7,9],[2,3])]

import Data.List
import Data.Function (on)

--[[1,2,3,5,7,8],[2,3,5,6,7],[3,5,7,9],[1,2,3,7,9],[3,5,7,10]]

tupleCat x y = (fst x, sort $ nub $ snd x ++ snd y)
isInResult x result = case lookup x result of
                        Just a  -> [a]
                        Nothing -> []

sInt xs = concat $ sInt' (csubs xs) 0 (length xs) where
    csubs = map (filter (not . null) . concatMap inits . tails)
    sInt' []     _     _       = []
    sInt' (x:xs) count origLen = 
        let result = (zip (zip (replicate (length xs) count) [count+1..origLen]) 
                 $ map (\y -> intersect x y) xs)
        in concatMap (\x -> let a = fst x in map (\y -> (y,a)) (snd x))
                 result : sInt' xs (count + 1) origLen

concatResults [] result     = result 
concatResults (x:xs) result = 
    let match = isInResult (fst x) result 
        newX  = (fst x, [fst $ snd x, snd $ snd x])
    in  if not (null match)
        then let match'    = (fst x, head match)
                 newResult = deleteBy (\x -> (==match')) match' result
             in concatResults xs (tupleCat match' newX : newResult)
        else concatResults xs (newX : result)

combFreq xs =
  filter (\x -> length (fst x) > 1)
  $ reverse $ sortBy (compare `on` (length . snd)) $ concatResults (sInt xs) []
4

2 回答 2

2

这就是我将如何去做。我没有比较它的性能，它肯定是幼稚的。它枚举每个列表的所有连续子序列并将它们收集到一个Map. 它应该满足您更简洁的要求。

import Data.List as L
import Data.Map (Map)
import qualified Data.Map as M

nonEmptySubs :: [a] -> [[a]]
nonEmptySubs = filter (not . null)
             . concatMap tails
             . inits

makePairs :: (a -> [a]) -> [a] -> [(a, Int)]
makePairs f xs = concat $ zipWith app xs [0 .. ]
    where app y i = zip (f y) (repeat i)

results :: (Ord a) => [[a]] -> Map [a] [Int]
results =
    let ins acc (seq, ind) = M.insertWith (++) seq [ind] acc
        -- Insert the index at the given sequence as a singleton list
    in foldl' ins M.empty . makePairs nonEmptySubs

combFreq :: (Ord a) => [[a]] -> [([a], [Int])]
combFreq = filter (not . null . drop 1 . snd) -- Keep subseqs with more than 1 match
         . filter (not . null . drop 1 . fst) -- keep subseqs longer than 1
         . M.toList
         . results

请注意，此版本将给出相同的定性结果，但顺序不同。

我最大的建议是更多地分解事物并利用一些标准库中的内容来完成繁琐的工作。请注意，我们可以将大量工作分解为单独的阶段，然后组合这些阶段以获得最终功能。

于 2013-03-05T16:37:15.040 回答
0

如果您的所有列表都在增加（就像在您的示例中一样），则以下内容应该有效（不是美女，因为我是 Haskell 新手；非常欢迎对如何改进发表评论）：

import Control.Arrow (first, second)

compFreq ls = cF [] [] ls
  where cF rs cs ls | all null ls = rs
                    | otherwise   = cF (rs++rs') (cs'' ++ c ++ cs') ls'
          where m = minimum $ map head $ filter (not . null) ls
                ls' = map (\l -> if null l || m < head l then l
                                                         else tail l) ls
                is = map snd $ filter ((==m) . head . fst) $ filter (not . null . fst) $ zip ls [0,1..]
                c = if atLeastTwo is then [([m], is)] else []
                fs = filter (\(vs, is') -> atLeastTwo $ combine is is') cs
                cs' = map (\(vs, is') -> (vs++[m], combine is is')) fs
                cs'' = map (second (filter (not . (`elem` is)))) cs
                rs' = filter ok cs'
                combine _ [] = []
                combine [] _ = []
                combine (i:is) (i':is') | i<i' = combine is (i':is')
                                        | i>i' = combine (i:is) is'
                                        | i==i' = i:combine is is'
                atLeastTwo = not . null . drop 1
                ok (js, ts) = atLeastTwo js && atLeastTwo ts

这个想法是通过始终查看最小值 m 来处理列表，将其从所有列表中删除以获得 ls'。索引列表告诉 m 被删除的位置。内部工作函数 cF 有两个额外的参数：到现在的结果列表 rs 和当前子序列的列表 cs。如果最小值至少出现两次，则最小值开始一个新的子序列 c。cs'是以m结尾的子序列，cs''是没有m的子序列。新结果 rs' 都包含 m 作为最后一个元素。

您的示例的输出是

[([1,2],[0,3]),([2,3],[0,1,3]),([1,2,3],[0,3]),([3,5],[0,1,2,4]),([2,3,5],[0,1]),([5,7],[0,2,4]),([3,5,7],[0,2,4]),([7,9],[2,3])]
于 2013-03-05T18:37:13.890 回答