[Python-ideas] Haskell envy
Terry Reedy
tjreedy at udel.edu
Mon Apr 23 04:55:49 CEST 2012
On 4/22/2012 9:07 PM, Nestor wrote:
> The other day a colleague of mine submitted this challenge taken from
> some website to us coworkers:
This is more of a python-list post than a python-ideas post.
So is my response.
> Have the function ArrayAddition(arr) take the array of numbers stored
> in arr and print true if any combination of numbers in the array can
> be added up to equal the largest number in the array, otherwise print
> false. For example: if arr contains [4, 6, 23, 10, 1, 3] the output
> should print true because 4 + 6 + 10 + 3 = 23. The array will not be
> empty, will not contain all the same elements, and may contain
> negative numbers.
Since the order of the numbers is arbitrary and irrelevant to the
problem, it should be formulated in term of a set of numbers.
Non-empty means that max(set) exists.
No duplicates means that max(set) is unique and there is no question of
whether to remove one or all copies.
> Examples:
> 5,7,16,1,2
False (5+7+1+2 == 15)
> 3,5,-1,8,12
True (8+5-1 == 12)
> I proposed this solution:
>
> from itertools import combinations, chain
> def array_test(arr):
> biggest = max(arr)
> arr.remove(biggest
> my_comb = chain(*(combinations(arr,i) for i in range(1,len(arr)+1)))
I believe the above works for sets as well as lists.
> for one_comb in my_comb:
> if sum(one_comb) == biggest:
> return True, one_comb
> return False
The above is must clearer to me than the Haskell (or my equivalent)
below, and I suspect that would be true even if I really knew Haskell.
If you want something more like the Haskell version, try
return any(filter(x == biggest, map(sum, my_comb)))
To make it even more like a one-liner, replace my_comb with its expression.
> But then somebody else submitted this Haskell solution:
>
> import Data.List
> f :: (Ord a,Num a) => [a] -> Bool
> f lst = (\y -> elem y $ map sum $ subsequences $ [ x | x<- lst, x /=
> y ]) $ maximum lst
If you really want one logical line that I believe matches the above ;-)
def sum_to_max(numbers):
return (
(lambda num_max:
(lambda nums:
any(filter(lambda n: n == num_max, map(sum,
chain(*(combinations(nums,i) for i in
range(1,len(nums)+1))))))
) (numbers - {num_max})
# because numbers.remove(num_max)is None
) (max(numbers))
)
print(sum_to_max({5,7,16,1,2}) == False,
sum_to_max({3,5,-1,8,12}) == True)
# sets because of numbers - {num_max}
True, True
Comment 1: debugging nested expressions is harder than debugging a
sequence of statements because cannot insert print statements.
Comment 2: the function should really return an iterator that yields the
sets that add to the max. Then the user can decide whether or not to
collapse the information to True/False and stop after the first.
> I wonder if we should add a subsequences function to itertools or make
> the "r" parameter of combinations optional to return all combinations
> up to len(iterable).
I think not. The goal of itertools is to provide basic iterators that
can be combined to produce specific iterators, just as you did.
--
Terry Jan Reedy
More information about the Python-ideas
mailing list