Update solution for #12 to be more succinct

[anukem]

Issue Description

Updating the solution for #12 as either an alternative or replacement. I had tried the other solution and it seemed more difficult to reason about because of the additional helper function, but would love to get thoughts on whether or not this implementation is useful to add.

Fixes # (issue)

Changes Made

Please describe the changes that you made.

• Please check if the PR fulfills these requirements

• [ ] PR is descriptively titled and links the original issue above
• [ ] Before/after screenshots (if this is a layout change)
• [ ] Details of which platforms the change was tested on (if this is a browser-specific change)
• [ ] Context for what motivated the change (if this is a change to some content)

[patricoferris]

Hi @anukem apologies for the delay.

I had a look at your solution and it seems correct but there are two problems I see.

1. I'm not sure removing the helper function has made it much clearer (although it is quite subjective). The reason I say that is the recursion in your | Many... -> step is now performing both the adding of the "many" letters and (once c = 0) the moving along of the list of 'a rles. For me this is slightly more confusing. A compromise perhaps is to annotate the functions in the original solution with comments describing what they do?
2. I believe your solution does a fair amount of extra allocating. OCaml is a garbage-collected language and for most non-integer values they are stored in the heap (allocated). This includes things like Many (1, "a") and lists. In the original solution the many helper function adds the appropriate amount of 'a to the list by recursively calling itself with smaller n values. Your solution allocates a new Many (n - 1, v) on to a list (see https://ocaml.org/manual/intfc.html#s:c-ocaml-datatype-repr for more details). A result of this is that your solution for bigger lists with large Manys ends up using quite a bit more memory and takes a bit longer I think.

I'm no expert so perhaps I've gotten point (2) wrong, but I ran some benchmarks using bechamel which seem to back-up my claims https://gist.github.com/patricoferris/951ad129daf14e285b545017d67a06ef. To reproduce you should be able to do (I attached some results from a particular run too):

opam install notty bechamel bechamel-notty
dune exec -- ./main.exe

[anukem]

hey @patricoferris, just now seeing this as well. I appreciate the perf concerns and certainly didn't know the goal was the most efficient solution so apologies for that. As for your first comment about readability, I think my goal in submitting was to provide an alternative solution didn't require a helper. Happy to meet in the middle with the comments on top for further descriptions. Also, I had a smaller change that still hasn't been reviewed that I would love someone to take a look at #1594