7 ms·

> Text literals use double-quotes (""), and are syntactic sugar for lists of characters. They have type List<Char>. Perhaps not the best choice. I believe this

• eptcyka 6y ago
  Depends on the underlying implementation of `List<T>`. It should be fine as long as it's not a linked list.
  • mannerheim 6y ago
    If I'm reading the implementation of `reverse<T>` correctly, it appears to be a linked list.
    • eptcyka 6y ago
      You're right, oh boy! https://github.com/evincarofautumn/kitten/blob/master/common.ktn#L1152 https://github.com/evincarofautumn/kitten/blob/master/common...
      • exdsq 6y ago
        Why is this an issue, out of interest? :)
        • fiddlerwoaroof 6y ago
          Random access is pretty common with strings, so using a datastructure that makes it expensive is problematic.
          • jjnoakes 6y ago
            Is random access that common? I usually only iterate over strings (and random access is hard to do with utf-8 and friends). I think the two biggest reasons to not use a list of characters to represent a string are memory efficiency (not storing a linked list pointer per character) and memory locality (keeping the characters of the string near each other in memory since they are frequently used as a unit).
            • erik_seaberg 6y ago
              Unicode grapheme clusters (letters/ideograms plus accent marks) are inherently variable length, but most devs haven’t read about how that works. We shouldn’t be working with single codepoints or bytes for the same reason we don’t work with US-ASCII one bit at a time, because most slices of a bit string will be nonsense.
              • bjourne 6y ago
                Treating strings as arrays of bytes is very reasonable. It is the assumption that each byte is exactly one character that causes trouble.
                • astrange 6y ago
                  You should treat them as strings, the backing data store is an implementation detail. What do you want to do with individual bytes if you access them? Whatever you do is likely to be incorrect in some language, even English with emoji mixed in or Zalgo text. This also lets you implement compressed small strings (eg in tagged pointers) which is a good memory optimization.
            • fiddlerwoaroof 6y ago
              Not exactly random access, but things like finding the last character, trimming trailing whitespace, etc. are all less efficient with linked lists because you have to copy the head of the list to change the tail. As far as UTF-8 goes, it does add a whole layer of complexity that I had overlooked: although, I suspect intelligent data structure choices could mitigate the random access cost (something like an array of bytes plus an array of grapheme cluster offsets, or similar). I personally have never found the memory locality concerns relevant to the vast majority of programs I write: when using a language like Python or Ruby or Haskell, you already have a lot of pointer chasing going on because of your non-string data structures such that the memory locality of strings is nearly irrelevant.
              • jjnoakes 6y ago
          • jerf 6y ago
            Exactly the opposite... non-random access is extremely common. If you're reading byte X, the odds that you're going to read X+1 are very good. So it makes most sense to pack them tightly in memory in order, not splash them all over RAM and tie them together with pointers. The latter makes certain things easier, but never by enough on modern hardware to beat the array representation.
            • fiddlerwoaroof 6y ago
              I’m not really talking about access as the computer sees it: most of the code I write that processes strings ends up doing things like splitting at new lines and stripping off the trailing space of each line. Or getting the length of the string or similar things that require efficient access to a semi-arbitrary offset into the string. For the type of string processing code I find myself writing, linked lists are the wrong data structure because they tend to turn O(n) algorithms into O(n^2) ones: this can be mitigated by things like skip-lists, and is complicated by things like Unicode. But, personally, I tend to think that the biggest issue is not the performance impact of non-local storage of the string’s contents (which can be mitigated by techniques like cdr-coding). The problem is that string processing code, in my experience, tends to assume getting a predetermined offset into the string is relatively low cost.
        • mannerheim 6y ago
          It's not a huge issue since you can have other datatypes to deal with strings efficiently. E.g., Haskell has Text and ByteStrings (both lazy and strict versions) for this reason. But it is considered a design mistake that the least efficient way of handling strings was made the default.
        • dahfizz 6y ago
          Linked lists are slower to iterate through than contiguous arrays, and are much slower at random access. Both are common operations for strings
        • andrepd 6y ago
          "Hello World!" now takes 192 bytes in memory, instead of 12. Traversing (for printing, etc) is at least tens of times slower. Changing it to "Hello World?" is now 12 pointer chases rather than 1 assembly instruction. Etc.
        • eptcyka 6y ago
          It doesn't have to be an issue, but users should be aware that the default string type should be avoided in hot paths, which can be cumbersome. The reason it'll be slow is because iterating linked lists involve a lot of pointer chasing, which implies bad behavior on x86 and worse behavior on CPUs that don't have a data prefetcher.
  • astrange 6y ago
    It's a mistake to define a string as a collection type, because strings aren't fundamentally about a single kind of element. They have elements at different abstraction levels (bytes, codepoints, composed characters, words) you sometimes want to enumerate but mostly you operate on the whole string at once. I do think this was a mistake in Haskell, but also it's silly that Haskell and Lisp are based on lists which are a bad inefficient data structure. It's doubly silly that lazy languages like Haskell use linked lists (which are bad) as a metaphor to represent generator functions (which are good).
