Trying to make recursive solution fully functional

Question

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]

@IgnacioAlorre I want to implement it myself with my own functions so I understand everything better. — user737163, Jan 01 '21 at 20:51
@Barmar I would agree that this is a poor duplicate as it answers a question the OP quite clearly shows he has already answered. — user2390182, Jan 01 '21 at 21:00
I don't know but I almost solve this with `print(list(map(lambda item: result + [item] if type(item) != type([]) else result + flatten(item), arr)))` and then I realized the lambda needs to call itself. I'm not smart enough to understand the techniques for getting a lambda to call itself https://stackoverflow.com/questions/481692/can-a-lambda-function-call-itself-recursively-in-python — MatthewMartin, Jan 01 '21 at 21:01
I did read it fully. Most of the answers in that question use a loop, but one of them is functional as he requests. @user737163 — Barmar, Jan 01 '21 at 21:01
@user737163 My comment about flattening only one level was in response to someone else's comment. — Barmar, Jan 01 '21 at 21:03
The solution linked is indeed functional, you are correct @Barmar. — user737163, Jan 01 '21 at 21:07
@MatthewMartin [recursive lambda](https://stackoverflow.com/a/43195580/633183) or _anonymous recursion_ is not as challenging as you might think! Such a technique makes recursion possible even where recursion by name is not supported. Note, the `x => ...` arrows functions from JavaScript are equivalent to Python's `lambda x: ...` functions, — Mulan, Jan 01 '21 at 21:58

user2390182 · Answer 1 · 2021-01-01T21:14:50.957

1

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]

edited Jan 01 '21 at 21:14

answered Jan 01 '21 at 21:07

user2390182

72,016
6
67
89

Mulan · Accepted Answer · 2021-01-01T21:36:44.217

You can use mathematical induction -

if input t is empty, return the base case, []
(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:]
(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

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

A different sub-problem could look like this -

combine the first element, t[0], with the rest of the list, t[1:], as x
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]

Trying to make recursive solution fully functional

2 Answers2