https://kotlinlang.org logo
Join Slack
Powered by
Let's say I have a simple structure like this (wit...
# arrow
c
Let's say I have a simple structure like this (without annotations etc):
Copy code
sealed class Tree {
    class Leaf(val x: Int) : Tree()
    class Node(val x: Int, val children: Map<String, Tree>) : Tree()
}
What would be the Optics way of filtering nodes based on some criteria throughout the entire tree (recursively)?
c
Another question if you don't mind me hijacking a bit. Can you derive optics for this? Or do you need to implement them yourself?
(fwiw, I am also curious about your question!)
c
It's just adding the 
@optics
annotation and 
companion object
in the right places, I left it out for readability
s
https://github.com/nomisRev/kotlinx-serialization-jsonpath This is an example of a DSL based on Optics for a recursive structure. Without understand the assignment of Advent. I assume that 
children
here are selected based on some key in 
String
? I'm not sure if there is a way to focus on all recursive trees.. 🤔 You would have to specify the depth.
Copy code
<http://Tree.node.children.at|Tree.node.children.at>(At.map(), "key").<http://node.children.at|node.children.at>(At.map(), "nested-key")
c
The assignment is: each leaf has a size, the size of a node is the sum of the size of the children; but we only care about nodes smaller than some given size
s
I think there is an Optic that does what you want, but it's not implemented in Arrow 🤔 IIRC Scala had something called 
Plated
that for example allowed modifying elements in Json that matches a predicate
c
Hm. Intuitively, I'm trying to reach for something like 
fold
, but I can't wrap my head around implementing it for a tree
and the wikipedia article only gives Haskell code 😅
j
The optics path has to use something like 
deepOf plated f
in haskell, probably won't exist in many other langs because this is hard to get right on a non stacksafe implementation. This optic will focus all children recursively excluding matched ones. So it will recursively run 
plated
which extracts the immediate children, then runs the optic 
f
and if that focuses no elements it recurses through the children previously returned by 
plated
. Getting this correctly implemented is annoying (@simon.vergauwen I think I had this in the profunctor branch at some point. I can look it up if you are interested 😅) You can also do this neatly with recursion schemes, but those are even harder to get right on non stacksafe platforms and I do not recommend this outside of haskell. Even there only do it if you have lots and lots of recursive traversals on tree like structures.
c
it would be so convenient though 😅
j
It really is 
plated
and 
deep = deepOf plated
are useful for generic tree traversals. Simply define/derive 
plated
for a type and you can easily write any sort of recursive Traversal
s
I once implemented 
Plated
and it was terribly slow. I can probably dig it up. I looked at it in Scala as well and it's similarly slow
Not sure what the performance was of that type in your branch @Jannis?
Also nice to see you here again @Jannis ☺️ Hope you're doing well!
j
I split the function (
f.deepOf(g)
) into a 
Fold
and 
Traverse
side (overloaded so a user won't ever notice). The fold worked as follows: We start with the top level element in a queue. Dequeue one element, run the focusing optic 
g
and record if it executed (or was filtered out). If it was filtered out, use the extract optic (usually 
plate
) to get new elements, append them to the queue. Repeat until the queue is empty. Since I used `Applicative`'s the return value was 
Kind<F, Unit>
on a fold and combining all the intermediate return values was obvious (just combine the context using 
ap
.) This I assume is fast, a mutable buffer as a queue and it is working through a flattened structure. The 
Traversal
side is more complex because the return type actually matters and isn't just 
Unit
wrapped in some context. I had to use 
DeepRecursiveFunction
but other than that the concept was very similar, just that now we can't just flatten everything because we need to plug the results into the correct places. That being said, it is probably still faster than any 
Eval
version. Here are two links: Fold: https://github.com/arrow-kt/arrow/pull/2407/files#diff-e1b4ae612d548a8678a928b28c8d98bcbb382e622e85a4d677b7bf56c8a68b7cR172-R192 Traversal: https://github.com/arrow-kt/arrow/pull/2407/files#diff-73e1ef7af4d30c50b1bd69be8111db7c8a90fa843a18371860ad6a3648a25203R247-R275 Honestly the traversal is very confusing, but should work. (tho it does require stable traversal order on the extract optic)
Also nice to see you here again @Jannis ☺️ Hope you're doing well!
Thanks 😄 Had lots of things to deal with so I usually just catch up superficially on things. It's interesting to see how arrow developed, glad that the dsls around effects are still around and evolving. Your twitter screenshots look great! A bit sad to see what was cut, but given the lack of language support it's inevitable, otherwise arrow would remain niche forever.
@simon.vergauwen Btw you should really check out the test file where I had some examples (plated is down the end) . Despite the scary type signatures kotlin did really really well at inferring the types. In fact if it weren't for the lack of higher kinds, inlining and optimization by the compiler, I would still consider this to be by far the best way to implement optics.
s
A bit sad to see what was cut, but given the lack of language support it's inevitable, otherwise arrow would remain niche forever.
What do you feel was lost? A lot was cut, that's for sure. Just looking for feedback, perhaps there are some gaps we can still try to figure out how to fill. I think biggest miss is proper multi-shot continuation. Beside being more idiomatic to Kotlin, due it lacking some language features the biggest win IMO was the drastically decrease in the learning curve. It's been much easier to get started with Arrow/FP for new-comers, and teach people FP in Kotlin. In my day-to-day, working on microservices I don't feel I've lost anything. As a library author, I had to shift my mindset. Instead of composing higher-level things, I quite often have to build something from scratch. For more complex use-cases we'll probably need compiler plugins, that's also how I hope to take Optics further. (Due to lack of 
Generic
and 
typeclasses
) but was kind-of the same before...
j
It was horrible slow when I tried to use, and implement it over 
Json
.
Yeah anything that uses 
Sequence.plus
is in my experience very slow (such as the 
universe
impl, which as far as I can tell is the only recursive one there. Ignoring rewrite which recurses on the optic to apply not the structure). I think if you want a decently fast implementation on a non-lazy non-stacksafe language you most likely need something similar to what I did. The haskell implementation of 
deepOf
is a one-liner btw. Laziness and stacksafety coupled with a ~32 year old strong compiler can do magic 😄
I think biggest miss is proper multi-shot continuation.
This mostly. Like why not at least give the option of cloning the continuation. Like optimize for linear continuations all you want, but if someone really wants to pay the price for cloning a continuation, let him do so. There is probably a technical reason for this, but likely nothing insurmountable.
Beside being more idiomatic to Kotlin, due it lacking some language features the biggest win IMO was the drastically decrease in the learning curve
The old HKD definitions and typeclasses were both new to many and hard to use at the same time. Like with monad tutorials, they all get it wrong. No one cares what a monad is, what `beginners need to know is that you can use 
<-
in a 
do
block to extract a value. But if even that is annoying for lack of syntax sugar or other caveats, then its just another hurdle for beginners. I do really miss applicative combinators tho. Having used them more and more for 
Haxl
like dsl's and parsers they are super convenient for optimizing static structures (such as concurrent requests or parsers)
Also 
Generic
. This alone saves so much boilerplate
s
they are super convenient for optimizing static structures (such as concurrent requests or parsers)
Yes... but in my production usage of Kotlin I haven't had a lot of need for this. It's still achievable but you need to build it on a special basis. We have a 
Haxl
like library in Scala @ 47 and I've ported it to Kotlin. It works but 
zip
is weird if you have 
bind
, it's "as hard" manually optimising with a cache. 😅 I.e. using 
parZip
instead of 
zip
for concurrent requests. Albeit it can be parameterised at the edge if you have a special data type for it.
There is probably a technical reason for this, but likely nothing insurmountable.
IIRC this requires a language to be pure, right? I think the language authors talked about this ones, and the probably is mutability in the language IIRC but I could be mistaken.
j
It works but 
zip
is weird if you have 
bind
, it's "as hard" manually optimising with a cache. 😅
This is also true in haskell. Hence why facebook invented and added 
ApplicativeDo
s
Right, but that wouldn't have been feasible with the old Arrow either I think
The old bind with reflection was really bad 😂
j
IIRC this requires a language to be pure, right?
If you want sensible results in multishot mode yes. But this is doable on user level right? So make it clear to any user that mutability is a global thing and will change on multiple runs. We have to clone the stack anyway, so it is only mutable if we use references to mutable objects, but that is a user decision
Right, but that wouldn't have been feasible with the old Arrow either I think
Right, applicatives just don't work well in languages without decent partial application support
The old bind with reflection was really bad 😂
Honestly was it? It really just gave access to the stack and made it cloneable. It was terrible at interacting with other suspend code, but that is because kotlin focused that feature super hard on concurrency and not on general use as continuations
s
but that is a user decision
Right but which is what makes it so hard for a language, or even library to expose it. It's fine inside of a library if the author knows what he's doing but I would also not trust this in an application.
Honestly was it?
Okay, maybe depends on what angle you look at it from 😅 Reaching out to unstable bytecode, and interacting with it is quite bad in general. Also it limited us to the JVM, so for Kotlin it wasn't a great solution.
j
"kotlin focused that feature super hard on concurrency and not on general use as continuations"
btw I am thinking about implementing linear delimited continuations in the haskell rts and this has been very high on things to think about: ie how much do I want this to be about scheduling/concurrency
Reaching out to unstable bytecode, and interacting with it is quite bad in general. Also it limited us to the JVM, so for Kotlin it wasn't a great solution.
That is true. It was quite clever imo, but very unsafe and when kotlin multiplatform started to grow also not usable
s
Right, I think a less strong focus on scheduling/concurrency would've been really awesome. You can see that it leaked into the Kotlin Compiler and Std even though it's an external lib.
12 Views
Open in Slack
PreviousNext
Powered by