Hacker News Reader

Comment by saagarjha | Hacker News Reader

The author uses Go in this example, and they're really just struggling against the language. This is a pretty good example of why choice of language matters: in C++ this could be a simple, linear pass through the array with an std::unordered_set storing visited elements, with an optional std::remove_if/std::erase at the end if they wanted to actually get rid of the elements. All done in linear time, space overhead, and likely with shorter and faster code.

View on HN

Yup, you can implement the whole ordeal in C++ like this:

  int main(int argc, char** argv) {
    std::vector<std::string> strings{
      "apple", "cAt", "cat", "Dog", "apple", "dog", "Cat",
      "Apple", "dOg", "banana", "cat", "dog", "apple",
    };
  
    strings.erase(
      std::remove_if(
        std::begin(strings),
        std::end(strings),
        [seen = std::unordered_set<std::string>{}](std::string_view str) mutable {
          std::string lower = "";
          std::transform(std::begin(str), std::end(str), std::back_inserter(lower), ::tolower);
          if (seen.find(lower) == std::end(seen)) {
            seen.insert(lower);
            return false;
          }
          return true;
        }
      ),
      std::end(strings)
    );
  
    for (auto& str : strings) {
      std::cout << str << "\n";
    };
  }

if (seen.find(lower) == std::end(seen)) { seen.insert(lower); return false; }

You can just return

seen.insert(lower).second

as insert function return a pair<iterator, bool>

And today I learned something new. Been a long time since I wrote my last lines of C++ anyway.

Bonus points for using emplace() instead of insert

Yeah, this is definitely the downside to Go. You can write more or less the same code as your C++ in Rust like this:

    use std::collections::HashSet;
    
    fn main () {
        let strings = vec![
          "apple", "cAt", "cat", "Dog", "apple", "dog", "Cat",
          "Apple", "dOg", "banana", "cat", "dog", "apple",
        ];
        
        let mut set : HashSet<&'static str> = HashSet::new();
        
        let strings : Vec<&str> = strings
            .into_iter()
            .filter(|string| set.insert(string))
            .collect();
        
        println!("{:?}", strings);
    }

