Where communities thrive


  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
People
Repo info
Activity
Andi Miller
@andimiller
which version of cats-effect are you on?
Paulius Imbrasas
@CremboC
0.5
Andi Miller
@andimiller
works for me with import cats._, cats.implicits._, cats.effect._
@ Monoid[IO[Option[Int]]].empty 
res1: IO[Option[Int]] = IO(None)
Paulius Imbrasas
@CremboC
hmm looks like I have to do import cats.effect._ instead of import cats.effect.IO, i.e. IO is not enough
Fabio Labella
@SystemFw
@CremboC do you have -Ypartial-unification on?
Paulius Imbrasas
@CremboC
yup
I just changed ^^ and it works
Fabio Labella
@SystemFw
mmm
that's weird
the instance is mixed in the companion object of IO, it should not require an import to be visible
Paulius Imbrasas
@CremboC
huh, even weirder, Monoid[IO[Option[Int]]].empty works, but Option[IO[..]].orEmpty doesn't work?
Martijn Hoekstra
@martijnhoekstra
@SystemFw right, so tackled that: https://scalafiddle.io/sf/skLC0Sv/1
Otto Chrons
@ochrons
//print should work as expected, but doesn't. This seems to be either a scalajs or a ScalaFiddle artifact, ScalaFiddle "emulates" println but print goes to browser console
Martijn Hoekstra
@martijnhoekstra
:+1:
thanks!
Otto Chrons
@ochrons
there's also Fiddle.print for printing HTML directly
Martijn Hoekstra
@martijnhoekstra
thanks
Otto Chrons
@ochrons
you need that scalatags import to bring in some implicit conversions, though
Martijn Hoekstra
@martijnhoekstra
fair enough
"printing" is something really weird anyway
Otto Chrons
@ochrons
btw, Cats 1.0.1 is already in ScalaFiddle if somebody wants to try it out ;)
Otto Chrons
@ochrons
probably not a Cats issue?
Fabio Labella
@SystemFw

@martijnhoekstra right, so there's a lot of directions you can go from there.

  • You could refactor the interpret bit, for example using the State monad (or its tagless version MonadState) rather than the manual state threading, or note how your Data and Instructions are very similar to each other.
  • You could switch to a different language (e.g. a stack based one where you can also pop from the stack), and note that what you have now, i.e. an instruction being an AST with no type parameters and a program being simply List[BFInstruction], transforms to an instruction being an AST with a type parameter for the output type, and a program no longer being just a List[Instruction], but a Free[Instruction, A], so you go from Free Monoids to Free Monads.
  • You could try moving what you have to final tagless, but as it stands, it's not easy: the current logic requires going back and forth along the List of instructions for loops, which is obviously easier to do if you have a concrete representation (the AST). If you change your instructions set to e.g. have a case class Loop(p: List[BFInstruction) instead, then you can remove that logic and move it to the Parser (you'd need a parser combinator library), at which point translating to tagless should be easier.

There are two versions that do the above:
1) initial: https://github.com/ekmett/lens/blob/b1ca6288fed878d7197416a9ca72983577260ad6/examples/Brainfuck.hs
2) final:
https://github.com/ekmett/lens/blob/bec00420db73cacb2bb8a277ca115d2220ef2c76/examples/BrainfuckFinal.hs

warning: the haskell there is a bit outdated

(I recommend reading the initial version first)
Martijn Hoekstra
@martijnhoekstra
thanks, I'll take a look where I can go
I particularly wanted to see where things would lead, and what kinds of operations are easy/hard in what style, but a stack based language might indeed be better for discovering that.
there are such obvious optimizations, that I was really wondering how that would work, and what that would look like
Fabio Labella
@SystemFw
I think writing "compilers" is skewed towards an initial representation
it can be more intuitive to write transformations and stuff
final can give you advantages like fusion though, but it's harder to figure out imho
the opposite is true in user code, like for your standard "interface"
where final wins due to less boilerplate and ease of composition
Martijn Hoekstra
@martijnhoekstra
I was led to believe that Free was ideal for such things
Fabio Labella
@SystemFw
yeah, that's what I mean by initial representation
an AST, basically
whereas a final representation is functions (the eliminators)
and in fact, you are using Free now
your Free is List
and it's Free wrt to Monoid, which is all you need here
Martijn Hoekstra
@martijnhoekstra
I don't know what initial, final, or eliminator really means
Fabio Labella
@SystemFw
ok, I can explain the terminology to bring some clarity :)
so, the domain all this originated is EDSLs (embedded domain specific languages)
the most intuitive way of writing one is by writing a data structure that represent your EDSL, then interpreting it into something else
e.g. data Op = Add Int Int | Const Int
plus a function from Op to whatever you want to interpret this to (e.g. an Int for evaluation, or a String for pretty printing)
this is an example of an initial encoding, also referred to as a deep embedding
what you had there is therefore initial
an AST basically