Hacker News Reader

Comment by weavejester | Hacker News Reader

"No, it's just a simple [Map Text Text]. Or if you want a little more safety, then [Map Text Value]."

I think you're confusing `assoc-in` with `assoc`. The latter is trivial to type; the former is not.

The problem with typing `assoc-in`, is that the type of the vector of keys is derived from the type of the nested map in a way that's hard to generalize.

For example:

    (assoc-in m [a] b)

Has (approximately) the type signature:

    Map a b -> a -> b -> Map a b

But:

   (assoc-in m [a b] c)

Has the type signature:

   Map a (Map b c) -> (a, b) -> c -> Map a (Map b c)

And so forth.

"But this requires more code. More code is error-prone and takes time to write and maintain."

No it doesn't; you can generate and run the tests from the function's spec automatically. If I run `(clojure.spec.test.alpha/check)` in Clojure, it will generate and run tests for all functions that have specs.

View on HN

> The latter is trivial to type; the former is not.

That's why I'm not trying to make it typed. Instead of

    Map a (Map b c)

I'm dropping down to something like

    Map Int (Map Text a)
    Map Int (Map Text Text)
    [Map Text Text]
    Vector (Map Text Text)

...which is more like what's really going on in Clojure.

Come to think about it, assoc-in is a great example of why I want static types. It's very hard to figure out what that function does from reading the documentation. There's no type signature to help me, the description doesn't give me much more to go on. Reading the examples leaves me wondering whether I actually understand what it's doing or if I'm missing some corner case.

> it will generate and run tests for all functions that have specs

But you have to write the specs. And that's the code I'm talking about. Fundamentally the generator can't just know what behavior you want and what you don't want. You have to tell it.

"That's why I'm not trying to make it typed."

Are you proposing that a distinct `assoc-in` function should be written for every combination of types you'd need in your program?

Doesn't that rather prove my point that some functions that are trivial to write in a dynamically typed language are hard to write in a statically typed language?

"Come to think about it, assoc-in is a great example of why I want static types. It's very hard to figure out what that function does from reading the documentation."

I've always thought the function was trivial. I mean, it's just four lines of code:

    (defn assoc-in [m [k & ks] v]
      (if ks
        (assoc m k (assoc-in (get m k) ks v))
        (assoc m k v)))

I have a much harder time relating back a complex type signature in Haskell back to what the function actually does, but perhaps that's something that just requires more practice.

"But you have to write the specs."

Sure, but you have to write the type signatures, too. Type inference certainly cuts down on a lot of work, but it doesn't entirely eliminate the need for explicit typing.

I also tend to prefer adding explicit type signatures, even for functions that could be inferred. It makes type errors easier to catch.

> Are you proposing that a distinct `assoc-in` function should be written for every combination of types you'd need in your program?

No. I'm proposing something like what tel described elsewhere in the thread. If that's not dynamic enough for you, then you can go with something like JSON's Value type. In both cases lenses give you very convenient and composable access and manipulation.

> I've always thought the function was trivial. I mean, it's just four lines of code:

But you have to read the code. The type signature / code boundary is very useful for allowing you to chunk things and abstract over implementation details. This particular case may not be much code to read, but that is often not true in the general case.

> Sure, but you have to write the type signatures, too. Type inference certainly cuts down on a lot of work, but it doesn't entirely eliminate the need for explicit typing.

> I also tend to prefer adding explicit type signatures, even for functions that could be inferred. It makes type errors easier to catch.

That's exactly my point. Type signatures can be inferred, specs cannot. Choosing to add them is irrelevant. If you want the add them that can be done automatically.

"No. I'm proposing something like what tel described elsewhere in the thread."

tel's solutions are "use lenses" or "assume all keys are strings", both of which miss the point.

Yes, you can work around the limitations of a static type system, either by finding another solution (lenses) or by making functions more specific (assume all keys are strings), but that doesn't mean the limitations disappear. It just means you're working around them.

In a statically typed language the solutions to a problem are constrained by the type system. The question is not whether statically typed languages are more constrained than dynamically typed languages, but whether the constraints that static typing introduces are offset by the guarantees they purchase.

"That's exactly my point. Type signatures can be inferred, specs cannot."

The compiler can infer some type signatures, and if you're not explicitly typing your named functions (which is generally cited as good practice), that does mean you get some checking "for free".

But specs can also test more things than types; they occupy a space somewhere inbetween static types and a generative testing solution like QuickCheck. Depending on the function, a spec might be more or less verbose than the equivalent checks in a language like Haskell.

> Yes, you can work around the limitations of a static type system, either by finding another solution (lenses) or by making functions more specific (assume all keys are strings), but that doesn't mean the limitations disappear. It just means you're working around them.

I'm less concerned about the theoretical limitations of types that you seem to be talking about and more interested in looking at concrete real-world applications where you think you need dynamic types and seeing exactly what we can do to address them with a type system. I know there exist things that are difficult or maybe impossible to define types for (the Y combinator for instance, or possibly this assoc-in). My argument is that you don't need this power. I don't care whether difficult to type things exist, I care about whether real-world problems require them. I have yet to encounter one that I felt requires the same amount of dynamic typing power that you seem to be arguing for.