• neolog 6y ago
  Having characters at all is probably a mistake.
  • alpaca128 6y ago
    How so? Character doesn't necessarily mean ASCII char nowadays, if that's what you mean. And other than that I don't know how it's a mistake to have a concept for the individual parts that make up a String.
    • JadeNB 6y ago
      > How so? Character doesn't necessarily mean ASCII char nowadays, if that's what you mean. And other than that I don't know how it's a mistake to have a concept for the individual parts that make up a String. But why? It seems like having a `Digit` type, and having a `NatNum` type that's `List<Digit>`. (OK, to nerdsnipe myself, that runs into trouble with leading 0's, but hopefully the point is clear. `0 | NonZeroDigit:List<Digit>` is maybe more accurate but less punchy.)
      • alpaca128 6y ago
        > But why? It seems like having a `Digit` type, and having a `NatNum` type that's `List<Digit>`. BigInt types are in fact more or less List<Digit>, normal integer types just aren't implemented like that for performance reasons. A char is the primitive type that makes up a string if chained together. It's more or less a practical naming convention, just like we can call a tuple of floats a vector. Maybe you could get by without chars, but then String would be the only type in your language that doesn't consist of any scalar element but always has an arbitrary length in every situation.
        • reikonomusha 6y ago
          Arguably strings these days don’t really have scalar elements, not at least in the way we think. One “character” might be several distinct code points, and character access might not be a linear time operation.
• artemonster 6y ago
  What is a proper implementation of strings? I often hear this argument (and that null terminated are even worse) but I never understood what is a proper solution then? Can you please explain? Thank you.
  • nerdponx 6y ago
    A text string standalone data type (maybe called Text) that supports traversal/iteration, subsetting/slicing, containment checking, and has a finite known length. Internally it can be a list or array or whatever. Traversal could yield Character objects, which would correspond to Unicode code points (the easy but less-good option, like in Python) or extended grapheme clusters (the actually useful option, like in Swift [0]). It should also be easy to convert to/from a list or array of raw bytes. [0]: https://docs.swift.org/swift-book/LanguageGuide/StringsAndCharacters.html https://docs.swift.org/swift-book/LanguageGuide/StringsAndCh...
  • brundolf 6y ago
    I think they just meant that for ergonomic purposes, strings are very fundamental to most types of programs and deserve first-class support on the same level as primitives Though possibly they just meant a string shouldn't be stored as a linked-list; I'm not familiar enough with Haskell to know whether List implies that underlying representation
    • mannerheim 6y ago
      String in Haskell is a type synonym for `List Char` (or `List<Char>`). The question of 'primitives' in Haskell is tricky, as usually you don't deal with primitives at all, although this depends on what you mean by that word: > Primitive (unboxed) types cannot be defined in Haskell, and are therefore built into the language and compiler. Primitive types are always unlifted; that is, a value of a primitive type cannot be bottom. We use the convention (but it is only a convention) that primitive types, values, and operations have a # suffix (see Section 7.3.2, “The magic hash”). For some primitive types we have special syntax for literals, also described in the same section. So with respect to 'primitives', Strings are not less special in Haskell-land than, say, Integers (which are arbitrary-size and assignable as literals). Anyway, Strings as Lists of Chars perform poorly both memory-wise and speed-wise, which is why the linked-list implementation is generally considered a mistake.
• Syzygies 6y ago
  > I believe this is frequently considered a design mistake in Haskell. More accurately, there's an impedance mismatch with how many people use strings. Text is a better fit for them. The Haskell implementation is not purely functional. It is however well tested, and wicked fast. While it is immensely appealing to view Haskell as a "there is a God!" abstraction, one does well to often consider and exploit what is happening through the looking glass. One sees this for example using `type ShowS = String -> String` to concatenate many small strings to later output all at once. A project I've been meaning to complete is to translate a fast parser of mine to Text, to see if I can get it to run as fast. I'm sure the response to that blog post will be amusing.