3 ms·

> Types are your data structures Is this true? I understand types are abstract, while data structures are concrete. Like, the type... x -> a x y -> z y ...t

> Types are your data structures Is this true? I understand types are abstract, while data structures are concrete. Like, the type... x -> a x y -> z y ...tells me nothing. But that is, among many things, the type for a hash map lookup. Still, a hash map is a particular implementation, and the type alone doesn't capture this – it could mislead me into thinking any implementation that fits this shape is fine.

lolinder 4y ago
You made that type artificially abstract by leaving out the type names, which in a nominally-typed language are a first-class part of the type signature, not arbitrary symbols you can leave out. This is the actual type of Haskell's dictionary lookup: k -> Map k a -> Maybe a I don't know about you, but that's pretty self-explanatory to me.
- hcarvalhoalves 4y ago
  The moment you name the type, you're talking about a particular implementation, no? The type system doesn't know about the semantics humans ascribe to names, it just matches shapes. That's only because you, the programmer, expect a type named "hash map" to implement a hash map – but this information is not being described by the type itself, it's out-of-band. The actual definition of the hash map data structure is given by the algorithm. In fact, without inspecting the algorithm, it's impossible to know it correctly implements a hash map, you're just trusting the arbitrary name of the type.
  - lolinder 4y ago
    > The moment you name the type, you're talking about a particular implementation, no? Depending on the language, no. In many languages types can be subtyped, and if you name the supertype you do not know necessarily which implementation you have. (Incidentally, in Haskell, a Map is not a HashMap, it is a tree map.) > The actual definition of the hash map data structure is given by the algorithm. In fact, without inspecting the algorithm, it's impossible to know it correctly implements a hash map, you're just trusting the arbitrary name of the type. This is exactly my point! The question we started with is: does the type signature help you to reason about how to transition from one data structure to another data structure without having to think about the details of the algorithm? I argue that it does, because I tend to trust that standard library designers aren't capriciously violating my expectations for what a Map is. If you trust the standard library designers, then the type signature abstracts away the implementation details of the algorithm so you can do what Rob Pike recommends and focus on the data. If you don't trust your language's standard library, you have worse problems than difficulty reasoning about type relations.
    - nequo 4y ago
      > trust that standard library designers aren't capriciously violating my expectations for what a Map is. You don't even need to trust them. The compiler checks that their Map is the same as what you call a Map. In the scenario that I am imagining, you have defined your data structures as types. You're looking for an algorithm to perform a particular transformation on your data. This transformation is from one data type to another, so you know the "type signature" of the algorithm. If the algorithm is already implemented, then you can find it with typed holes or Hoogle. If it doesn't exist yet, you can write it. Rob Pike's Rule 5 says that if your types are good, it will be self-evident what functions to use to transform them.
      - lolinder 4y ago
        > You don't even need to trust them. The compiler checks that their Map is the same as what you call a Map. Sort of. I think the person I was replying to was indicating that the implementation could be wrong and still match the type signature. As a simple example, `insert` could return the exact same Map object as was passed in (rather than one that has the key updated) and still match the type signature of `insert`. On the whole you're right, because if your standard data structures are that bad you should really be using a different language, not choosing to ignore types because they might not be helpful this time.
nequo 4y ago
> the type... > x -> a x y -> z y > ...tells me nothing. I am guessing that you wouldn’t see a type signature like this in a real codebase. The type signature of Data.HashMap.Strict.lookup is (Eq k, Hashable k) => k -> HashMap k v -> Maybe v which is quite a bit more readable. You can even search Hoogle for x -> HashMap x y -> y and find it, try it! https://hoogle.haskell.org/?hoogle=x%20-%3E%20HashMap%20x%20y%20-%3E%20y https://hoogle.haskell.org/?hoogle=x%20-%3E%20HashMap%20x%20...
valenterry 4y ago
That's like saying "words are abstract, while nouns are concrete". Not really. Types include datastructures. They define the set of values that a datastructure can assume. They do the same for everything else, like variables, functions etc.

lolinder 4y ago

You made that type artificially abstract by leaving out the type names, which in a nominally-typed language are a first-class part of the type signature, not arbitrary symbols you can leave out. This is the actual type of Haskell's dictionary lookup: k -> Map k a -> Maybe a I don't know about you, but that's pretty self-explanatory to me.

hcarvalhoalves 4y ago
The moment you name the type, you're talking about a particular implementation, no? The type system doesn't know about the semantics humans ascribe to names, it just matches shapes. That's only because you, the programmer, expect a type named "hash map" to implement a hash map – but this information is not being described by the type itself, it's out-of-band. The actual definition of the hash map data structure is given by the algorithm. In fact, without inspecting the algorithm, it's impossible to know it correctly implements a hash map, you're just trusting the arbitrary name of the type.
- lolinder 4y ago
  > The moment you name the type, you're talking about a particular implementation, no? Depending on the language, no. In many languages types can be subtyped, and if you name the supertype you do not know necessarily which implementation you have. (Incidentally, in Haskell, a Map is not a HashMap, it is a tree map.) > The actual definition of the hash map data structure is given by the algorithm. In fact, without inspecting the algorithm, it's impossible to know it correctly implements a hash map, you're just trusting the arbitrary name of the type. This is exactly my point! The question we started with is: does the type signature help you to reason about how to transition from one data structure to another data structure without having to think about the details of the algorithm? I argue that it does, because I tend to trust that standard library designers aren't capriciously violating my expectations for what a Map is. If you trust the standard library designers, then the type signature abstracts away the implementation details of the algorithm so you can do what Rob Pike recommends and focus on the data. If you don't trust your language's standard library, you have worse problems than difficulty reasoning about type relations.
  - nequo 4y ago
    > trust that standard library designers aren't capriciously violating my expectations for what a Map is. You don't even need to trust them. The compiler checks that their Map is the same as what you call a Map. In the scenario that I am imagining, you have defined your data structures as types. You're looking for an algorithm to perform a particular transformation on your data. This transformation is from one data type to another, so you know the "type signature" of the algorithm. If the algorithm is already implemented, then you can find it with typed holes or Hoogle. If it doesn't exist yet, you can write it. Rob Pike's Rule 5 says that if your types are good, it will be self-evident what functions to use to transform them.
    - lolinder 4y ago
      > You don't even need to trust them. The compiler checks that their Map is the same as what you call a Map. Sort of. I think the person I was replying to was indicating that the implementation could be wrong and still match the type signature. As a simple example, `insert` could return the exact same Map object as was passed in (rather than one that has the key updated) and still match the type signature of `insert`. On the whole you're right, because if your standard data structures are that bad you should really be using a different language, not choosing to ignore types because they might not be helpful this time.

nequo 4y ago

> the type... > x -> a x y -> z y > ...tells me nothing. I am guessing that you wouldn’t see a type signature like this in a real codebase. The type signature of Data.HashMap.Strict.lookup is (Eq k, Hashable k) => k -> HashMap k v -> Maybe v which is quite a bit more readable. You can even search Hoogle for x -> HashMap x y -> y and find it, try it! https://hoogle.haskell.org/?hoogle=x%20-%3E%20HashMap%20x%20y%20-%3E%20y https://hoogle.haskell.org/?hoogle=x%20-%3E%20HashMap%20x%20...

valenterry 4y ago

That's like saying "words are abstract, while nouns are concrete". Not really. Types include datastructures. They define the set of values that a datastructure can assume. They do the same for everything else, like variables, functions etc.