Where communities thrive


  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
People
Repo info
Activity
    Greg Pfeil
    @sellout
    @cmcmteixeira Also, the most significant difference with mine is not having a separate call to List.filter.
    cmcmteixeira
    @cmcmteixeira
    ouch! it does ... that's what you get when you just trust intellij :smile: ; my bad !!
    That call to "list.filter" is only cause I remove the fixed which as you said it's probably not the best of ideas
    Greg Pfeil
    @sellout
    You could still use my approach even if you don't re-wrap in Fix (meaning the predicate and result use TreeF[Fixed]), but I think the API there is just not quite as nice. I tend to only use the unwrapped form when I'm dealing in individual nodes, and (sub)trees are wrapped.
    cmcmteixeira
    @cmcmteixeira

    Had a quick go.. adapting your approach @sellout ends up looking like this:

    def filter(treeF: Fixed)(predicate: Fixed => Boolean): List[Fixed] =
        scheme.zoo
          .para[TreeF, Fixed, List[Fixed]](RAlgebra { f: TreeF[(Fixed, List[Fixed])] =>
            val currentNode: TreeF[Fixed] = f.map(_._1)
            val alreadySelectedNodes = f.map(_._2) match {
              case Leaf(_)           => Nil
              case Node(_, children) => children.toList.flatten
            }
            if(predicate(Fix(currentNode))){
              Fix(currentNode) :: alreadySelectedNodes
            } else {
              alreadySelectedNodes
            }
          })
          .apply(treeF)

    The only difference is that Fix.un(subtree).map(_._2) results in a TreeF[List[Fixed]] so I had to pattern match there to get the previous results

    cmcmteixeira
    @cmcmteixeira
    Also, @monaddle , thank you very much for your help too! Regarding the empiricist ; yep! me too :wink:
    Greg Pfeil
    @sellout
    @cmcmteixeira Since you have Traverse, you also have Foldable, so try val alreadySelectedNodes = f.foldMap(_._2) without the match.
    @cmcmteixeira Now, if you look at the resulting code, you'll see there's no reference at all to TreeF, so you can generalize it as def filter[F[_]: Traverse](tree: Fix[F])(predicate: Fix[F] => Boolean): List[Fix[F]]
    Greg Pfeil
    @sellout
    @cmcmteixeira Tangentially, a more precise way to define filter is def filter[F[_]: Traverse](tree: Fix[F])(predicate: Fix[F] => Option[A]): List[A], which prevents bad implementations like filter(treeF)(predicate) = [treeF]. I.e., you know only things that have passed the predicate can be in the result.
    cmcmteixeira
    @cmcmteixeira
    indeed ! That's amazing! Way better !
      def filter[F[_]: Traverse](treeF: Fix[F])(predicate: Fix[F] => Boolean): List[Fix[F]] =
        List(treeF).filter(predicate) ++ scheme.zoo
          .para[F, Fix[F], List[Fix[F]]](RAlgebra { f: F[(Fix[F], List[Fix[F]])] =>
            f.foldMap(_._2) ++ f.map(_._1).filter_(predicate)
          })
          .apply(treeF)
    kinda annoying that I have to add that List(treeF).filter(predicate) if I want the root node to be looked at but not the end of the world
    Greg Pfeil
    @sellout
    Yeah, I don't like that special handling of the root node -- I would prefer a more verbose algebra like the earlier cases today that handles all nodes identically.
    cmcmteixeira
    @cmcmteixeira
    Agree.. It's a bit unfortunate that we can't really get "the current" node as a Fix[F] ; only the descendants
    Greg Pfeil
    @sellout
    Yeah -- that's what the Elgot stuff solves for us. But explicitly wrapping with Fix isn't so terrible.
    Soren
    @srnb_gitlab
    @sellout One to potentially add to the readme, with an explanation of pattern functors:
    sealed trait TreeF[A, X]
    case class Leaf[A, X](data: A) extends TreeF[A, X]
    case class Branch[A, X](left: X, right: X) extends TreeF[A, X]
    
    sealed trait Step
    case object StepLeft extends Step
    case object StepRight extends Step
    
    def listPaths[A]: Algebra[TreeF[A, *], Vector[(A, Vector[Step])]] = Algebra {
      case Leaf(a) => Vector((a, Vector()))
      case Branch(l, r) =>
        val newL = l.map { case (end, steps) => (end, StepLeft +: steps) }
        val newR = r.map { case (end, steps) => (end, StepRight +: steps) }
        newL ++ newR
    }
    This'll list every path in a binary tree when put through a cata
    Fun exercise to implement manually
    Soren
    @srnb_gitlab
    What's the current status of a recursion scheme library for Scala 3/Cats 2.3.0? Droste hasn't been touched in a bit and I doubt all of the stuff would support those new versions.
    Greg Pfeil
    @sellout
    @srnb_gitlab Good question! I just realized my other recursion scheme libs suggest Turtles (which I never actually published) as the Scala recursion scheme lib. I should update that ... and it'd be good to be able to mention the situation for Scala 3 as well.
    Soren
    @srnb_gitlab
    :smile: awesome
    Soren
    @srnb_gitlab
    image.png
    Michanix
    @Michanix
    Hi lads! For the last couple of days I have been battling with expression simplification program as a final project for Scala course in my university. Just explain in short, it takes S-expression like this (+ (* (- 5 5) (^ x 2)) 8) and simplify it down to (5-5)*x^2+8 → 0*x^2+8 → 0+8 → 8. I have no problem with constructing expression tree and evaluating it, but i have problem with how big my simplifying function gets. So, in short, I have this code at the moment and if you look at the simplify() and simplify2() functions then they are already looking huge. And those function only covers sum operation and a little of subtraction at the moment. I have been suggested, that Droste can help me reduce all that boiler plate code, but since I am new to Scala I really struggle to put concepts of recursive schemes together and apply to my code. So, if any of you could help me out with this problem or have any advice on how this can be improved in another way, I would really appreciate it.
    damn, that's a lot of text, sorry
    Soren
    @srnb_gitlab
    @Michanix So, the reason "Algebra" in school is called algebra:
    Soren
    @srnb_gitlab
    @deriveFixedPoint sealed trait Expr
    object Expr {
      case class Num(num: Int) extends Expr
      case class Add(left: Expr, right: Expr) extends Expr
    }
    import Expr._, Expr.fixedpoint._

    First, you'll want to derive the fixedpoint of your expression tree. This will give you ExprF, which is the "pattern functor" for your expression tree. Then, you can write your simplification rules as algebras:

    def simplify: Algebra[ExprF, Int] = Algebra {
      case Num(i) => i
      case Add(l, r) => l + r
    }
    def infixify: Algebra[ExprF, String] = Algebra {
      case Num(i) => i.show
      case Add(l, r) => "(" ++ l ++ " + " ++ r ++ ")"
    }

    Here an Algebra represents a "step in the process", i.e. it tells you what to do at a single point in your simplification. Then, you apply a recursion scheme to your tree: In this case, we'll be applying a "catamorphism", a.k.a. "generalized fold": Simplifying an expression is just a big fold

    def toSimple: Expr => Int = scheme.cata(simplify)
    def toInfix: Expr => String = scheme.cata(infixify)
    I hope that helps.
    Soren
    @srnb_gitlab
    If you need to preserve variables, then you'll need to replace that Int with something that supports the operations you need
    But it should work beautifully then
    Soren
    @srnb_gitlab
    (Algebra[ExprF, Expr] would work, as long as you make sure it creates the most simplified case.)
    (I made a mistake too, in my above algebras I should have put case NumF and case AddF instead of case Num/case Add)
    Michanix
    @Michanix
    Wow! I had all these pieces in my mind, but couldn't put them all together. This explanation makes things a lot more clear now! Thank you for your time!
    Soren
    @srnb_gitlab
    Happy to help :smile:
    Mark
    @Fristi
    Hi there :)
    Is a release planned ? I see 0.8 is only available for scalajs 0.6
    But in the build it's bumped to 1.x
    tpataky
    @tpataky
    I'd be interested in a new release too. Are there any plans? Thx
    Tim Spence
    @TimWSpence

    I was trying

    @deriveFixedPoint sealed trait Tree[B]
    case class Leaf[B]() extends Tree[B]
    case class Branch[B](left: Tree[B], value: B, right: Tree[B]) extends Tree[B]
    
    object Tree {
    
    }

    and am getting the error

    [info] compiling 1 Scala source to /Users/tim/work/example/service/target/scala-2.13/classes ...
    [error] /Users/tim/work/storm/service/src/main/scala/com/itv/storm/DrosteTest.scala:13:2: not found: type B
    [error] @deriveFixedPoint sealed trait Tree[B]
    [error]  ^
    Aly
    @aly:scuttlebug.space
    [m]
    It might be that @deriveFixedPoint doesn't work with multiple type arguments? Also, if I remember correctly, you have to put Leaf and Branch inside the case object for Tree @TimWSpence
    Tim Spence
    @TimWSpence
    Thanks @aly:scuttlebug.space I had a quick look at the macro and it looked like it should work with multiple type arguments but I’m no expert on macros. I tried putting Leaf and Branch inside the companion object but it didn’t help
    Tristan Lohman
    @gatorcse
    sorry if this has been addressed before, but is there a reason why there isn’t CVAlgebraM and CVCoalgebraM?
    Nick Childers
    @Voltir
    has anyone here started on the journey of scala3ifying droste?
    Richard
    @Executioner1939

    Hi guys, I really don't know where to start with what I am trying to accomplish. As with most cases I have an Expr AST that defines operations like Or, And EqualTo etc. As well as a variety of Literal Types such as Int, Date, String and so on.

    My issue with the recursion is dealing properly with these types, for example final case class EqualTo(lhs: Expr, rhs: Expr) extends Expr (haven't moved to recursion schemes yet) obviously lhs and rhs need to be equal types.
    Does anyone have any idea about how I could achieve this?

    My Expr needs to return an aggregated list of Actions to execute based on the conditions in the tree.

    Does anyone have any idea about how I could achieve this?- I mean handling the different types, and somehow conveying that the lhs and rhs need to be comparable.
    Adam Rosien
    @arosien

    @Executioner1939 your expression type is "untyped", so as-is you would need to reject bad types at evaluation time, or run some type-checking algorithm that would accept or reject a given Expr value by traversing the structure, ensuring the types align properly. this is difficult.

    you could alternatively add type info to trait Expr[A], so then case class EqualTo[A](lhs: Expr[A], rhs: Expr[A]) extends Expr[Boolean] would ensure the argument types match

    Richard
    @Executioner1939
    @arosien thanks for the guidance, let me see what I can do. Hopefully I can get it to work.
    Tim Spence
    @TimWSpence

    Hi! Firstly I wanted to say thanks so much to all the people who worked on getting Droste published for scala 3. That’s really awesome to see!
    @joroKr21 and I just had a few questions/reservations around the scala 3 macros piece. I see it’s a direct copy from our in-progress work on kittens for scala3 so just wanted to flag that

    1. That work is still very much in-progress and the current derivations are not lawful!
    2. We weren’t sure what value maintaining a (potentially out-of-date) copy of those derivations in droste-macros has? As things currently stand in droste (please correct me if I’m wrong!) you need to write your own base functors and then provide instances of Functor and Traverse for them, either by writing them by hand or deriving them. I’m just not sure what value the copied subset of kittens derivations provides over just importing kittens itself? It’s a separate dependency either way.

    I hope I’ve struck the right tone here - one of genuine questioning and expressing reservations, rather than criticism. And once again, massive thanks to all who were involved in supporting scala 3. I’m a big fan of Droste and am super excited to see it make the jump!

    Tim Spence
    @TimWSpence
    Anyone? :)
    Georgi Krastev
    @joroKr21
    Seconded :point_up: (sorry for the late reply :smile:)
    Alex Kozlenkov
    @prova
    Hi, quick one really, what are the stack use expectations regrarding the majority of Fix based constructions in droste? The regular ghylo in the README easily blows up the stack with sumSquares(100000). Is this expected or my assumptions are wrong in some way?
    Alex Kozlenkov
    @prova
    Answering myself and related to higherkindness/droste#95, this uses Cats Effect 3
    Alex Kozlenkov
    @prova
        // required by hyloM
        implicit val natTraverse: Traverse[Nat] = new DefaultTraverse[Nat] {
          override def traverse[G[_] : Applicative, A, B](fa: Nat[A])(f: A => G[B]): G[Nat[B]] = fa match {
            case Zero() =>
              Applicative[G].pure(Zero())
            case Succ(previous) =>
              f(previous) map (Succ(_).asInstanceOf[Nat[B]])
          }
        }
    
        val natAlgebraM = AlgebraM[IO, Nat, Int] {
          case Zero() => IO.pure(1)
          case Succ(n) => IO.delay(n + 1)
        }
    
        val natCoalgebraM = CoalgebraM[IO, Nat, Int] {
          n => if (n == 0) IO.pure(Zero()) else IO.delay(Succ(n - 1))
        }
    
        assert(scheme.hyloM(natAlgebraM, natCoalgebraM).apply(100000).unsafeRunSync() == 100001)