[Python-ideas] Haskell envy

Nestor nestornissen at gmail.com
Mon Apr 23 03:07:36 CEST 2012


The other day a colleague of mine submitted this challenge taken from
some website to us coworkers:

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.

Examples:
5,7,16,1,2
3,5,-1,8,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)))
    for one_comb in my_comb:
        if sum(one_comb) == biggest:
            return True, one_comb
    return False


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


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).



More information about the Python-ideas mailing list