user737163
user737163

Reputation: 471

Trying to make recursive solution fully functional

I am currently doing a recursive problem and I solved it. Now I want to make the solution fully functional by replacing the for loop with a helper function but I can't quite wrap my head around that. I am pretty sure it is done with a helper function that loops over the list by calling itself recursively and slicing the list after every item but I can't seem to have any luck. Any tips?

def flatten(arr):
    result = []
    for item in arr:
        if type(item) != type([]):
            result = result + [item]
        else:
            result = result + flatten(item)
    return result

print(flatten([1,[[2],3],[[[4]]]]))
##[1,2,3,4]

Upvotes: 0

Views: 73

Answers (2)

Mulan
Mulan

Reputation: 135217

You can use mathematical induction -

  1. if input t is empty, return the base case, []
  2. (induction) t is not empty. if the first element in t is a list, flatten it and combine it with the flattened sub-problem t[1:]
  3. (induction) t is not empty and the first element in t is not a list. return the first element in t and the flattened sub-problem, t[1:]
def flatten(t):
  if not t:
    return []                             # 1
  elif isinstance(t[0], list):
    return flatten(t[0]) + flatten(t[1:]) # 2
  else:
    return [t[0]] + flatten(t[1:])        # 3

print(flatten([1,[[2],3],[[[4]]]]))
[1,2,3,4]

Which is the same as this, using * spread operator -

def flatten(t):
  if not t:
    return []                                   # 1
  elif isinstance(t[0], list):
    return [ *flatten(t[0]), *flatten(t[1:]) ]  # 2
  else:
    return [ t[0], *flatten(t[1:]) ]            # 3

Another option is to describe a new sub-problem in branch 2. Instead of

  1. flatten the first element, t[0], as x
  2. flatten the rest of the list, t[1:], as y
  3. combine, x + y

A different sub-problem could look like this -

  1. combine the first element, t[0], with the rest of the list, t[1:], as x
  2. flatten x
def flatten(t):
  if not t:
    return []                         # 1
  elif isinstance(t[0], list):
    return flatten(t[0] + t[1:])      # 2 <-
  else:
    return [ t[0], *flatten(t[1:]) ]  # 3

Or consider using generators -

def flatten(t):
  if not t:
    return                       # 1
  elif isinstance(t[0], list):
    yield from flatten(t[0])     # 2
    yield from flatten(t[1:])    # 2
  else:
    yield t[0]                   # 3
    yield from flatten(t[1:])    # 3

print(list(flatten([1,[[2],3],[[[4]]]])))
[1,2,3,4]

Or use generic functionals like flatmap -

def reduce(f, init, t):
  if not t:
    return init
  else:
    return reduce(f, f(init, t[0]), t[1:])

def flatmap(f, t):
  return reduce \
    ( lambda r, v: r + f(v)
    , []
    , t
    )

def flatten(t):
  return flatmap \
    ( lambda v: \
        flatten(v) if isinstance(v, list) else [v]
    , t
    )

print(flatten([1,[[2],3],[[[4]]]]))
[1,2,3,4]

Upvotes: 1

user2390182
user2390182

Reputation: 73460

You can make it work along the following lines, using functools.reduce:

from functools import reduce

def reducer(a, b):
    return a + (flatten(b) if isinstance(b, list) else [b])

def flatten(arr):
    return reduce(reducer, arr, [])

>>> flatten([1,[[2],3],[[[4]]]])
[1, 2, 3, 4]

Upvotes: 1

Related Questions