Beauty in the Eye of the Spectator

allProductsTimes: aNumber
do: aBlock

       self
             allProductsTimes: aNumber
	     startingAt: 1
	     do: aBlock

allProductsTimes: aNumber
startingAt: anIndex
do: aBlock

       anIndex > self size
       ifTrue: [aBlock value: aNumber]
       ifFalse:
               [self
	             allProductsTimes: aNumber
		     startingAt: anIndex + 1
		     do: aBlock.

	       self
	             allProductsTimes: aNumber * (self at: anIndex)
		     startingAt: anIndex + 1
		     do: aBlock]
powerset :: [a] -> [[a]]
-- returns powerset of given set
powerset []     = [[]]
powerset (x:xs) = concat [ [s, x:s] | s <- powerset xs ]
Main> powerset [2 .. 4]
[[],[2],[3],[2,3],[4],[2,4],[3,4],[2,3,4]]
Main> :t foldl
foldl :: (a -> b -> a) -> a -> [b] -> a
Main> :t foldl (*) 1
foldl (*) 1 :: Num a => [a] -> a

Main> :t product
product :: Num a => [a] -> a
powerset :: [a] -> [[a]]
-- returns powerset of given set
powerset []     = [[]]
powerset (x:xs) = concat [ [s, x:s] | s <- powerset xs ]

allProducts :: Num a => [a] -> [a]
-- returns arithmetic product of each subset of given set
allProducts = map product . powerset
Main> allProducts [2 .. 4]
[1,2,3,6,4,8,12,24]
  • If an initial value is not known, we could (like in the Smalltalk code) choose to take the first element of the set as initial value (requiring the set to contain at least one element):
Main> :t foldl1 (*)
foldl1 (*) :: Num a => [a] -> a
  • The above code works on sets represented as lists. Replacing [a] with Set a => a is left as an exercise to the reader (it will look uglier).

Update 2005-09-28: Powerset Code Explanation

powerset :: [a] -> [[a]]
powerset (x:xs) = concat [ [s, x:s] | s <- powerset xs ]
[ x | x <- gen ]

Update 2005-09-28: MORE POWERSET!

Main> <kbd>take 10 (powerset [1 ..])</kbd>
comments powered by Disqus