Фильтрация списка единообразных списков

Question

Я пытаюсь найти решение этой проблемы в течение нескольких дней и до того, как я слишком расстроился, я решил обратиться за помощью.

У меня есть список единообразных списков, например. [[2], [2, 2], [3], [3, 3] [3, 3, 3], [5]], и я хочу применить фильтр так, чтобы остались только списки, которые не являются подмножествами любого из остальных списков.

Это было сложное предложение. В основном я нужна функция f для которой

f [[2], [2, 2], [3], [3, 3] [3, 3, 3], [5]] 

приводит

[[2, 2], [3, 3, 3], [5]] 

Я надеюсь, что я сделал себе ясно. Если нет, помогите мне уточнить!

Answer 1

Похоже, что вы хотите:

import Data.List 
import Data.Function 

f :: (Ord a) => [[a]] -> [[a]] 
f = map (maximumBy (compare `on` length)) . groupBy ((==) `on` head) . sortBy (compare `on` head) 

Мы просто группа списки вместе по голове и выбрать максимум каждого.

Если я не понял вас неправильно, вы хотите выбрать список, который не является подсписком других списков, который по сути является самым длинным списком для каждой группы.

Answer 2

Предполагая, что ваши списки все обмундирование, в том, что ни один список не содержит два различных элемента (т.е. [2, 3]), вы могли бы вместо того, чтобы поставить этот вопрос с точки зрения длины:

> import Control.Arrow 
> -- Equivalent to `\x -> (head x, length x)` 
> :t head &&& length 
head &&& length :: [a] -> (a, Int) 
> (head &&& length) [2, 2, 2] 
(2, 3) 
> 
> let myData = <what you have above> 
> map (head &&& length) myData 
[(2, 1), (2, 2), (3, 1), (3, 3), (5, 1)] 

Теперь вы можете сгруппировать их по первому элемент

> import Data.List 
> :t groupBy 
groupBy :: (a -> a -> Bool) -> [a] -> [[a]] 
> import Data.Function 
> :t on 
on :: (b -> b -> c) -> (a -> b) -> a -> a -> c 
> :t on (==) fst 
on (==) fst :: Eq b => (b, b1) -> (b, b1) -> Bool 
> :t groupBy (on (==) fst) 
groupBy (on (==) fst) :: Eq b -> [(b, b1)] -> [[(b, b1)]] 
> groupBy (on (==) fst) $ map (head &&& length) myData 
[[(2,1),(2,2)],[(3,1),(3,2),(3,3)],[(5,1)]] 

Затем вы можете выбрать срок с крупнейшим snd:

> :t maximumBy 
maximumBy :: (a -> a -> Ordering) -> [a] -> a 
> import Data.Ord 
> :t comparing 
comparing :: Ord a => (b -> a) -> b -> b -> Ordering 
> :t comparing snd 
comparing snd :: Ord a => (a1, a) -> (a1, a) -> Ordering 
> :t maximumBy (comparing snd) 
maximumBy (comparing snd) :: Ord a -> [(a1, a)] -> (a1, a) 
> :t map (maximumBy (comparing snd)) 
map (maximumBy (comparing snd)) :: Ord a => [[(a1, a)]] -> [(a1, a)] 
> map (maximumBy (comparing snd)) $ groupBy (on (==) fst) $ map (head &&& length) myData 
[(2, 2), (3, 3), (5, 1)] 

А теперь, если вы хотите, вы можете преобразовать его обратно в списки с помощью replicate:

> map (uncurry (flip replicate)) $ map (maximumBy (comparing snd)) $ groupBy (on (==) fst) $ map (head &&& length) myData 
[[2, 2], [3, 3, 3], [5]] 

---

Последняя функция будет выглядеть

import Data.List (groupBy, maximumBy) 
import Data.Ord (comparing) 
import Data.Function (on) 
import Control.Arrow ((&&&)) 

biggestUnique :: [[Int]] -> [[Int]] 
biggestUnique 
    = map  (uncurry (flip replicate)) -- Convert back to lists 
    . map  (maximumBy (comparing snd)) -- Select by the maximum length 
    . groupBy ((==) `on` fst)    -- Group by the element value 
    . map  (head &&& length)    -- Reformulate in terms of length 

И вы можете сжать map сек в один, но я думаю, что он делает его менее читаемым.

ВНИМАНИЕ: Это не будет работать должным образом, если ваши элементы не уникальны в каждом подсписке.

Answer 3

Ни один список не является подходящим подсписком пустого списка. Пустой список является подходящим подсписком для каждого непустого списка.

import Data.List (delete) 

sublist :: Eq a => [a] -> [a] -> Bool 
sublist _  []    = False 
sublist []  _    = True 
sublist (x : xs) ys | x `elem` ys = sublist xs (delete x ys) 
        | otherwise = False 

С none pred = not . any pred и без ограничения: Ord

superlists :: Eq a => [[a]] -> [[a]] 
superlists xss = filter (\ xs -> none (xs `sublist`) xss) xss 

смысл

superlists [[1,2,2],[2,2,1],[1],[]] == [[1,2,2],[2,2,1]] 

и

superlists [[2],[2,2],[3],[3,3],[3,3,3],[5]] == [[2,2],[3,3,3],[5]] 

---

Denotationally равноценной альтернативой sublist:

elemDelete :: Eq a => a -> [a] -> (Bool, [a]) 
elemDelete _ []     = (False, []) 
elemDelete y (x : xs) | x == y = (True, xs) 
         | otherwise = let (b, zs) = elemDelete y xs 
            in (b, x : zs) 

sublist :: Eq a => [a] -> [a] -> Bool 
sublist _  [] = False 
sublist []  _ = True 
sublist (x : xs) ys = let (b, dys) = elemDelete x ys 
         in if b then sublist xs dys 
           else False 

Но elemDelete y xs на самом деле менее эффективна, чем (elem y xs, delete y xs).