New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Scalaz 8 Roadmap #1526

Open
jdegoes opened this Issue Nov 22, 2017 · 41 comments

Comments

Projects
@jdegoes
Copy link
Member

jdegoes commented Nov 22, 2017

Checklist

  • Core
    • Type
      • Leibniz
      • Liskov
      • AList
      • ...
    • Data
      • IList — Current version not functional
      • Maybe
      • Iso
      • Disjunction
      • Heap
      • Map
      • These
      • NonEmpty — Replaces OneAnd and NonEmptyList (type Nel[A] = NonEmpty[List, A])
      • Array — This has questionable value outside ST
      • Fingertree
      • EphemeralStream
      • ...
    • Category Theory
      • Functor Hierarchy
        • ...
    • Effects
      • ApplicativeAsk
      • ApplicativeError
      • ApplicativeLocal
      • FunctorListen
      • FunctorTell
      • MonadState
      • ...
    • Abstract Algebra
      • Magma
      • Quasigroup
      • Monoid
      • Semigroup
      • Group
      • AbelianGroup
      • Ring
      • QuotientRing
      • Field
      • Module
      • VectorSpace
      • RingAlgebra
      • FieldAlgebra
      • AssociativeAlgebra
      • LieAlgebra
      • LieGroup
      • Lattice
      • BoundedLattice
      • Semilattice
      • JoinSemilattice
      • MeetSemilattice
      • HeytingAlgebra
      • BooleanAlgebra
      • LieGroup
      • ...
    • Other CT
      • ...
  • Syntax
    • Zero-cost, by-name syntax macros
    • ...
  • IO
    • IO
    • IORef
    • RTS (JVM)
    • RTS (JS)
    • Fallible
    • Terminatable
    • Foreign
    • Effect
    • ...
  • Documentation
    • Examples
      • scalaz.effect
    • Scaladoc
      • scalaz.effect
    • README.md
      • scalaz.effect
  • Test
    • ScalaProps
      • Port to Scalaz 8
      • Remove Arbitrary
      • Add Shrinking
      • Add Exhaustivity
    • Algebra
    • Category Theory
    • Mutable
    • IO
    • Effects
  • Benchmark
    • scalaz.effect.IO
    • scalaz.effect.IORef
    • scalaz.typeclass.Equal
    • scalaz.typeclass.Ord
    • ...
  • Design Guide

  • Third-Party
    • scalaz-deriving
    • scalaz-nio

Overview

Core

Data

Needed: Someone to spearhead this work.

Functor Hierarchy

The Scalaz 8 functor hierarchy needs to be generalized to minimize the number of new abstractions needed to capture distinctions between different types of functors.

A more generic encoding of functor, more faithfully following category theory, will allow custom arrows and refined objects.

While the scope and nature of these changes is TBD, one useful suggestion by @ekmett is to factor out Productive and Coproductive classes:

trait Productive[F[_]] {
  def product[A, B](fa: F[A], fb: F[B]): F[(A, B)]
  def unit: F[Unit]
}
trait Coproductive[F[_]] {
  def coproduct[A, B](fa: F[A], fb: F[B]): F[A \/ B]
  def counit: F[Void]
}

These abstractions permit more sharing between, for example, an invariant applicative and a covariant applicative, reducing the number of type class variations that would otherwise have to exist.

Similarly, modeling Bind as F[F[A]] => F[A] (rather than (F[A], A => F[B]) => F[B])) allows many more types of monads to exist.

Lead: @alexknvl

MTL

Type classes to describe all classes of effects. Unlike MTL, constraints should be minimized (e.g. Functor or Apply / Applicative when possible, Monad only when necessary), and as a result, names will differ substantially from Haskell.

While the type classes are essential, the dirty secret in Scala is that actual monad transformers do not perform well and are not a realistic solution for most code. An alternative to stacks of monad transformers that is better suited to Scala must be developed.

Needed: Someone to spearhead this work.

Algebra

Needed: Someone to spearhead this work.

Other CT

Syntax

Effect

Lead: @jdegoes

Mutable

High-performance ST-based mutable data structures and constructors allowing importing impure Scala code to directly manipulate mutable data structures. Instances for MTL type classes.

Needed: Someone to spearhead this work. @jdegoes ?

Documentation

Comprehensive documentation, readmes, and examples for all data types and abstractions in Scalaz 8.

Test

Benchmark

The benchmark package should help ensure Scalaz 8 encoding techniques, data structures, and effect systems are competitive with other techniques, up to the limits of the design goals.

Design Guide

Scalaz 8 needs a design guide that can ensure uniform standards are followed.

