Typeclass abstraction to use for data structures?


#1

chexxor [8:29 PM]

rich [10:24 AM]
Is there an abstraction of adding an element to an Array or List, so where
Semigroup.append :: a -> a -> a, you’d have Class.fnname :: a -> f a -> f a
Where f is a Semigroup or a Monoid or something

natefaubion [10:25 AM]
Potentially Alternative
where you have pure :: a -> f a and plus :: f a -> f a -> f a

^ This is an interesting topic. Is there a typeclass which says “a f which can eat my a and from which I maybe get that a back out again”? This sounds like a data structure to me.
Perhaps

class Container f a where
   insert :: a -> f a -> f a
   query :: Query f a -> f a -> Maybe a
type Query f a = (a -> Boolean)
 -- idk about "Query", but you need some way of choosing the `a` to retrieve from the `f`, right?

-- Could define a similar type for these operations occurring in a monad/context
class Container m f a where
  insert :: a -> f a -> m (f a)
  query :: Query f a -> f a -> m (Maybe a)

monoidmusician [8:30 PM]
FoldableWithIndex can provide one method for selecting an element

chexxor [8:32 PM]
Ah, foldable is an interesting idea

monoidmusician [8:32 PM]
but insert is sort of the blindspot of most existing typeclasses
pure with <|> usually works fine though

chexxor [8:35 PM]
Wait, how would <|> apply to this problem?

monoidmusician [8:37 PM]
insert a fa = pure a <|> f a (or the commuted version)

chexxor [8:39 PM]
ah, right
Dang, that’s interesting. I didn’t consider Foldable and Alt to be so analagous to traditional data structure operations

monoidmusician [8:43 PM]
every program is traverse :wink:

chexxor [8:43 PM]
Wait, the Plus class docs say "It is similar to Monoid, except that it applies to types of kind * -> *"
But Monoid’s mempty isn’t annihilitive like that
A law of Plus: Annihilation: f <$> empty == empty

monoidmusician [8:43 PM]
right, you have to consider empty together with <|> to get the Monoid analogy
there is no analogy for that annihilation law in monoid

chexxor [8:44 PM]
Ah, the monoid part is the left identity and right identity laws

monoidmusician [8:47 PM]
I’ve always wondered if f <$> empty == empty is redundant … I suspect it probably just needs id <$> fa == fa and naturality :slightly_smiling_face:

chexxor [8:48 PM]
What is naturality?
ah, natural transformation?

monoidmusician [8:53 PM]
erm I think I mean parametricity, sorry

chexxor [8:54 PM]
that sounds better

monoidmusician [9:02 PM]
we know that id <$> empty = empty, by the law; obviously f <$> empty = (f <<< id) <$> empty, but f cannot apply to any elements of empty (because a is arbitrary in empty :: f a; e.g. absurd <$> empty), so it cannot change the result, obviously, thus we have that f <$> empty = (f <<< id) <$> empty = id <$> empty = empty


#2

I think the problem with most collection abstractions is that they end up being a generalization of List, whose operations are satisfied by existing abstractions like Foldable and Alternative. Alternative lets you produce a functor as if it were a Monoid (and List is the free Monoid), and Foldable lets you consume a functor as if it were a List. It’s hard to distill all the different containers down to something that can be shared and isn’t in essence a List.


#3

Can you think of a different abstraction that could possibly exist to complement Foldable? Maybe something which closer relates to a Tree?


#4

Alternative satisfies that. f a -> f a -> f a takes two branches and merges them into one. Monad also satisfies that. f a -> (a -> f b) -> f b will replace all the leaves in a tree with branches to b.


#5

Cool! Nice example.
So it seems that List and Tree are the only data structure abstractions we need. :wink:
Nah, I bet there’s some other interesting descriptions of traditional data structures using general-purpose, lawful type classes like this. The “Index” ones, like FoldableWithIndex, can describe the cool part of Map/JSObject, for example.


#6

But, I still can’t think of a type class which describes a data structure query, like using an SQL filter to select records from a List (Record row).


#7

https://pursuit.purescript.org/packages/purescript-filterable/3.0.1 perhaps


#8

You can also get inspiration from http://hackage.haskell.org/package/algebraic-graphs for graphs.


#9

Still really, really, really want to see or participate in porting this to PureScript (algebraic-graphs)


#10

This sounds a bit like linq (it’s probably nothing similar but it just triggered some past trauma working on C# MVC :slight_smile:)


#11

Linq is a concrete data type kinda thing and this thread has been about lawful type classes. Just wanted to notify you of the unique interest of the original line of questioning. :+1:


#12

Various monoid plus foldMap(WithIndex) can get you quite far. See this blog post for inspiration: https://lptk.github.io/programming/2018/10/04/comprehending-monoids-with-class.html

Obstacles in PureScript:

  • Currently we don’t have something like Haskell’s monoidal-containers, so you’re stuck with the respective container’s default monoid (Array, List: append, (Hash)Map, (Hash)Set: union).
  • There’s no comprehension syntax. (I actually have a branch with prototype monoid comprehension syntax, if anyone’s interested just ask.)
  • Ideally the compiler would rewrite certain patterns into more efficient operations. For example, if you use naive monoid comprehension to filter an array, you end up appending one element at a time, which gets you quadratic instead of linear complexity.

For construction, there is Unfoldable. The problem with Unfoldable is that it does not work if you need additional constraints like Ord or Hashable, so it doesn’t abstract over all that much, just cons-list-like things.

Last time I looked into this I dug up these references:

There’s a paper by Simon Peyton-Jones and a Haskell library that has an alternative Unfoldable (and Foldable and others) class with two parameters. I’m not sure what became of that approach.

There is also a (potentially vaporware?) data structures library by Chris Okasaki, described here:
https://doi.org/10.1016/S1571-0661(05)80546-8

Also Kiselyov, et al.
https://doi.org/10.1145/1017472.1017488

Peter Buneman did some work on bags, sets, and multisets and how they relate.

Torsten Grust worked on monad comprehensions, IIRC.

Jeremy Gibbons has something on comprehending ringads in Wadler’s Festschrift.
Also some recent work on categories, adjoints, and relational algebra which might or might not be relevant: https://www.cs.ox.ac.uk/jeremy.gibbons/publications/reladj.pdf