search

byorgey / enumeration

Simple Haskell package for efficiently indexable finite and infinite enumerations.
BSD 3-Clause "New" or "Revised" License
11 stars 2 forks source link

Proposing Profunctor-shaped IEnumeraion #3

Open viercc opened 4 years ago

viercc commented 4 years ago

I propose adding two more types related to Enumeraion and IEnumeraion.

-- Inverse of Enumeration
-- (can be seen as a classification of values of `a`
--  onto a set of integers up to `card`)
data CoEnumeration a = CoEnumeration
  { card :: Cardinality
  , locate :: a -> Index
  }
instance Contravariant CoEnumeration

-- IEnumeration but input and output were separated
data ProEnumeration a b = ProEnumeration
  { card :: Cardinality
  , locate :: a -> Index
  , select :: Index -> b
  }

---- Currently Profunctor is not in base
-- instance Profunctor ProEnumeration

CoEnumeration have (><), (<+>) combinators like Enumeration, and these make it instances of Divisible and Decidable.

A ProEnumeration is a CoEnumeration and an Enumeration with same cardinality bundled in one. It can have (><), (<+>) operations too. These combinators make ProEnumeration an instance of Generic(Unit|Empty|Product|Sum)Profunctor. Additionally, ProEnumeration can be composed each other:

toFunction :: ProEnumeration a b -> a -> b
toFunction e = select e . locate e

compose :: ProEnumeration a b -> ProEnumeration b c -> ProEnumeration a c
compose e1 e2
  | card e1 <= card e2 = rmap (toFunction e2) e1
  | otherwise = lmap (toFunction e1) e2

IEnumeration a can be characterized as e :: ProEnumeration a a with additional guarantee toFunction e = id.

I'm not strongly proposing about making them actually an instance of Divisible and Profunctor etc. They are parts of packages with heavy dependencies, and they're not really lawful instances if infinities are involved.

Those types are translation of what I've been making as a part of my pet project. I found (a type analogous to) your Enumeration and the proposed types useful, and was surveying Hackage for already written packages.

If you think they'll worth adding, I'm willing to write PR.

byorgey commented 4 years ago

Hi @viercc , thanks so much! This sounds like a great idea. I'm always happy to add more categorically-inspired things, especially if they don't change the API of the existing types (and sometimes even if they do). If you wanted to write a PR that would be great.

viercc commented 4 years ago

Thank you too! I'm starting translation, but I want to ask some details:

byorgey commented 4 years ago

Contravariant, Divisible, Decidable make sense to add. As for Profunctor, I'm not sure. Let's add the other ones first and then see what it would look like to add Profunctor.

I like the names CoEnumeration and ProEnumeration.

On Mon, Sep 7, 2020 at 9:16 PM Koji Miyazato notifications@github.com wrote:

Thank you too! I'm starting translation, but I want to ask some details:

-

How many dependencies for type classes?

  • Contravariant: Already in base, but only since base-4.12.0 (GHC 8.6). It seems this package currently available for older versions of GHC (GHC-8.0?). To support older GHC, contravariant https://hackage.haskell.org/package/contravariant is needed. It's a lightweight package. (I said it has large dependencies but I remembered it wrong.)

  • I named CoEnumeration and ProEnumeration with casual one-minute thought. Do you think they make sense?

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/byorgey/enumeration/issues/3#issuecomment-688578636, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAECKYZDKSIWLWSA2HFUTNDSEWHZTANCNFSM4Q6GYCNA .

viercc commented 4 years ago

Thank you for the review and merge. I commented to the PR page I want Data.Enumeration.Invertible module to be rewritten using ProEnumeration, so tried to make an update:

https://github.com/viercc/enumeration/tree/feature-invertible-by-proenumeration

But it didn't go well in terms of API design, so I want to discuss what to do now.

It became clear that what I made as ProEnumeration is, while using the same representation (the triple (Cardinality, Index -> a, a -> Index),) quite different to what your IEnumeration is.

For what I was making in ProEnumeration, locate part of them are total function a -> Index, but what IEnumerations hold are functions a -> Index which are guaranteed to be correct (or even terminate) only for enumerated values.

As the result of this mismatch, my attempt (the above link) had to distort your original API in surprising way. Notably, finiteList :: [a] -> IEnumeration a was changed to [a] -> IEnumeration (Maybe a).

Because locate must be total, it had to assign some special index for non-enumerated values. That special index must correspond to a value not enumerated in the given list. That is not possible for generic type a, so I changed the enumerated type from a to Maybe a like the following:

finiteList "abc" :: [Char] -> IEnumeration (Maybe Char)
=======================================================
Nothing  -> 0 -> Nothing
Just 'a' -> 1 -> Just 'a'
Just 'b' -> 2 -> Just 'b'
Just 'c' -> 3 -> Just 'c'
Just _   -> 0 -> Nothing

Considering the vast overlap of enumeration/reverse-indexing algorithm, I don't want to just give up on the current status of code duplication. For example, functionOf for IEnumeration is a special case of proenumerationOf for ProEnumeration. Also, I think it will be really unfriendly to users other than me, to include two quite similar but fundamentally different set of APIs.

In my motivating use-case, all ProEnumerations were constructed from unit and void using combinators like (<+>), so its locate were automatically total function.

How should I (would you) proceed?