An initial version of the Design Guide can be found here.

  • Policies for laws — algebraic and operational
  • Policies for eager / lazy
  • Policies on overloading
  • Policies for variance (Invariance?)
  • Policies for polymorphic values (Pascal)
  • Policies for naming conventions
    • Instances, classes, etc.
  • Policies for impure code
    • OK to accept if RT (e.g. lift into IO), not OK to return
    • OK to hide fast impure code beneath pure interface
  • Policies for PartialFunction
  • Detailed guide on type class encoding
  • Policies on native methods vs. extension methods
  • Detailed guide on syntax encoding

Needed: Someone to spearhead this work.

Third-Party

Scalaz-Deriving

Machinery to derive type classes automatically given instances supplied by the type class author.

Lead: @fommil

Scalaz-Nio

Type safe, minimal interface to Java NIO, including cost-free newtype wrappers for mutable data types.

@jdegoes jdegoes added the scalaz8 label Nov 22, 2017

@jdegoes jdegoes added this to To Spec in Scalaz 8 Nov 22, 2017

@jdegoes

This comment has been minimized.

Copy link
Member Author

jdegoes commented Nov 22, 2017

TODO: Port over these notes from @aloiscochard

@fommil

This comment has been minimized.

Copy link
Contributor

fommil commented Nov 22, 2017

Deriving will need iotaz if it is to be part of core, so perhaps best left as an addon module?

@TomasMikula

This comment has been minimized.

Copy link
Member

TomasMikula commented Nov 22, 2017

Can you expand on this?

Similarly, modeling Bind as F[F[A]] => F[A] (rather than (F[A], A => F[B]) => F[B])) allows the question of arrow type to be deferred and isolated to map in the corresponding type of functor.

@jdegoes

This comment has been minimized.

Copy link
Member Author

jdegoes commented Nov 22, 2017

@fommil Sure, it can live anywhere, although there are other reasons to consider including iotaz (composable error sets, for example). I view some of the other major areas as potentially existing elsewhere, in different repos.

@TomasMikula The current definition of Bind marries it to covariant functors. But if you modify the definition as suggested, then if you want a covariant monad, you combine Functor with Bind, and if you want an invariant monad, you combine Invariant with Bind.

@jdegoes

This comment has been minimized.

Copy link
Member Author

jdegoes commented Nov 22, 2017

Btw, to all Scalaz contributors: Please feel free to add to, edit, amend, and fill in!

@emilypi

This comment has been minimized.

Copy link
Member

emilypi commented Nov 22, 2017

Have we enumerated what's going to be included in data yet, or is it, or do we just have List and Map outstanding currently

@Jacoby6000

This comment has been minimized.

Copy link
Contributor

Jacoby6000 commented Nov 22, 2017

There's definitely a lot missing from that list. I know for sure it is missing OneAnd, NonEmptyList, These/Ior, and some sort of Array backed collection.

@TomasMikula

This comment has been minimized.

Copy link
Member

TomasMikula commented Nov 22, 2017

There was a proposal to have 2 versions of some data types: a direct, fast, but stack-unsafe encoding, and a slower but stack-safe encoding. Applies to e.g. State monad.

@jdegoes

This comment has been minimized.

Copy link
Member Author

jdegoes commented Nov 22, 2017

@TomasMikula We have discussed something even more radical, which is to not have the State monad at all, but only the type class MonadState or rather ApplicativeState (I suppose). Let's discuss sometime w/ @edmundnoble on the private http://gitter.im/scalaz channel.

@NeQuissimus

This comment has been minimized.

Copy link
Member

NeQuissimus commented Nov 22, 2017

Should we maybe convert the example project to use tut, so that Markdown can be used to explain certain pieces of code, thereby providing rich documentation?

@TomasMikula

This comment has been minimized.

Copy link
Member

TomasMikula commented Nov 22, 2017

👍 for tut. Is there a way to automate the process of publishing tuts with every build?

@NeQuissimus

This comment has been minimized.

Copy link
Member

NeQuissimus commented Nov 22, 2017

I have only ever done this for an internal project (on GitHub Enterprise) and we have our build server build the documentation, then commit it into a separate repo, whose contents we expose via GitHub Pages. The separate repo was mostly to keep the tut commits out of our code history.

I am unaware of a better way but surely there must be one :D

@jdegoes

This comment has been minimized.

Copy link
Member Author

jdegoes commented Nov 23, 2017

@NeQuissimus Sounds like a great idea. 👍

@caente

This comment has been minimized.

Copy link

caente commented Nov 27, 2017

Could you elaborate a bit more on the Algebra entry?

@jdegoes

This comment has been minimized.

Copy link
Member Author

jdegoes commented Nov 28, 2017

