[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