Flatten list

# Elixir, functional (one understandable, and one fast version)
defmodule Flat do
    # Easy to read, preferred for small input. O(length*depth)
    def flatten([[a]]), do: flatten([a])
    def flatten([a]), do: [a]    
    def flatten([a|bs]), do: flatten(a) ++ flatten(bs)    

    # Linear time, a bit harder to read if you're not used to 
    # high-performant functional programming. O(length+depth)
    def flatfast(a), do: reverse flatfast(a, [])
    def flatfast([], r), do: r
    def flatfast([a|as], r), do: flatfast(as, flatfast(a, r))
    def flatfast(a, r), do: [a|r]    
        
    # Reverse a (linked-)list in linear time.
    def reverse(a), do: reverse(a, [])
    def reverse([], b), do: b
    def reverse([a|as], b), do: reverse as, [a|b]
end
        
IO.inspect Flat.flatten([[[[1]],[2]],[3],4])
IO.inspect Flat.flatfast([[[[1]],[2]],[3],4])


# Python, imperative (with a walker)
def flatten(a):
    """ Flatten a list in linear time. """
    def walk(a, res):
        """
        Walk walks over the nested lists as if it was a tree,
        putting all items it finds in `res`.
        """
        if isinstance(a, list):
            for item in a:
                walk(item, res)
        else:
            res += [a]

    res = []
    walk(a, res)
    return res

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