smol projects

length of a nested array

11.11.2023 3 min read

Write a function that returns the total number of non-nested items in a nested array.


def get_length(arr)

This felt like cheating, so I thought maybe I’d try to implement flatten in nim. But no - this wasn’t happening. Nim seems to be quite strict about how variables are typed, which makes it a non-trivial challenge to write something like this. There are some Github issues regarding this here and here, but none of them have made their way to the stdlib yet… And I honestly have no idea what I’m looking at.

So I went back to Crystal. It was moderately difficult to do with generics, but I managed to scrape together something that (seems to) work:

def flat(arr : Array(T)) forall T
  res = [] of T
  arr.each do |e|
    if e.responds_to?(:size)
      res += flat(e)
      res << e

The key thing here is responds_to?. If the element we are looping over responds_to(:size), then we know that we are dealing with an array - which means that we are not done, and need to append the result of recursively calling flat to the current result set. Before this solution, I tried using e.is_a?(T). My thought process was this: we tell Crystal that arr will be of type Array(T). So, if e.is_a?(T), then it cannot be Array(T). But that didn’t work - FWIW, ChatGPT said it maybe had something to do with “incomplete type information at runtime”, whatever that means. Moving on…


[1, [2, [3, 4]]].flat.say; # (1 [2 [3 4]])
[1, [2, [3, 4]]].List.flat.say; # (1 2 [3 4])

Raku doesn’t seem to flatten arrays. It needs a list before it’ll start to flatten, and even then, it’ll only flatten one level. I found this discussion from S/O. An excerpt:

Unfortunately there’s no direct built-in that completely flattens a data structure even when sub-lists are wrapped in item containers.

The built-in flat function can flatten a deeply nested lists of lists just fine.

How to avoid: Use Lists of Lists instead of Arrays of Arrays, if you don’t need the mutability that Array provides.

Again, it turns out that this is harder than expected.

The solution (that I didn’t write):

sub length-of-a-nested-array(@a) {
    my @res = gather @a.deepmap(*.take);

As I understand it - deepmap descends recursively into sublists. From the thread: “…using take as the callback means that gather will collect a flat list of the leaf values.”

O..K… I’ve RTFM, and I have some idea of what gather/take does, but I don’t think I would’ve been able to come up with this on my own.


function lengthOfANestedArray(arr: unknown[]) {
  return arr.flat(Infinity).length;

Welp. Overall, this has been a lot more challenging than I expected. Suffice to say - some things are easier in certain languages than others.

Built with Astro and Tailwind 🚀