Counting elements in recursive type alias lists

Question

Working from the recursive type alias hints in the elm-compiler repository, one solution yields a type signature of:

type alias Comment =
  { message : String
  , upvotes : Int
  , downvotes : Int
  , responses : Maybe Responses
  }

type Responses = Responses (List Comment)

(where responses has been extended to type Maybe Responses here to allow an empty response list).

I'm interested in counting the number of elements in such a list, although my current solution seems to be far more complex than needed.

count : List Comment -> Int
count comments =
    let
        responses =
            List.concatMap (\c -> flatList c) comments
    in
    List.length responses


flatList : Comment -> List Comment
flatList root =
    let
        rest =
            case root.children of
                Just responseList ->
                    List.concatMap (\child -> flatList child) <| unwrapResponses responseList
                Nothing ->
                    []
    in
    root :: rest

unwrapResponses : Responses -> List Comment
unwrapResponses responses =
    case responses of
        Responses comments ->
            comments

Effectively, this unwraps each Responses sublist and recursively flattens it. Then, for each of the parent Comments we concatenate each of the flat Responses lists together and finally get the length of this list.

Since I have no use for this flattened list, I would much prefer to just count each List.length as I recurs through the list, then either fold or sum the result (or, use some other method of retrieving the total element count). However, I'm unsure how generate such a solution without returning the flatList results.

Answer 1

It sounds like you need a specialized fold function for comments. Folding is the idea of visiting every element in a structure with a function that accepts the element and some kind of accumulator value so that you can keep some state from step to step.

Side note: I would recommend you define the Comment responses as Responses instead of Maybe Responses since an empty list and Nothing really represent the same thing.

You could define a foldl for a list of Comments like this:

foldl : (Comment -> b -> b) -> b -> List Comment -> b
foldl f =
    List.foldl
        (\c acc ->
            case c.responses of
                Responses responses ->
                    foldl f (f c acc) responses
        )

That means it will first visit the comment node with your function, then all children left to right, accumulating the results along the way.

To use it to determine the length, you simply ignore the comment and increment a counter along the way:

length : List Comment
length =
    foldl (\_ acc -> acc + 1) 0

You'll see that the definition of List.length uses the same idea of foldl for its implementation.