Reputation: 471
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
Reputation: 135217
You can use mathematical induction -
t
is empty, return the base case, []
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:]
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
t[0]
, as x
t[1:]
, as y
x + y
A different sub-problem could look like this -
t[0]
, with the rest of the list, t[1:]
, as x
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
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