3 ms·

Don't overthink it. But if we're gonna overthink it, one thing we can notice is that a rose tree is a free monad, and like any free structure is initial in its

Don't overthink it. But if we're gonna overthink it, one thing we can notice is that a rose tree is a free monad, and like any free structure is initial in its category - meaning there's a unique monad homomorphism from a rose tree to any other monad. Lists form a monad, so we can ask "what is that homomorphism?" It turns out to be the traditional definition of flatten. That is to say, only flatten solves these equations for lists and rose trees: (flatten . f =<< flatten m) == flatten (f =<< m) pure x = flatten (pure x)

cestith 10y ago
I believe speaking of monads, monoids, functors, and homomorphism when discussing an interview question for fairly fresh programmers is definitely overthinking it. I'm not sure what you think is so simple about your solution compared to: sub flatten { map { ref ? flatten( @$_ ) : $_ } @_; } Goodness, and Perl gets a bad reputation for the amount of punctuation in the code. Of course if you want flatten in Haskell you have it for Tree and Forest. import Data.Tree tree = Node "A" [Node "B" [], Node "C" [Node "D" [], Node "E" []], Node "F" []] main = do print $ flatten tree If a Perl programmer wanted to pull in a CPAN module, there are many from which to choose. Of course, it was just done in a one-line subroutine...: http://search.cpan.org/~obradovic/List-Flatten-0.01/lib/List/Flatten.pm http://search.cpan.org/~obradovic/List-Flatten-0.01/lib/List... (which does not handle arbitrary depths) http://search.cpan.org/~rthompson/List-Flatten-Recursive-0.103460/lib/List/Flatten/Recursive.pm http://search.cpan.org/~rthompson/List-Flatten-Recursive-0.1... (which seems overly complicated) http://search.cpan.org/~rsavage/Set-Array-0.30/lib/Set/Array.pm#flatten() http://search.cpan.org/~rsavage/Set-Array-0.30/lib/Set/Array... (which tries to flatten hashes as well as lists and seems, well, overly complicated... and pulls in a bunch more methods and functions) http://search.cpan.org/~satoh/List-Enumerator-0.10/ http://search.cpan.org/~satoh/List-Enumerator-0.10/ (which seems about right, including stopping the flattening at an arbitrary depth and comes with other useful array tools) Of course it's possible to apply the concept of flattening to hashes/dictionaries, too, so there goes the concept of keeping the original sort order. http://search.cpan.org/~bbc/Hash-Flatten-1.19/lib/Hash/Flatten.pm http://search.cpan.org/~bbc/Hash-Flatten-1.19/lib/Hash/Flatt... http://search.cpan.org/~chocolate/Hash-Fold-0.1.2/lib/Hash/Fold.pm http://search.cpan.org/~chocolate/Hash-Fold-0.1.2/lib/Hash/F...
- dllthomas 10y ago
  > I believe speaking of monads, monoids, functors, and homomorphism when discussing an interview question for fairly fresh programmers is definitely overthinking it. I agree. I said as much. I just thought it was interesting. > I'm not sure what you think is so simple about your solution compared to [...] Which solution? I didn't present an implementation in this thread. I did elsewhere (https://news.ycombinator.com/item?id=13726564 https://news.ycombinator.com/item?id=13726564), but I don't think that's what you're talking about? I was discussing specification, and the code fragment in my comment was a property, not a definition. > Of course if you want flatten in Haskell you have it for Tree and Forest. Yes, though Tree is a slightly less natural choice for this than a rose tree (aka `Free []`). Of course, you still have it (in the form of toList). > If a Perl programmer wanted to pull in a CPAN module, there are many from which to choose. Of course, it was just done in a one-line subroutine. ... yes? You seem to be desperately trying to defend perl against an attack you imagine me to have made. I have nothing against perl (at least, nothing beyond a strong desire for static types on large projects, but that applies equally to a great many languages).
  - cestith 10y ago
    Oh, I'm not imagining you making an attack on Perl. It happens commonly enough, though. I was commenting that your property had a lot of punctuation and bemoaned that Perl with the same amount often gets criticized for that very thing. Meanwhile many of the same people are fine with Python's invisible punctuation, Lisp's parentheses, or Haskell's syntax which likewise includes a lot of punctuation. I also was pointing out that Haskell has Tree shipping with it, and Perl's CPAN, which is usually a stellar place to look, has what appear to be some false starts. I'd sort of expect one of the many List:: modules like List::Utils, List::MoreUtils, etc. to have the functionality, but as far as I saw when looking, no. It's easy enough to do in the base language, though. I assumed Haskell from your language and the syntax of your notation. Your Bash and sed solution appears simple on the surface, but it is using a trick of the data format and bringing together two languages. It's even using a syntax that will confuse some people on first look in that you're putting square brackets within square brackets starting with the right bracket then the left. Many people are going to look at that and at first think it's two empty character classes then do a double take. It's clever, but any simplicity in it is rather baked into some, let's say interesting assumptions. I like it as a snarky response to the problem, but it's not something I'd hire a programmer for proposing as a serious solution.

cestith 10y ago

I believe speaking of monads, monoids, functors, and homomorphism when discussing an interview question for fairly fresh programmers is definitely overthinking it. I'm not sure what you think is so simple about your solution compared to: sub flatten { map { ref ? flatten( @$_ ) : $_ } @_; } Goodness, and Perl gets a bad reputation for the amount of punctuation in the code. Of course if you want flatten in Haskell you have it for Tree and Forest. import Data.Tree tree = Node "A" [Node "B" [], Node "C" [Node "D" [], Node "E" []], Node "F" []] main = do print $ flatten tree If a Perl programmer wanted to pull in a CPAN module, there are many from which to choose. Of course, it was just done in a one-line subroutine...: http://search.cpan.org/~obradovic/List-Flatten-0.01/lib/List/Flatten.pm http://search.cpan.org/~obradovic/List-Flatten-0.01/lib/List... (which does not handle arbitrary depths) http://search.cpan.org/~rthompson/List-Flatten-Recursive-0.103460/lib/List/Flatten/Recursive.pm http://search.cpan.org/~rthompson/List-Flatten-Recursive-0.1... (which seems overly complicated) http://search.cpan.org/~rsavage/Set-Array-0.30/lib/Set/Array.pm#flatten() http://search.cpan.org/~rsavage/Set-Array-0.30/lib/Set/Array... (which tries to flatten hashes as well as lists and seems, well, overly complicated... and pulls in a bunch more methods and functions) http://search.cpan.org/~satoh/List-Enumerator-0.10/ http://search.cpan.org/~satoh/List-Enumerator-0.10/ (which seems about right, including stopping the flattening at an arbitrary depth and comes with other useful array tools) Of course it's possible to apply the concept of flattening to hashes/dictionaries, too, so there goes the concept of keeping the original sort order. http://search.cpan.org/~bbc/Hash-Flatten-1.19/lib/Hash/Flatten.pm http://search.cpan.org/~bbc/Hash-Flatten-1.19/lib/Hash/Flatt... http://search.cpan.org/~chocolate/Hash-Fold-0.1.2/lib/Hash/Fold.pm http://search.cpan.org/~chocolate/Hash-Fold-0.1.2/lib/Hash/F...

dllthomas 10y ago
> I believe speaking of monads, monoids, functors, and homomorphism when discussing an interview question for fairly fresh programmers is definitely overthinking it. I agree. I said as much. I just thought it was interesting. > I'm not sure what you think is so simple about your solution compared to [...] Which solution? I didn't present an implementation in this thread. I did elsewhere (https://news.ycombinator.com/item?id=13726564 https://news.ycombinator.com/item?id=13726564), but I don't think that's what you're talking about? I was discussing specification, and the code fragment in my comment was a property, not a definition. > Of course if you want flatten in Haskell you have it for Tree and Forest. Yes, though Tree is a slightly less natural choice for this than a rose tree (aka `Free []`). Of course, you still have it (in the form of toList). > If a Perl programmer wanted to pull in a CPAN module, there are many from which to choose. Of course, it was just done in a one-line subroutine. ... yes? You seem to be desperately trying to defend perl against an attack you imagine me to have made. I have nothing against perl (at least, nothing beyond a strong desire for static types on large projects, but that applies equally to a great many languages).
- cestith 10y ago
  Oh, I'm not imagining you making an attack on Perl. It happens commonly enough, though. I was commenting that your property had a lot of punctuation and bemoaned that Perl with the same amount often gets criticized for that very thing. Meanwhile many of the same people are fine with Python's invisible punctuation, Lisp's parentheses, or Haskell's syntax which likewise includes a lot of punctuation. I also was pointing out that Haskell has Tree shipping with it, and Perl's CPAN, which is usually a stellar place to look, has what appear to be some false starts. I'd sort of expect one of the many List:: modules like List::Utils, List::MoreUtils, etc. to have the functionality, but as far as I saw when looking, no. It's easy enough to do in the base language, though. I assumed Haskell from your language and the syntax of your notation. Your Bash and sed solution appears simple on the surface, but it is using a trick of the data format and bringing together two languages. It's even using a syntax that will confuse some people on first look in that you're putting square brackets within square brackets starting with the right bracket then the left. Many people are going to look at that and at first think it's two empty character classes then do a double take. It's clever, but any simplicity in it is rather baked into some, let's say interesting assumptions. I like it as a snarky response to the problem, but it's not something I'd hire a programmer for proposing as a serious solution.