(runnable snippet: https://play.rust-lang.org/?version=stable&mode=debug&editio...)

EDIT: updated to make use of the fact that `set.insert` returns a boolean.

Just like C++, your filter can be simplified like,

filter(|string| {set.insert(string)}

as insert return a bool.

Oo, I didn't realise that. Super handy. I've updated my snippet to make use of your suggestion :)

The output form this is a little different form the article, as it additionally requires:

* that the uniqueness check is done case-insensitively,

* that the casing from the first instance of the string in the input array should be used in the output, and

* that the output should be ordered based on the order of the first instance of the string in the input array

Possibly an unusual set of requirements (I'd generally expect that if removing duplicates from a list, that the output order wouldn't matter) but hey, different problems have different requirements.

The desired output is:

    apple
    cAt
    Dog
    banana

while that code snippet produces:

    apple
    cAt
    cat
    Dog
    dog
    Cat
    Apple
    dOg
    banana

I've tried to fix the Rust code, but I'm getting some lifetime errors. Can anyone spot the problem? (Note: I've used C++ for most of the time and am still uncomfortable with Rust)

  use std::collections::HashSet;

  fn main () {
    let strings = vec![
      "apple", "cAt", "cat", "Dog", "apple", "dog", "Cat",
      "Apple", "dOg", "banana", "cat", "dog", "apple",
    ];

    let mut set : HashSet<&'static str> = HashSet::new();
    
    let strings : Vec<&str> = strings
        .into_iter()
        .map(|string| (string, string.to_lowercase()))
        .filter(|(_, lower)| set.insert(lower))
        .map(|(string, _)| string)
        .collect();
    
    println!("{:?}", strings);
  }

The lower value is of type &String because the argument to filter is of type &(String, String) and the pattern match needs to propagate the &. The reference is only valid for the body of the filter closure (that is, it is &'short String, for some anonymous/unnamed lifetime 'short), but it is being put into a set that expects &'static str (the explicit type on the let line). The &String to &str type coercion is fine, but it's not correct to treat the &'short as a &'static (the short one is potentially invalid after filter's closure returns).

Changing the type annotations won't make this compile, because it is actually catching a real bug. The iterator is lazy and the full pipeline is executed for each element at once: lowercasing, inserting into the set, inserting into the Vec that's the result of the collect, and deallocating the lower string. This last step is the key/danger: if the HashSet held references/slices to the lower strings (instead of owning them), those references would become dangling immediately and future look-ups into the set won't work right/will trigger undefined behaviour.

The problem is a little clearer (and mostly fixed) if you simplify the code slightly by removing the two map calls, and instead call to_lowercase in the filter directly:

        .into_iter()
        .filter(|string| set.insert(string.to_lowercase()))
        .collect();

This form is a type error, that can be corrected by changing the type annotation to be HashSet<String>, or even removing it entirely and letting type inference handle it. The HashSet owning the strings is the key, so they only disappear after the entire iteration is complete, not after each element.

Even with the hash set solution, it would be nice to not copy the string contents, which unfortunately is needed if the hash set contains lowercased versions of the strings. On the other hand, converting all strings to lowercase then comparing them isn't a great way to case-insensitively compare strings anyway, as Unicode doesn't guarantee that will work.

The UniCase crate defines a wrapper around strings with a case-insensitive Eq implementation, so this works:

    use std::collections::HashSet;
    use unicase::UniCase;

    fn main () {
        let strings = vec![
            "apple", "cAt", "cat", "Dog", "apple", "dog", "Cat",
            "Apple", "dOg", "banana", "cat", "dog", "apple",
        ];
        
        let mut set = HashSet::new();
        
        let strings: Vec<_> = strings
            .iter()
            .filter(|&string| set.insert(UniCase::new(string)))
            .collect();
        
        println!("{:?}", strings);
    }

https://play.rust-lang.org/?version=stable&mode=debug&editio...

This is pretty cool. People might think it's cheating to pull in a crate. But IMO the fact that its super easy to pull in a crate in Rust is one of the best things about the language.

You don't even need the filter, all you need is:

    let dedup = strings.into_iter().map(|s| s.to_lowercase()).collect::<HashSet<_>>().into_iter().collect::<Vec<_>>();

Unfortunately that doesn't preserve case nor order of the input strings.

Similar to the C++, all of those are addressed by inserting lower-cased into the set, which can be achieved via an extra method call:

   set.insert(string.to_lowercase())

It also requires adjusting/deleting the type annotation on the set.

https://play.rust-lang.org/?version=stable&mode=debug&editio...

For completeness, Java is basically the same:

    List<String> strings = new ArrayList<>(List.of("apple", "cAt", "cat", "Dog", "apple", "dog", "Cat",
                                                   "Apple", "dOg", "banana", "cat", "dog", "apple"));

    Set<String> seen = new HashSet<>();
    strings.removeIf(s -> !seen.add(s.toLowerCase()));

    strings.forEach(System.out::println);

EDIT How much copying does each implementation do?

The Go version only copies in the cleanup pass he doesn't show, so it copies each surviving element once, and no other elements. The Rust version makes a new vector, so it does the same minimal amount of copying (well, moving). The C++ version uses remove_if, and the documentation doesn't specify how it does the copying [1], but knowing what C++ people are like, it will probably do the minimum of copying too. The Java version hits some truly hoopy code in removeIf [2], which does the same minimal copying, but does allocate a bitmap and walk the array twice, in order to support predicates which want to look at the rest of the list.

I would say all of these reflect their language's values. The Go code is efficient, but only because the programmer has to write it all out longhand, so there is nowhere for inefficiency to hide. The C++ code is (i think!) efficient, because C++ implementers value maximal efficiency in their libraries. The Java code sacrifices a little efficiency to allow its users to do silly things safely.

[1] https://en.cppreference.com/w/cpp/algorithm/remove

[2] http://hg.openjdk.java.net/jdk/jdk11/file/1ddf9a99e4ad/src/j...

>The Rust version makes a new vector, so it does the same minimal amount of copying (well, moving).

To be clear, the Rust version does not do any copying or moving of the strings. Both the set and the new Vec contains &'static str, same as the original Vec.

But a more realistic example is where the original Vec was of String elements instead of &'static str. The same point would still apply, but the result Vec of &str would borrow from the original Vec of String. If the goal was to produce a Vec of String, then it would need to copy (clone) the Strings from the original Vec.

This is good enough for "small" arrays, but I wouldn't wanna run it on really large ones. You double the space with those lowercased copies + some extra space for the set itself. And you'll also spend a lot of time lowercasing the strings and std::hash'ing them for the set.

You need to be careful with C's tolower. It takes a signed integer, and negative values are undefined behaviour. It would be safer to cast to unsigned char before calling tolower. https://en.cppreference.com/w/cpp/string/byte/tolower

This is the author's choice to make the problem hard -- Go has a built-in map type that works fine for this, and produces code as compact as the C++ version, and is also O(n):

  seen := make(map[string]bool)

  for n, s := range array {
    if seen[strings.ToLower(s)] {
      array[n] = ""
    } else {
      seen[strings.ToLower(s)] = true
    }
  }

Code golf: https://play.golang.org/p/mZf5KoAN_87

Don't calculate strings.ToLower() twice and skip over s == "" to avoid the map lookups and some assignments when already tombstoned and you'll save a lot of time.

    seen := make(map[string]bool)
    for n, s := range array {
        if s == "" {
            continue
        }
        lower := strings.ToLower(s)
        if seen[lower] {
            array[n] = ""
        } else {
            seen[lower] = true
        }
    }

How can an element be already tombstoned? Isn’t that the first loop, making only one pass?

Does Go just warp people's view of what's possible in programming languages? This is a trivial problem to solve for arrays on any data type, but the author can only think about solving it with strings and for whatever bizarre reason can't write out the name "hash set" for the simplest, most general and performant solution?

Yes. Or more precisely, any language puts various limits on what you can easily and conveniently express - in the strict sense, everything you can implement in one language you can implement in all of them as long as they're Turing-complete. However, the amount of effort required to express different things varies between the languages very significantly, and the users tend to confine their thinking to the most directly-supported features of the language they use, as they are most convenient to use most of the time. The term to search for is the "Blub paradox".

Go is a language which consciously limits the expressive power of the language in some areas, with the goal of simplifying the implementation and reducing the complexity of codebases written in Go (trading that for repetition). We'll see in 20 years how that plays out.

Anyway, constraining oneself to a single language is never good. Learning other languages widens the horizons of what you can imagine implemented (and how), also in your original language. I wish more people - especially starry-eyed fans of this or that language - learned about this fact... :)

> Blub

I love the blub paradox story[0]. If you hadn't mentioned it, I was going to. The central idea is, each language lives at a particular spot on a 'power spectrum' -- perhaps 'expressiveness spectrum' is more accurate since theoretically any Turing-equiv lang is technically as powerful as the others.

When you look down the power spectrum, at less-expressive languages, it's easy to scoff and say "I can't believe that language is missing Feature X of my chosen language." But when you look up the spectrum (and in the article, LISP is the example given), the more powerful features in that language just look like nonsense. The money quote is "Blub is good enough for him, because he thinks in Blub."

For me, my primary language is C#. When I look at Go, I can't help but think "I can't believe it doesn't have generics, how can anyone get anything done in it?" But when I look at LISP metaprogramming, I get uncomfortable with my lack of understanding. Luckily I am a language nerd so I force myself to experience languages at all ends of the spectrum.

Highly recommended read.

[0]: http://www.paulgraham.com/avg.html

> Luckily I am a language nerd

Oh, hi there, always good to meet others with the same hobby ;)

Yeah, the Blub essay is well-written and it influenced my thinking significantly when I read it for the first time. It was one of the reasons I started asking myself: "what other above-Blub languages are there, and what features do they boast?" and made me become a language nerd ;)