See this thread for some concrete examples:

https://www.reddit.com/r/haskell/comments/792nl4/clojure_vs_...

You can use lenses, it's something like

    over (at "foo" . at "bar") :: (a -> b) -> (Map String (Map String a) -> Map String (Map String b))

Neatly, this system generalizes to typed realizations immediately, too.

    over (foo . bar)

Sure, lenses are a solution. My point isn't that an alternative solution to this is impossible (or even difficult) in a statically typed language, but that static typing makes some solutions infeasible. There are some very trivial functions that Clojure has that are nevertheless impractical to write a robust type signature for.

There's also the way where you encode `Map String Value` as a member of `Value`. This is closer to what Clojure does and does allow assoc-in to be written directly. I was just playing along with the other comments' encoding of maps.

    data Value = 
      ...
      | VMap (Map String Value)
      | VNull
      ...

    assocIn :: [String] -> (Value -> Value) -> (Value -> Value)
    assocIn (name:names) f (VMap m) = _

In general, the more type information you leave around the more you have to do to ensure that it remains meaningful. Erase enough of it and you can arrive back at Clojure.

You're not solving the same problem. You're fixing the keys of the nested maps to a single type, but the difficulty is when the keys are all different types.

In other words, you want to type a general form of:

    Map a (Map b (Map c ... z)) -> (a, b, c...) -> z -> Map a (Map b (Map c ... z))

And even that is more limited that Clojure's `assoc-in`, as the type signature still assumes each nested map is homogenous.

When they keys are all different types then you've got

    data Value =
      ...
      | VMap (Map Value Value)
      ...

    assocIn :: [Value] -> (Value -> Value) -> (Value -> Value)

I was again assuming types more informative than Clojure. Also again, lenses actually solve the higher information type situation that you're pointing at in your comment.

Yes, you can write the function using entirely dynamic types:

    Map Dynamic Dynamic -> [Dynamic] -> Dynamic -> Map Dynamic Dynamic

But would you actually write a function like that? Of course not. Not only is it a pain to unwrap nested maps of dynamic types, but you lose almost all the advantages of a static type system.

So what's the alternative? As you point out, a more idiomatic way is to use lenses, as they solve a similar problem but can be typed.

However, in Clojure we can use assoc-in or lenses. Dynamically typed languages are not constrained by what is feasible to statically type. In Haskell, it is hard to the point of being infeasible to robustly type assoc-in, so it's not idiomatic to use it. But in Clojure we're not restricted by the limitations of a static type system; we can use functions like assoc-in.

This is the trade off of static typing. A static type system limits what solutions are feasible and idiomatic; even functions that are simple to express and reason about, can be extremely hard to accurately type.

I wouldn’t because once I’ve got a type system the tradeoff never works out. But the same thing can be expressed.

I don’t see the thrust of your argument. You can write both styles of program in both languages, but you can only have type guarantees in a language with a type system.

So, you’ve shown that assoc-in can be written so long as type guarantees are thrown away. That seems like a reasonable reason to pick lenses either way.

"You can write both styles of program in both languages"

No you can't, not in any way that's practical.

It's possible to write Haskell by wrapping every value in a Dynamic type, but possible does not mean feasible.

If you don't believe there's a distinction, then try writing a functionally equivalent `assoc-in` in Haskell. I don't mean sketch out a design in pseudo-code; I mean produce a fully working function that operates seamlessly with all possible types of Data.Map.

"So, you’ve shown that assoc-in can be written so long as type guarantees are thrown away. That seems like a reasonable reason to pick lenses either way."

Well, that's the question: is it?.

Lenses can be typed, but `assoc-in` is conceptually simpler. Haskell advocates using only solutions that can be typed; Clojure advocates using the simplest solution.

Static typing is a constraint, because it limits the solutions that are feasible and idiomatic. In return it provides a compile-time guarantee. The question is whether the guarantee is worth the solutions that are (for all practical purposes) removed.

Immutability is another type of constraint. As is automatic memory management, variable scoping... programming languages are designed around constraints. Pretending that you can introduce a constraint and not narrow the solution space is wishful thinking.

It’s feasible and easy to write assoc-in atop of Dynamic... it’s just not done because nobody programming in Haskell thinks it’s valuable. We could choose to support much more opt-out dynamic behavior no sweat, but nobody wants to.

The idea of assoc-in working for every type of Map also doesn’t make sense. Map only exists statically. Types as Clojure discusses them exist at runtime, are statically Dynamic, and it’s trivial to write assoc-in that works over all of them in any language.

Your argument hinges on the idea that it’s impractical to write using Dynamic in Haskell. I do not think this is true. There is perhaps some value in greater library support, but it is easy to do this. It is simply not considered valuable.

"It’s feasible and easy to write assoc-in atop of Dynamic..."

Then why don't you do it and post up the code? If it's as easy as writing the same function in a dynamically typed language it shouldn't take more than a minute or two.

"The idea of assoc-in working for every type of Map also doesn’t make sense. Map only exists statically."

