[rebeccaskinner]

I've recently started writing a series of blog posts (https://rebeccaskinner.net/posts/2024-10-18-dictionaries-are...) trying to explain the idea and my approach has been to explain the idea using comprehensions. I haven't had a lot of people review the post yet, and I still have at least one if not two more follow-ups before it's done, so I'm not yet sure how well the idea will land.

[magicalhippo]

Nice introduction. Still not entirely sold that dictionaries are pure functions, though.

Will you be covering common dictionary operations like adding/removing elements and iterating over the dictionary keys?

I have some ideas on how one might frame it in a pure function setting but they all seem quite contorted in a similar way to your incrementDict, ie you'd never actually do that, so curious if there are better ways. Then maybe you'll sell me on the premise.

[rebeccaskinner]

I'm really focusing less on the idea that Dict the data type with it's associated methods is like a function, and more on the idea that a dictionary in the general sense is a mapping of input values to output values, and you can think of functions that way.

That said, there are some pretty reasonable analogies to be made between common dictionary operations and functions.

For example, adding and removing items can be done with function composition so long as you are okay with partial lookups. Here's a really short example I put together:

  module Example where
  import Control.Applicative

  type Dict a b = Eq a => a -> Maybe b

  emptyDict :: Dict a b
  emptyDict = const Nothing

  singleton :: a -> b -> Dict a b
  singleton k v target
    | k == target = Just v
    | otherwise = Nothing

  unionDict :: Dict a b -> Dict a b -> Dict a b
  unionDict dict1 dict2 k = dict1 k <|> dict2 k

  insertDict :: a -> b -> Dict a b -> Dict a b
  insertDict k v dict = singleton k v `unionDict` dict

  removeDict :: a -> Dict a b -> Dict a b
  removeDict k dict target
    | k == target = Nothing
    | otherwise = dict k

This particular representation of dictionaries isn't necessarily something you'd really want to do, but the general approach can be quite useful when you start working with something like GADTs and you end up with things like:

  data Smaller a where
    SmallerInt :: Smaller Int
    SmallerBool :: Smaller Bool
  
  data Larger a where
    LargerInt :: Larger Int
    LargerBool :: Larger Bool
    LargerString :: Larger String
  
  someLarger :: Larger x -> x
  someLarger l =
    case l of
      LargerInt -> 5
      LargerBool -> True
      LargerString -> "foo"
  
  embedLarger ::
    (forall x. Larger x -> Smaller x) ->
    (forall smallerI. Smaller smallerI -> r) ->
    (forall largerI. Larger largerI) -> r
  embedLarger mapping fromSmaller larger = fromSmaller (mapping larger)

(I'm actually co-authoring a talk for zurihac this year on this pattern, so I have quite a bit more to say on it, but probably not ideal to cram all of that into this comment).

[magicalhippo]

> and more on the idea that a dictionary in the general sense is a mapping of input values to output values, and you can think of functions that way.

So what's the difference between a map and a dictionary then?

> Here's a really short example I put together

Much appreciated. I don't really know Haskell (nor any other functional language), but I'm pretty sure I understood it.

> This particular representation of dictionaries isn't necessarily something you'd really want to do

Yeah that's pretty much what I had in mind, and yes it's possible but it feels forced. For one you're not actually removing an element, you just make it impossible to retrieve. A distinction that might seem moot until you try to use it, depending on the compiler magic available.

> I'm actually co-authoring a talk for zurihac this year on this pattern

Sounds interesting, will check it out when it's published.

[rebeccaskinner]

> So what's the difference between a map and a dictionary then?

You're asking good questions and catching me being imprecise with my language. Let me try to explain what I'm thinking about more precisely without (hopefully) getting too formal.

When I say "a function is a mapping of values" I'm really trying to convey the idea of mathematical functions in the "value goes in, value comes out" sense. In a pure function, the same input always returns the same output. If you have a finite number of inputs, you could simply replace your function with a lookup table and it would behave the same way.

When I talk about dictionaries, I'm speaking a little loosely and sometimes I'm taking about particular values (or instances of a python Dict), and other times I'm being more abstract. In any case though, I'm generally trying to get across the idea that you have a similar relationship where for any key (input) you get a particular output.

(aside: Literally right now as I'm typing this comment, I also realize I've been implicitly assuming that I'm talking about an _immutable_ value, and I've been remiss in not mentioning that. I just want to say that I really appreciate this thread because, if nothing else, I'm going to edit my blog post to make that more clear.)

The main point is that dictionaries are made up of discrete keys and have, in Python at least, a finite number of keys. Neither of those constraints necessarily apply to functions, so we end up in an "all dictionaries are functions, but not all functions are dictionaries" situation.

> Yeah that's pretty much what I had in mind, and yes it's possible but it feels forced. For one you're not actually removing an element, you just make it impossible to retrieve. A distinction that might seem moot until you try to use it, depending on the compiler magic available.

This is a great example of the kind of thinking I'm trying to address in the article. You're completely right in a very mechanical "this is what memory is doing in the computer" sort of sense, but from the standpoint of reasoning about the problem space deleting an element and being unable to access the element are the same thing.

Of course in the real world we can't completely handwave away how much memory our program uses, or the fact that a function encoding of a dictionary turns a constant time lookup into a linear time lookup. Those are real concerns that you have to deal with for non-trival applications, even in a pure functional language.

The benefit you get, and I apologize because this is hard to explain- let alone prove, is that you can often end up with a much _better_ solution to problems when you start by handwaving away those details. It opens up the solution space to you. Transformations to your architecture and the way you think about your program can be applied regardless of the specific representation, and it's a really powerful way to think about programming in general.

[magicalhippo]

Thanks for the detailed responses, highly appreciated.

I taught myself programming as a kid using QBasic, and quickly moved on to Turbo Pascal and assembly, so clearly my programming career was doomed from the start[1].

For one I do like to keep in mind how it will actually be executed. The times I've not done that it has usually come back to bite me. But that perhaps hampers me a bit when reading very abstract work.

That said I like going outside my comfortable box, as I often find useful things even though they might not be directly applicable to what I normally do. Like you say, often changing the point of view can help alot, something that can often be done in a general way.

Anyway, looking forward to the rest of the article series and the talk.

[1]: https://en.wikiquote.org/wiki/Edsger_W._Dijkstra#How_do_we_t...

[mncharity]

Interesting. I liked how "Dictionaries are Pure Functions" set up currying as JSON nested dictionaries.

Curiously, I've a backburnered esolang idea of gathering up the rich variety of dict-associated tooling one never gets to have all in one place, and then making everything dict-like. Permitting say xpath sets across function compositions.