@caente I think this is a catch all for abstractions from abstract algebra, including things like Semigroup, Lattice, Field, and Ring. I have sketched some detail out above, and I think we can take inspiration from PureScript's hierarchy (and some work has been done in Scala, as well, in Spire and other libraries). Any interest in contributing to this one? 😁

@caente

This comment has been minimized.

Copy link

caente commented Nov 28, 2017

@jdegoes I was hopping you would say that. I'm definitely interested in contributing. From what you say it seems like there isn't even a desired roadmap? I don't think my abstract algebra kung fu is enough for planing an strategy/hierarchy.
Although perhaps it could be enough to "copy" PureScript as you said?
Do you have experience with Spire's algebra? Any reason for not follow a very similar path to theirs?

@vmarquez

This comment has been minimized.

Copy link
Member

vmarquez commented Nov 28, 2017

@caente would be awesome to have someone tackle this in depth! One thing to keep in mind though is that it may make sense to decide how we want to do laws first. Algebraic structures such as Group, Semigroup, Monoid, SemiLattice, etc. all look pretty similar with different laws... hence why when I added SemiLattice to 7.3.x, I didn't add to Scalaz8. Food for thought. :)

@puffnfresh

This comment has been minimized.

Copy link
Member

puffnfresh commented Nov 28, 2017

@caente copy PureScript

@dchenbecker

This comment has been minimized.

Copy link
Contributor

dchenbecker commented Nov 28, 2017

Would improving scaladoc be considered part of "Examples"?

@jdegoes

This comment has been minimized.

Copy link
Member Author

jdegoes commented Nov 28, 2017

@caente I can definitely help out with that (as can others). As @puffnfresh says, starting with the PureScript hierarchy would be a good first step. It's not quite fine-grained enough but it has the right general shape. There is overlap with Spire but Spire contains "non-things" like Trig which would definitely not be desired in an abstract algebra package.

@dchenbecker I rewrote that section to be Documentation, which now contains Scaladoc, examples, and README.md. Any contributions to any of these would be enormously beneficial.

Also: hi! 😄

@caente

This comment has been minimized.

Copy link

caente commented Nov 28, 2017

@jdegoes @puffnfresh I've been looking into purescript docs, and their algebra typeclasses seem to be distributed among several modules:

I find strange that Ring and Semigroup are in prelude, but Group and Monoid and in different libs... wouldn't we want that Ring to be "composed" with abelian group and monoid, for example?

what would be the advantage of such non-hierarchical hierarchy?

@puffnfresh

This comment has been minimized.

Copy link
Member

puffnfresh commented Nov 28, 2017

@caente Ring and Semigroup are there because that's where (+) and (-) come from. Prelude without (+) and (-) would be a bit weird! You'll also see Semiring and EuclideanRing for (*) and (/)

@puffnfresh

This comment has been minimized.

Copy link
Member

puffnfresh commented Nov 28, 2017

@caente yeah, I think you're right, don't copy this part!

@caente

This comment has been minimized.

Copy link

caente commented Nov 28, 2017

thanks @puffnfresh, on the other hand this seems like a nice guide http://a-guide-to-the-purescript-numeric-hierarchy.readthedocs.io/en/latest/

I see, there are Monoid and Semigroup, so it seems to make sense to implement groups and abelian group, and then rings and fields?
but also, I don't see any Monoid or Semigroup instances in scalaz8, nor tests nor laws... am I missing something? why are they checked off?

Any thoughts on how to enforce laws? I see that in the current version of scalaz they are "built-in" on the typeclass itself, e.g. https://github.com/scalaz/scalaz/blob/series/7.3.x/core/src/main/scala/scalaz/Monoid.scala#L69-L82
I don't see any tests of that kind on scalaz8, is there a consensus about it?

btw I'd love to hear of any use cases for these typeclasses...

@jdegoes

This comment has been minimized.

Copy link
Member Author

jdegoes commented Nov 28, 2017

@caente For now, I wouldn't worry about enforcing laws. The laws can be described in comments. Ultimately we want to add them as methods on the type classes, like Scalaz 7, but possibly closer to what Cats is currently doing, which is representing laws as data (case class IsEq[A](lhs: A, rhs: A), with <-> syntax for construction).

You are also right that PureScript makes some tradeoffs when it comes to the Prelude and also how fine-grained the hierarchy is. That's why we don't want to just copy wholesale, although it's a good place to start. See also the abstractions I posted above, Algebra (possibly the Gold Standard?), Spire, Cats Algebra, and of course Wikipedia and other free resources.

@jdegoes

This comment has been minimized.

Copy link
Member Author

jdegoes commented Nov 29, 2017

@caente I found Edward Kmett sketched out a hierarchy here. It uses a someone non-idiomatic style of Scala but looks clean and well put together (Kmett also wrote Algebra for Haskell).

@caente

This comment has been minimized.

