Go is not an easy language

Re:Go is not an easy language by johnisgood on Monday February 22, 2021 @02:01AM (#26221625)

Haskell documentation uses the Big O notation everywhere which I really love. I wish Go and many other languages did the same.

An example would be https://hackage.haskell.org/package/containers-0.4.0.0/docs/....

  size :: Map k a -> IntSource
  O(1). The number of elements in the map.

  member :: Ord k => k -> Map k a -> BoolSource
  O(log n). Is the key a member of the map? See also notMember.

  lookup :: Ord k => k -> Map k a -> Maybe aSource
  O(log n). Lookup the value at a key in the map.

And so forth...

[ Parent | on HN ]

Re:Go is not an easy language by arp242 on Monday February 22, 2021 @02:34AM (#26221806)

Redis does the same; e.g. [1]:

> Time complexity: O(N) where N is the number of elements to traverse to get to the element at index. This makes asking for the first or the last element of the list O(1).

I agree this is something more documentations should do when possible; it doesn't even have to be big-O notation as far as I'm concerned, just a "this will iterate over all keys" will be fine.

Ruby's delete() doesn't mention any of this, although you can easily see the (C) implementation in the documentation[2]. In principle at least, this doesn't have to be O(n) if the underlying implementation would be a hash for example, which of course has its own downsides but something like PHP may actually do this with their arrays as they're kind of a mixed data structure? Not sure.

[1]: from https://redis.io/commands/lindex

[2]: https://ruby-doc.org/core-3.0.0/Array.html#method-i-delete

[ Parent | on HN ]

Re:Go is not an easy language by Groxx on Monday February 22, 2021 @02:37AM (#26221824)

Redis's documentation is wonderful, I wish every system I use were documented even half as well.

[ Parent | on HN ]

Re:Go is not an easy language by johannes1234321 on Monday February 22, 2021 @08:05AM (#26224037)

In the C++ standard the complexity of algorithms is a requirement for a compliant implementation. Many text books skip it, but better documentation references it. Taking the "delete element from list" example from this thread https://en.cppreference.com/w/cpp/container/list/remove states that there is a linear search.

[ Parent | on HN ]

Re:Go is not an easy language by mhh__ on Monday February 22, 2021 @03:12AM (#26222039)

Andrei Alexandrescu has a scheme to encode these in the D typesystem on his website. It didn't get merged into the standard library in the end but you can happily do it in your own code

[ Parent | on HN ]