Have people seen many programming languages where Sets are represented as functions from X → Bool and (more importantly) Lists are represented as functions from Int → X? And I mean they're truly just functions: all of the operations upon them are just operations upon functions, and thus they might be repurposed for other uses as well. Javascript and Lua kind of do this, except their philosophy is more like "all collections are just dictionaries", where a dictionary is a heavily-restricted class of function. This approach ("all collections are just functions") seems like a versatile foundation (especially in the context of the semantics of the programming language I'm working on), so I've been digging into the ramifications of it lately. My biggest challenge so far is figuring out how to identify for which functions operations like set union and intersection are computable. Depending on how the function is constructed/defined, it seems like it could be quite hard to figure out a static "safety check". I want these operations to be well-defined even on recursively-defined functions, so it's not as simple as "ensure the function definition is just a finite list of cases" (i.e, a dictionary). This doesn't seem unreasonable: Datalog works this way. Datalog predicates are recursively-defined functions from X → Bool (i.e. sets) that obey certain constraints so that queries upon them are answerable.

clojure

People do this kind of thing in haskell/other FP languages sometimes (although I don't have an example at hand right now). The biggest question is: how do you support other operations than construction or membership? I.e. set size, or more generally, iteration? Lists like you represent them have a similar problem. If you want to iterate, at what index will you start and end? Representing collections as functions is something that people tried to figure out in the lambda calculus a lot. You might be interested in e.g. fold lists.

Yeah, figuring out how to do the operations is interesting! One possibility I'm considering is identifying classes of function where the codomain has some "zero value", and allowing the range of those functions to be summed if the domain maps to finitely-many non-zero values. These conditions are obeyed by finite sets, and by finite lists whose codomain is a "Maybe" type (sets of size 0 or 1). "Safe" functional languages already handle list indexing using Maybes, so it doesn't seem that bizarre. It does seem a little bit hacky though!

You’re probably familiar with Conal Elliot? A lot of his work seems to focus on this idea (representing data & operations as functions / combinators). I don’t know of many languages that do this, though, probably for efficiency reasons. Adding an element to a set means allocating a new closure.

Yeah, I know some of Conal Elliot’s stuff. I’m not sure if he’s addressed the above ideas; I’ve only seen his stuff on recursive algebraic data types, which these are not. I’m avoiding/disowning ADTs in my language. And to be clear, I’m not interested in exploring mathematical curiosities and publishing a library or a paper, I’m interested in building a practical programming language, so the constraints of existing language implementations aren’t of concern to me. A language designed around data structures being encoded as functions isn’t going to be allocating millions of closures every second. Functions are just the interface; the implementation can do anything semantically equivalent!

set-size(my_set)

, where

set-size

is implemented by dynamic dispatch on its argument. This also reminds me of the idea of records as (dependently typed) functions from a key type to whatever thing the struct was constructed with (or updated with? Hmm).

I'm reminded of Barry Jay's Pattern Calculus. If on the one hand a hash table is a bunch of key, value pairs and, on the other, a standard lambda takes anything and uses it to come up with something else, you can imagine a pattern as living somewhere between: takes some things and uses them to come up with a value. Given two patterns you can glue them together. The standard way is that if the first one matches you take it, otherwise check the second one. Not sure what he's been up to in the last while https://scholar.google.com/citations?hl=en&user=eWreFm4AAAAJ&view_op=list_works&sortby=pubdate.

@wtaysom I looked into Barry Jay’s stuff a while ago and remember not being impressed. Is there something that patterns are better than functions at expressing? One can already compose functions in many different ways.

Well, not at all in an important sense, but kind of depending on your domain. Patterns here basically amount to partial functions. So if your domain happens to be all about partial functions (that's me sometimes where I end up using a lot of tables), then there's something to find here. But it's not going to be anything more than having a few functions for nicely composing

a -> Maybe b

, generally. I guess a potential important difference can be whether you want to model order. For instance, Rubyist that I am, the keys in a

Hash

are ordered and I use this all the time. In another context, you may not want to keep that information around. Another thought that I had while trying to remember the pattern calculus is why prefer a composition operator like this

<+> :: (a -> Maybe b) -> (a -> Maybe b) -> (a -> Maybe b)
(f <+> g) x = f x `orElse` g x

over something that collects all the results:

<*> :: (a -> [b]) -> (a -> [b]) -> (a -> [b])
(f <*> g) x = f x ++ g x

And so on.

@wtaysom Partial functions are my mortal enemy 😇. It’s a strict requirement that my programming language only permits total functions. The challenge is then making it expressive enough that you never feel you “need” a partial function somewhere!