Final Exam 2011 Problem 1

[Erwin Magnaye]

How would you implement the reduce function using functional programming (using functions, recursion, if statements, but no loops)?

reduce (f,[a,b,c,d]) returns f(f(f(a,b),c),d)

def reduce(f,ls):

...

[Erwin Magnaye]

Here is a link to the exam.

http://courses.skule.ca/exams/bulk/20119/csc326f_2011_exam.PDF

[aya]

here is my solution:

def reduce2(f, input):
    return reduce(lambda a, b: f(a, b), input)

[Mustafa]

Hmmmmm, i don't think you can do that. You can't use the function reduce when you are being asked to implement it. 

I think this is more fitting. 

For functional: 

def reduce(f,ls):

    out = f(ls[0],ls[1])

    ls.pop(0), ls.pop(0)

    

    def recurse(out):

         if(len(ls) == 1):

               out = f(out,ls[0])

               return out

          else: 

              out = f(out,ls.pop(0))

              return recurse(out)

     return recurse(out)

            

For Imperative:

def reduce(f,ls):

    out = f(ls[0],ls[1])

    ls.pop(0), ls.pop(0)

    for t in ls:

         out = f(out, t)

   return out

[Mustafa]

I'm sure there are better solutions. 

[Wesley May]

Hmmmm did you just implement reduce with reduce? XD

[Mustafa]

hahahahahah, i'll remember that for tomorrow. 

[Vinh Hoang]

This is mine

def reduce(f, ls):
    if len(ls) == 2:
        return f(ls[0], ls[1])
    elif len(ls) > 2:
        return reduce(f, [f(ls[0], ls[1])] + ls[2:])
    else:
        return None

[Sheema Khan]

Mine:

def helper(f,ans,ls):
    if len(ls) <  2: return f(ans,ls[0])
    return helper(f,f(ans,ls[0]),ls[1:])
                     
def reduce(f,ans,ls):
    ans = f(ls[0],ls[1])
    return helper(f, ans,ls[2:])

[Sheema Khan]

I assumed that I can only use if and not if-else statements

[Vinh Hoang]

I think you can... since it's trivial to modify if else to sequences of if

[Wesley May]

Agreed