undefined | Better HN

0 pointsdllthomas3y ago0 comments

There is a reason in principle that you can't build a Set Monad that works that way: it violates the functor laws.

In order to be a functor, you need `fmap (f . g) == fmap f . fmap g`.

The problem is that some functions (for instance, Data.Set.showTree) can produce different results for two values that compare equal.

For instance, imagine we have a set containing (only) the lists `[1,2]` and `[2,1]`; let's call it s. How many elements are in `fmap (Data.Set.showTree . Data.Set.fromList) s`? Two, because the result of fromList winds up being order dependent in the structure of the internal tree, even though both Sets represent the same set of values. On the other hand, how many elements in `fmap showTree . fmap fromList`? Just one, because the Set has a chance to "see" the output of fromList and notice that they are equal according to Eq.

Does this violation of the functor laws matter? Maybe; likely not; it depends on your use case.

But mathematically it means that the thing we are working with is not a functor, and so the thing we are working with is also not a monad (as all monads are functors).

0 comments

shikoba3y ago

İ prefer to say that show tree violates the abstraction. You can have s1=s2 but not f(s1)=f(S2). So f (show tree) is not a real function (or = is not a real equal). But showtree is a debug function, it doesn't count. İt's like saying in C that a=13 and b=13 isn't a real equality because &a and &b are not equal. There is the underlying structure and the structure after the equivalence. You have to know of what you're talking.

dllthomasOP3y ago

I'm not unsympathetic to that position, but I think it's ill advised to take it as far as "Functor means functor up to Eq". I grant that showTree in particular is a debug function that will usually be called at the end of any meaningful computation, and handwaving it in particular away is probably fine. I don't think we can say the same of something like splitRoot, which instead breaks the abstraction for the sake of efficiency.

> You have to know of what you're talking.

And the language (/ecosystem) gives you no way of specifying, so we have to be somewhat conservative. I've actually been thinking (partly driven by trains of thought such as under discussion here) that it might be very interesting to have a language that let you reason explicitly about different sorts of equality (tentatively defined, in the context of the language, as indistinguishability relative to some interface).

shikoba3y ago

It's called math.

j / k navigate · click thread line to collapse

0 pointsdllthomas3y ago0 comments

There is a reason in principle that you can't build a Set Monad that works that way: it violates the functor laws.

In order to be a functor, you need `fmap (f . g) == fmap f . fmap g`.

The problem is that some functions (for instance, Data.Set.showTree) can produce different results for two values that compare equal.

Does this violation of the functor laws matter? Maybe; likely not; it depends on your use case.

But mathematically it means that the thing we are working with is not a functor, and so the thing we are working with is also not a monad (as all monads are functors).

0 comments

shikoba3y ago

dllthomasOP3y ago

> You have to know of what you're talking.

shikoba3y ago

It's called math.

j / k navigate · click thread line to collapse