Maybe you're misunderstanding me? I mean it should work for every `Data.Map k a`, where `k => Ord`, just like all the other Data.Map functions.

"Your argument hinges on the idea that it’s impractical to write using Dynamic in Haskell. I do not think this is true."

Then try it?

> I mean it should work for every `Data.Map k a`, where `k => Ord`, just like all the other Data.Map functions.

This is where we're got a difference of opinion. My statement is that assoc-in doesn't do anything close to working over "every `Data.Map k a`". Data.Map is a compile-time idea classifying names in the language and the Data.Map functions are designed to respect that both dynamically (manipulate some memory properly) and statically (create updated contexts with new and different information).

On the other hand, assoc-in works only dynamically/at runtime over all kinds of (Clojure and Java) data. In particular, it has meaningful semantics for every possible input value although it only has "interesting" semantics for certain runtime shapes.

That's easy to write in Haskell.

https://gist.github.com/tel/bb84fcc3f1b7488b53349156284b509a

Your code doesn't compile. I can fix the obvious typos and missing imports and language pragma, but the type errors that remain are beyond my knowledge to correct.

Apologies, quick sketch in an airport between flights. May fix this later when I’ve actually got an internet connection.

I fixed the type errors in what I presented before. Little changed: I had to fix the typos, bad imports, and missing pragmas, and then I had to instantiate Val as Hashable and Eq, but since all things inside of Val are Hashable and Eq it was straightforward.

https://gist.github.com/tel/bb84fcc3f1b7488b53349156284b509a

Can you give an example of use? It's not clear to me how this interacts with standard Haskell data structures. If I have an existing map, do I need to walk the tree and encase everything in a `Val`, and vice versa when I want to pull values out?

It doesn’t really. I’m not claiming this works with standard Haskell practice. Typed techniques don’t translate directly to untyped things.

The act of traversing each time is “forgetting”/“synthesizing” type information and is exactly the issue. Dynamic code destroys type information.

"It doesn’t really. I’m not claiming this works with standard Haskell practice."

Then I don't understand where you disagree with me. I'm not saying assoc-in is impossible; just that it's impractical.

We can write assoc-in with dynamic types, but that doesn't integrate with existing functions, and is generally a pain to work with. Alternatively we can try and to statically type it, but then we run into the limitations of Haskell's type system.

assoc-in is a solution that doesn't really work in Haskell, because the constraints of the language prevent it. Adding static typing to a language adds practical limitations in exchange for compiler guarantees.

I disagree it’s impractical—it’s just not valuable. Assoc-In reads as convenient to you, and it is if you’ve already thrown away type information, and reads as destructive to me, a force for destroying information.

Lenses aren’t better because they’re inconvenient but happen to work with types. They’re better because they properly relate to the typing context and persist important information. Lenses in dynamically typed languages don’t exploit this fact and usually are implemented in a way that’s “easy” but destructive.

What you see as practical limitations are seen by me as practical advantages. What you see as convenience and power I see as loss and destruction.

To my eyes, the reason is that you’re most interested in abilities that help you fluently write programs/create values. I’m interested in balancing the power to create with the power to analyze. I want my programs to have meaning both as runtime interpretations and as logical statements. I can choose other type systems to satisfy this balance, but if you just side with “power to create” then I think you lose big.

"What you see as practical limitations are seen by me as practical advantages. What you see as convenience and power I see as loss and destruction."

That's not quite how I see things: I see static typing as a constraint that trades solutions for guarantees.

"To my eyes, the reason is that you’re most interested in abilities that help you fluently write programs/create values. I’m interested in balancing the power to create with the power to analyze."

I don't believe that power and convenience should be pursued above all other considerations; if I did, do you think I'd use a language where data structures are immutable by default? Immutability is a significant constraint, yet clearly I think it worth the cost.

Constraints like static typing and immutability are useful only if the guarantees they deliver are worth more than the solutions they remove. You say that assoc-in is "not valuable", because it cannot easily be written without discarding type information; it's a net loss, because type information is more valuable to you.

Where we ultimately disagree, I think, is the value we place upon static types. I don't think they're particularly valuable at all. Their cost hugely exceeds their usefulness, which to my mind is minor at best, and non-existant at worst.

But my problem is not that you disagree with me over how valuable static types are, but that you seem to think they're not a trade-off. Forgive me if I've misunderstood you, but you don't seem to acknowledge that static types have any disadvantages associated with them at all.

> Their cost hugely exceeds their usefulness, which to my mind is minor at best, and non-existant at worst.

This value difference is indeed core. I value them exactly as "information that can be discerned from reading a program without having to try to execute it in your brain". There is a cost to retaining this information in that there exist programs which have operational meaning but lack this structure. At the same time, I think that this information is incredibly valuable.

So, yes, if you don't see the benefit then there's little more to say.

Honestly, at this point if you’d like to keep chatting, would you mind emailing me? I’d like to discuss these ideas further if it’s of interest.

We might be at the point where we should to agree to disagree. It's interesting to debate a point, particularly since it forces me to justify my viewpoint to myself as well as to you, but I think the discussion may have run its course. :)

Reply on news.ycombinator.com