Power set: Difference between revisions
→{{header|Haskell}}: Crazy implementation with only set ops
(→{{header|Haskell}}: Crazy implementation with only set ops) |
|||
Line 800:
<tt>listPowerset</tt> describes the result as all possible (using the list monad) filterings (using <tt>filterM</tt>) of the input list, regardless (using <tt>const</tt>) of each item's value. <tt>powerset</tt> simply converts the input and output from lists to sets.
'''Alternate Solution
<lang Haskell>powerset [] = [[]]
powerset (head:tail) = acc ++ map (head:) acc where acc = powerset tail</lang>
Line 816:
Prelude Data.List> subsequences [1,2,3]
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
'''Alternate solution'''
A method using only set operations and set mapping is also possible. Ideally, <code>Set</code> would be defined as a Monad, but that's impossible given the constraint that the type in inputs to Set.map (and a few other functions) be ordered.
<lang Haskell>import qualified Data.Set as Set
type Set=Set.Set
unionAll :: (Ord a) => Set (Set a) -> Set a
unionAll = Set.fold Set.union Set.empty
--slift is the analogue of lift2A for sets.
slift :: (Ord a, Ord b, Ord c) => (a->b->c) -> Set a -> Set b -> Set c
slift f s0 s1 = unionAll (Set.map (\e->Set.map (f e) s1) s0)
--a -> {{},{a}}
makeSet :: (Ord a) => a -> Set (Set a)
makeSet = (Set.insert Set.empty) . Set.singleton.Set.singleton
powerSet :: (Ord a) => Set a -> Set (Set a)
powerSet = (Set.fold (slift Set.union) (Set.singleton Set.empty)) . Set.map makeSet</lang>
Usage:
<lang Haskell>
Prelude> powerSet s
fromList [fromList [], fromList [1], fromList [1,2], fromList [1,2,3], fromList [1,3], fromList [2], fromList [2,3], fromList [3]]</lang>
=={{header|Icon}} and {{header|Unicon}}==
| |||