Project

General

Profile

Statistics
| Branch: | Revision:

cool / playground.hs @ master

History | View | Annotate | Download (1.42 KB)

1

    
2
import Control.Monad
3
import Data.List
4
import System.IO
5

    
6
-- some example functions which will be adapted to ocaml
7

    
8
--                 mutliset  -> disjoint subset
9
--                 of sets      /   / .... all those maximal ones
10
--                 |   |       |   | /
11
maxdisj :: Eq a => [[a]]   -> [[[a]]]
12
maxdisj = killsubsets . maxdisj' []
13

    
14
-- test it with:
15
-- flip (>>=) (return . length) $  mapM putStrLn $ map show $ maxdisj [[1,2],[2,3],[3,4]]
16
--
17
killsubsets :: Eq a => [[[a]]] -> [[[a]]]
18
killsubsets ccc = filter (\m -> not (any (\cc -> m `subset` cc) ccc)) ccc
19

    
20
subset :: Eq a => [a] -> [a] -> Bool
21
subset a b = (all (`elem` b) a) && ((length a) < (length b))
22

    
23

    
24
--   generate all disjoint subsets...
25
maxdisj' :: Eq a => [[a]] -> [[a]]   -> [[[a]]]
26
maxdisj' pool (x:xs) = oth2 -- extendable ++ maximal
27
  where oth = maxdisj' (x:pool) xs
28
        oth2 = oth ++ (map (x:) $ filter (all (disjoint x)) oth)
29
maxdisj' _ [] = [[]]
30

    
31
-- old helper functions:
32
        --(maximal,nonmaximal) = partition isMaximal oth2
33
        --isMaximal cc = let sups = filter (cc `subset`) oth2
34
        --               in all (\p -> ((not . compatible p cc)
35
        --                       `or`
36
        --                       (flip all sups (not . compatible p)))) pool
37
        --subset a b = all (`elem` a) b `and` (length a) < (length b)
38
        --compatible x cc = all (disjoint x) cc
39

    
40
disjoint :: Eq a => [a] -> [a] -> Bool
41
disjoint x = all (not . flip elem x)
42