[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
             ) (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