Many years later, after actually experiencing a whole lot of niche languages and wandering close to the verge of insanity countless times, I concluded that the "expressive power" is not that simple to define, that its definition can change over time (the essay is from 2001!). It's easy to imagine languages placed on steps of a ladder, where more expressive ones occupy higher positions. It can be a good mental model in practice when considering relatively similar languages, too.

The problem is, there are languages which use entirely different ladders! From the perspective of all languages on Blubby ladder, they set out to solve different problems, assume completely different contexts of use, use completely alien computation models, in short: work in a fundamentally different way.

It's not that they're not general-purpose languages, but still, directly comparing "expressive power" of Forth, Joy, Lisp, Prolog, Smalltalk, Clean, Idris, APL, Rebol with BASIC, Pascal, C/++/#, PHP, Python, JS and the likes just feels off somehow :) In other words, I believe that the phenomenon of language expressive power is not based simply on the number of features the language implements and even how advanced they are - it's got to be more complex than that. To me, rather than a single ladder, it looks like a 3d surface with randomly erected hills, where groups of similar languages gather around and below the local maxima. It's not certain if the relative heights of the hills are comparable in some way or if that comparison would have any meaning.

It was actually very pleasant realization: as I was heading towards the top of the ladder (starting at Pascal and C level), I stopped to look around and suddenly discovered that from this high up I can see a whole lot more hills worth climbing!

Anyway, whatever your approach and route would be, learning new languages is always good. Learning the concepts behind them gives you more mental tools for problem-solving, and learning about their internals often leads to a much better understanding of the concepts. Plus, forcing oneself to experience all of that is fun in its own right :)

What do you do if you're in a Go project and need to implement this, though? The complexity of FFIs and the maintenance expense of adding another language/compiler is worse than having to work against the language.

> What do you do if you're in a Go project and need to implement this, though?

Learn from your mistakes.

This is a bit like saying that English is a language superior to Danish, because there are better books out there in English.

I don't think this has anything to do with the language, it just happens that C++ ships with a much bigger standard library than Go.

It's much easier to implement in Javascript, too, even though JS has a much smaller standard library. The main problem is Go's lack of generics.

indeed, currently the standard library of JS is incredibly small.

> it just happens that C++ ships with a much bigger standard library than Go.

I thought go had much bigger standard library. Go has archive, compression, crypto, database, encoding, hash, html, and net etc.

It does have to do with the language. Writing a generic Set type is trivial in many languages, yet hard in Go.

Keep in mind that I’m not saying that C++ is a better language than Go here: I’d need a lot more evidence than an array deduplication routine to prove this. I’m just saying that Go is ill-suited for this particular task as compared to C++, and the author is struggling with this as they go through with implementing their algorithm; this leads them to settle on a clumsy and inefficient “solution” because there isn’t really a good alternative in the confines of the language that they chose. (FWIW, C++ does have a good standard library for implementing algorithms but this doesn’t really come into play here, since we’re not doing anything advanced. Any language with a set and filter would do the job. And for the record, I do think that C++ is a better language than Go, but I’m not going to argue it here because I don’t know the latter well enough to be confident in my viewpoint and don’t have enough space here to discuss it here if I did.)

Reply on news.ycombinator.com