Copy link

caente commented Nov 29, 2017

@jdegoes last night I began implementing Group in terms of monoid, then I saw Kmett's code and I was intimidated and confused: The code seems bottomless. Hence I repeat the question I asked before: are there use cases we want to prioritize? I imagine we don't exactly want to use scalaz to proof theorems, but rather to automate certain operations?
I'm afraid I'm not the target audience for these typeclasses, but still wanna help.

@jdegoes

This comment has been minimized.

Copy link
Member Author

jdegoes commented Nov 29, 2017

@caente Well, let's start with something simple then:

  • Abelian
  • Commutative
  • Group
  • Loop
  • Magma
  • Module
  • Monoid
  • Quasigroup
  • Rig
  • Ring
  • Ringoid
  • Semigroup
  • Semiring

This is a decent foundation and we can tweak or add other things (Lattice and friends) later. I can also sketch out the relationships between these, if you like (though it's all available above in the stated references). For example, Semigroup is a Magma, and so forth.

@vmarquez

This comment has been minimized.

Copy link
Member

vmarquez commented Nov 29, 2017

@jdegoes I'm most interested in SemiLattice, does that not belong on the list? They're very useful for distributed systems. (Idempotency + commutativity)

@TomasMikula

This comment has been minimized.

Copy link
Member

TomasMikula commented Nov 29, 2017

I'm also more interested in lattice-like structures than ring-like structures.

@jdegoes

This comment has been minimized.

Copy link
Member Author

jdegoes commented Nov 29, 2017

@vmarquez @TomasMikula I think we need them all, but we need to start somewhere. 😄

@caente

This comment has been minimized.

Copy link

caente commented Nov 30, 2017

@jdegoes I'll make a first stab at this tomorrow, it will probably be lacking, but I don't think I'll need anything else for now, between Kmett's code and Pinter's book I could be fine.

@garyb

This comment has been minimized.

Copy link

garyb commented Nov 30, 2017

@vmarquez @jdegoes If you add Idempotent you can get Band (Semigroup + Idempotent) and then Semilattice (Commutative + Band).

@jdegoes

This comment has been minimized.

Copy link
Member Author

jdegoes commented Dec 1, 2017

@caente Awesome, let me know if you run into any trouble!

@garyb Hehe. Thanks. Good to see you around these parts! 😄

@fommil

This comment has been minimized.

Copy link
Contributor

fommil commented Dec 1, 2017

What about a decent test library? It's still an open gap in FP... imagine a suite of matchers like scalatest that uses Equal and Order, and maybe even a "choose your Monad" runner so you could write Id tests, Either tests, or IO tests. With structural diffs of things that don't match the expectations. Maybe even macros to easily create "mock" versions of a finally tagless algebra backed by an mvar.

@tonymorris

This comment has been minimized.

Copy link
Member

tonymorris commented Dec 1, 2017

If you are going to do a decent test library, look at hedgehog.

https://hackage.haskell.org/package/hedgehog

Don't copy quickcheck/scalacheck. You'll be way ahead of anything else that exists for Scala.

IMO.

@caente

This comment has been minimized.

Copy link

caente commented Dec 1, 2017

@jdegoes @vmarquez @garyb @TomasMikula @puffnfresh I oppened this PR #1551 to move the conversation there, if possible I rather add small changes at a time.
Do let me know if you think we should start a "lower level".

@NeQuissimus

This comment has been minimized.

Copy link
Member

NeQuissimus commented Dec 2, 2017

@tonymorris @fommil I would be very interested in this actually. I just figured it would be beyond the Scalaz 8 scope. There is scala-dedgehog but I have never used it. In #1540 @jdegoes mentioned that ScalaProps is meant to become part of Scalaz 8, we should definitely keep that in mind.

@jdegoes

This comment has been minimized.

Copy link
Member Author

jdegoes commented Dec 2, 2017

@NeQuissimus @tonymorris Indeed, Hedgehog is my favorite too. ScalaProps is closer than ScalaCheck and can be made closer still, so it's a good base.

@jdegoes

This comment has been minimized.

Copy link
Member Author

jdegoes commented Dec 2, 2017

@fommil It's needed. All the test libraries are non-functional and do not understand functional concepts (e.g. Monad), which makes them difficult to use. Something small but fully integrated into Scalaz can be used for internal tests, but also as a dependency scalaz-test in other projects.

sderosiaux added a commit to sderosiaux/every-single-day-i-tldr that referenced this issue Apr 24, 2018

@edmundnoble

This comment has been minimized.

Copy link
Contributor

edmundnoble commented May 6, 2018

https://github.com/scalaz/testz is now up. It needs Hedgehog-style property-based testing, but for now it should at least let us write laws.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment