https://kotlinlang.org logo
Join Slack
Powered by
<@U4UGS5FC7> I'm working on a Kotlin MPP library f...
# arrow-contributors
a
@raulraja I'm working on a Kotlin MPP library for which I need some FP utilities which is provided by Arrow Core. My problem is that it is not MPP yet and now I'm trying to determine which is a more time-efficient solution: roll my own FP lib including the essentials or help Arrow become MPP. I've heard from @pakoito that you're working on it. Can you give me a rundown on what is needed to get there?
r
Hey Adam, for Arrow to become MPP we are developing typeclasses of KEEP-87 as a compiler plugin, it's still in early stages and prototype as we are discovering what the limitations of compiler plugins are and how we overcome it. At the rate we are going I expect to have an implementation mostly ready by September or October. I'm currently investigating and trying to implement quasiquote style tree transformations so we can do metaprogramming similar to Scala meta letting the Kotlin compiler do the codegen based on KElements
As for MPP in general it's in my opinion not ready. The IR implementation is not 100% mpp compatible and mpp is still lacking several areas in terms of dispatchers, etc.
If I were you I would depend and develop the library in terms of the JVM and arrow core for now because it will be mpp automatically by the end of the year. It is our goal Arrow is full MPP before 1.0
We have many more ideas for meta that would work in mpp https://github.com/47deg/arrow-meta-prototype/issues
I'm not sure if vavr uses inheritance in their collections but definetly the features of KEEP-87 can be used in a collections design to separate data and behaviors polymorphically for all Foldable and Traverse
s
for Arrow to become MPP we are developing typeclasses of KEEP-87 as a compiler plugin
Is this blocking core to be MPP? 
Monad#fx
and 
@higherkind
seem the blockers to me. 
@higherkind
could temporarly be replaced by its boilerplate. If we can find a (temp) solution to seperate 
Monad#fx
that would open the door to make core MPP already.
a
I see
Im not in a hurry
Mypoint is that writing common code is not much more difficult than writing jvm code
But it pays off in the future
Sorry im from phone
s
In that case, it’ll be easier to start from JVM like @raulraja suggested. Currently there is a lot of effort to make Arrow MPP, migrating to that should be trivial.
a
One moment brb
Do you have the core arrow interfaces in an mpp library?
Imean module
So i can depend on it, do my implementation of persistent data structures
Then backport it to arrow when it becomes mpp?
s
Work has been done to re-organise those classes but I don’t think it’s been made into a MPP project
a
Can i help?
I dont want to roll my own lib if it is possible to do this in arrow
s
I just checked and the core module still contains something that needs to be replaced by compiler plugins.
a
Ok
s
In case you’d like to develop MPP you could always clone the core module and rip out everything related to https://github.com/arrow-kt/arrow/blob/master/modules/core/arrow-core-data/src/main/kotlin/arrow/typeclasses/ContinuationUtils.kt
a
Then ill do my port (vavr)
Oh
s
Then afterwards, you can just toss the clone and depend on arrow-core directly
a
Good idea
Ill check it once im back at mycomputer
s
👍 if you need any help I’d love to help out. Exciting to see this happen
a
So you use vanilla kotlin data structures noww?
Cant type sorry
Vavr's option/try have different semantics
s
Yes, almost everything is vanilla Kotlin. We have to rely on some reflection to emulate 
for
comphresions/do-notation, for perf and MPP reasons we’ll replace this with compiler plugins.
a
So ill use theirs for the port
Then i refactor to arrow
s
I know Vavr has a couple of side-effecting APIs
a
I dont mind purging them
s
👍
a
This is how vavr looks like
i'm not familiar with Arrow's hierarchy, but I'm almost sure it is not compatible
that seems like a design smell to me is not only 
Value
(which they realized they need to remove)
but that all ADTs are 
Iterable
this might make sense for 
Option
which is an empty 
Iterable
if it is 
None
and an 
Iterable
with 1 element if it is 
Some
but how do you iterate an 
Either
?
or some custom time where iteration is not sensible
s
Iterable
is the wrong abstraction here. 
fold
is what you want to use instead, it's abstracted over by 
Foldable
. Which is the polymorphic way of providing this API.
a
do you have a set of interfaces which you use for collections / maps?
so I can yank it out
s
Not specifically for collections or maps since those abstractions can be implemented by most data class. `Functor`(map), 
Monad
(flatMap), `Foldable`(fold), 
Traverse
(traverse), 
FunctorFilter
(filter) etc
But those closes are typically used to abstract over the container. I'm not sure this is what you are looking for.
Could you share some signatures? It's probably easier to talk in terms of those.
a
oh I got it
so how can we reconcile Kotlin's 
Iterable
with these?
what I'd like to be able to do is to have an API which is a no brainer to use for Kotlin devs
for example
Copy code
myMap.toPersistentMap().map { (key, value) -> ...}.fold { ... }
I wrapped Clojure's collections in a POC which worked really good but there is a problem: the Kotlin stdlib defines a lot of extension functions on 
Iterable
so I need to supply specializations for all of them which work with `PersistentCollection`s
If I understand correctly Arrow's `Functor`/`Monad` etc completely decouple the whole thing from the Kotlin stdlib, right?
what's the relationship between this and
?
s
I think both were created for interested people but nothing ended up happening. It should be cleaned up.
Yes, the typeclass hierarchy is meant to decouple the actual types from the behavior. So it also effectively also decoupled everything from the std lib.
To be honest I'd avoid implementing 
Iterable
on your persistent collections. This way you can avoid getting tangled into the extensions functions of the std.
With keep-87 or the compiler plugin all these functions implemented by `Functor`/`Monad ` will be automatically available as instance methods.
Having 
object PersistedMapFunctor
available is enough for the compiler to know 
map
exists for 
PersistentMap
.
a
Copy code
This way you can avoid getting tangled into the extensions functions of the std.
This is what I implied, yes!
I've forked 
arrow
running 
./gradlew clean build
resulted in a wall of text of compilation errors. Am I missing something? A switch maybe?
this is an example:
Copy code
D:\dev\forks\arrow\modules\validation\arrow-validation\build\generated\source\kaptKotlin\main\extension\arrow\validation\refinedTypes\numeric\either\nonZero\EitherNonZero.kt: (18, 47): Type argument is not within its bounds: should be subtype of 'Number'
r
what JDK are you running this with? I’ve never seen that come up
a
I'm not at my other computer right now but I think it is the latest JDK8
(Oracle)
i'll check when I'm back at home
i'm trying it on my mac now
It is still running (15m) so I think this is a windows problem
on my mac I have OpenJDK
Is Oracle's JDK unsupported?
Confirmed, it works on my mac
message has been deleted
r
no idea what the issue is on your windows but AFAIK others have built it on Windows before
a
don't worry I'll figure this out
btw is it normal that a 
./gradlew clean build
takes 32m?
p
yes
use assemble for compilation
and test for festing
build does both, plus builds the docs
a
got it 👍
I just wanted a full build to verify that it works
@raulraja I'm going to create an implementation for 
PersistentMap
using Arrow with the plain old JVM target (no MPP) just to see how it works, although I have one question:
There is no typeclass for removal AFAIK. We should agree how it should work
r
What is the type signature of 
remove
?
a
I think the simplest solution is to add a 
fun remove(element: E): PersistentMap<E>
what do you think?
r
that does not mutate the map right?
a
it does not
it returns a new version which doesn't have 
element
now that I think of it, we can create a typeclass for this
something similar to 
FunctorFilter
r
well this probably already exists for either all Foldables or all Traverse
a
checking
r
so we can just add the 
remove
operation to wherever it fits
I mean is not there today but it’s an operation that can be probably implemented in Foldable
a
where do we have 
filter
?
remove
is a specialized version of 
filter
it filters a single element using an equality check
it is like 
list.filter { it != element}
it is just very ineffective: 
O(n)
vs 
O(1)
r
well data types can specialise it to make it fast
but we can provide a default implementation
a
we need something which defines 
eq
for 
E
and which has 
filter
makes sense
so it is a combination of 
FunctorFilter
and 
Eq
so we can add 
remove
to 
FunctorFilter
and have the default implementation which is 
O(n)
and the specialized version which implements the 
O(1)
version for 
PersistentMap
how's that sound?
r
Copy code
fun <F, A> Kind<F, A>.remove(a: A): Kind<F, A> =
  if (this.contains(a)) this.filter { it == a }
  else this
a
although I'm not 100% sure how 
Eq
comes into the picture
r
is that conceptually the impl ^^^ ?
a
yes!
so if I understand the concept properly
you define this on 
Kind<F, A>
and provide an implementation for 
Kind<ForPeristentMap, A>
?
s
Yes, so a default impl 
O(n)
impl would exist in 
FunctorFilter
and a fast impl would override the default in 
FunctorFilter<PersistentMapOf<Keys>>
and 
FunctorFilter<ForPersistentSet>
☝🏼 1
r
right
a
great!
i'll be back
i'm going to read the docs so I can quit asking stupid questions
i also need to port the unit tests
and the rest of the data structures
thanks for the input this was really insightful! 👍
👍 2
r
Copy code
fun <A> Kind<F, A>.remove(a: A): Kind<F, A> =
    mapFilter {
      if (a == it) Some(it)
      else None
    }
conceptually if this ends up inside FunctorFilter which is already in core master
the 
==
is where the equality plays a role
Also if you plan to add this to FunctorFilter or something similar we should consider others like 
removeIf
etc…
that resemble the apis in the standard library but without mutation
s
Yes, I've missed this set of functions a couple of times already and I always ended with slow 
fold
code instead
r
Also this may be also implemented in Foldable which in my opinion it would be more versatile
In Foldable we already have things like 
contains
etc.
so you may be able to fold and accumulate into the new collection ignoring items that match the predicate
p
if (a == it) Some(it)
==> one thing to mention, all maps in Haskell use Eq and Ord for keys
🔝 1
maybe if we're building our own libs we could leverage them too
a
Foldable
seems like a reasonable choice if we care about utility
but conceptually it would be best suited in 
FunctorFilter
➕ 1
I also agree with @pakoito that 
Eq
should be used instead of 
==
➕ 1
since we already have a lot of utitlity in 
Eq
where should I put the data types?
arrow-core-data
?
are persistent data structures a 
core
concept?
s
Core concept absolutely. Does it belong in 
core
not perse, if the module is small enough I'd say yes.
We've moved away from an as small as possible core module to one that makes more sense to users.
r
remove
would go in FunctorFilter or Foldable in core and the actual collection implementations datatypes and extensions a 
arrow-persistent-collections
or similar named module
a
which one would you guys prefer 
FunctorFilter
or 
Foldable
?
I'm not that familiar with the code yet to be able to make this decision on my own
so what I'm thinking is this: 1. I'll finish my port of persistent data structures to Kotlin in my own project 2. I'll properly read through the docs of Arrow and tinker with it so I can fully grasp how these concepts work 3. I'll integrate 
PersistentMap
on a branch in my Arrow fork and open a PR you can review
how's that sound?
I think it would make sense to start small and go from there (by not implementing 
PersistentSet
+ 
PersistentList
together with 
PersistentMap
in one go)
p
if it’s implementable with Foldable I’d use it, it’d be funny to use delete on Option hahaha
➕ 1
1. I’ll finish my port of persistent data structures to Kotlin in my own project
what’s missing/necessary?
a
i want to port the unit tests to see that my port is up to snuff
then I have to refactor the type hierarchy to align it with Arrow
the original implementation is full of `null`s so I have to double-check everything
good thing is that the code is in a 
common
project so retrofitting to MPP will be a no-op 😄
p
null is okay in internal implementation for speed
just make sure that collections can store nullables
then I have to refactor the type hierarchy to align it with Arrow
I’m curious about this, if the code is shared through inheritance
a
i've ported VAVR code as-is
next step is to make it Kotlin idiomatic
then make it Arrow-idiomatic 😄
p
fair 😄
let us know where we can help
a
will do! 👍
👍 1
I think the docs is fairly understandable
Do you think that 
null
keys should be allowed?
VAVR is allowing it 😮
p
keys will be restricted to Eq and Ord
which are the typeclasses that define equality and order
so if someone has a typeclass that does string nullability comparison I don’t see why not
it’s just an additional value
one trick that Clojure did is that keys and values were treated as Object/Any? and only safe at the edges
a
hm
r
null in Kotlin is isomorphic to None. It's a Singleton empty value and it's a valid value in the monoid of nullable types as the identity element
Kotlin already prevents you from referencing direct null types and allows you to pass null as a value so imo it should be a valid key
If the user wants a map that does not accept nullable types it could constrain the key with : Any which will not allow you pass null as a key but that in Kotlin is a specialization since Any? is more generic
a
That't true
i'm also using 
<K, V>
so 
null
is theoretically accepted
This is the 
interface
for HAMT right now:
Copy code
interface HashArrayMappedTrie<K, V> : Iterable<Tuple2<K, V>> {

    val isEmpty: Boolean
    val size: Int

    operator fun get(key: K): Option<out V>

    fun containsKey(key: K): Boolean

    fun put(key: K, value: V): HashArrayMappedTrie<K, V>

    fun remove(key: K): HashArrayMappedTrie<K, V>

    fun keysIterator(): Iterator<K>

    fun valuesIterator(): Iterator<V>
}
how do you think this should be modified to enable Arrow integration?
apart from using the Arrow 
Option
instead of the VAVR one
r
You would just provide similar instances as the ones MapK provides for whatever type classes that datatype can conform to.
You’d need to determine if that can implement Foldable, Traverse, Functor etc… based on whether it can guarantee order or not.
Currently MapK can provide instances for Eq, Foldable, Functor, Hash, Monoid, Semigroup, Show, Traverse
a
okay
I'll take a look at 
MapK
i also fixed nullable keys
👏 1
A bit of an update: I've ported all the tests for the HAMT implementation and they passed out of the box so I'm happy about this
🎉 2
Now I'm going to make it a bit more Kotlin-idiomatic
👏🏼 2
@raulraja @simon.vergauwen @pakoito what do you think about 
core/arrow-persistent-collections
as a module for the implementations?
r
Should be top level outside core like fx is now in master
a
okay
should I branch from 
master
?
r
Yes, thanks!
Happy to see this initiative reborn
a
me too!
so I'll add a top level module 
arrow-persistent-collections
in the 
modules
folder, I'll branch from 
master
and I'll augment 
Foldable
. If that's not gonna work I'll use 
FunctorFilter
I'll use 
MapK
as an example
p
a
what's the 
k()
function btw which creates a 
ListK
form a 
List
?
there are no docs
p
there’s also the collections repo if you prefer
k()
is how you wrap stuff
List -> ListK
Map -> MapK
only ListK and MapKa and the others have typeclass instances
a
I got it, I just don't understand what the name 
k
and the prefix 
K
means?
p
Kind/Kinded
a
oh!
p
because they implement Kind
r
When we do the newtype compiler plugin there will be no need to k()
Since we can create instances on the fly for foreign types
a
got it
r
For your own types you don't need k() in what you are doing since you can make then @highkind
a
i'm wondering how KEEP-87 will work with MPP
r
ListK is for cases where we can't modify the hierarchy
It does already using the IR Backend
Which arrow meta enables by default
a
IR?
r
It's the bytecode format of the Kotlin compiler Backend
a
oh I see
r
It's an intermediate format for all backends
a
i haven't done any bytecode manipulation since my days in OSGi
r
That's all I'm doing these days 😓
a
ever since I used LISP it feels like a hack 😄
oh 😓
r
More tree manipulation because meta is now functional to the user
It's a function from Tree to List of trees
a
got it
s
But Kotlin compiler plugins isn't bytecode manipulation. It's much higher level.
A modern kapt... 🤔
r
Yeah though some times you write the IR classes yourself to produce just bytecode without descriptors but still much higher level than working with ASM libs
Meta is already a modern kapt because it can spit any new trees in new actual files so it can do codegen with the KElements which are more complete than the JavaElements and you have access to the bindingtrace which you can use to typecheck expressions
So more complete than kapt for metaprogramming
Even with a simpler compiler plugin and just the analysys phase of a compiler plugin you can do all that kapt does faster and better
a
so
a compiler plugin is run before Kotlin is compiled to java bytecode / javascript / etc?
i've never worked on these things 😞
s
A plugin can register extensions in different phases of the compiler.
a
what's the case with Arrow?
i'm just curious about the compatibility with MPP
s
So you could also use compiler plugins to write linters and create a IDEA plugin from the compiler plugin.
We plug into multiple faces. Type checking and code gen for higher kinded types. But @raulraja knows all the details
r
Some of the things we are working on https://github.com/47deg/arrow-meta-prototype/issues
a
thanks
r
the README has some context
a
oh
so this happens before MPP compilation
good
r
yes
a
👍
r
this is just contributing to the compiler with new trees that get automatically compiled to whatever target
a
i wonder how this relates to MPS
if it relates at all
r
what is MPS?
a
r
I think the only relation is that both use the IDEA apis for the PsiElements
a
@raulraja i ended up leaving most of the ported code of the HAMT intact
I don't want to introduce subtle bugs with code transformation
r
At the PsiElement levels is where the AST is
a
I intend this implementation to be a placeholder until I get CHAMP working
all these things would be unnecessary if we were using a homoiconic language like LISP 😄
r
true that
a
nevertheless
you can expect a PR within 2 weeks
i'm going to be on vacation so I'm not sure about the timeline
r
no worries and enjoy your vacation, thanks so much for this contribution. Hope we get to meet in person at LW or KotlinConf
☝️ 2
👍 1
a
I hope so
I've submitted a talk to KotlinConf
although it is still being evaluated
i've looked at the implementation of 
MapK
and I think that we shouldn't implement Kotlin's 
Map
in our 
PersistentMap
because the stdlib has a lot of extension functions on 
Map
which just don't make sense in our implementation
i've added a module under 
modules/persistent/arrow-persistent-data-structures
because it is better aligned with the naming I see there
if that's OK
r
sounds good
a
Do you think that folding a map makes sense with a 
Tuple2
?
Copy code
@extension
interface PersistentMapFoldable<K, V> : Foldable<Tuple2<K, V>> {

  override fun <A, B> Kind<Tuple2<K, V>, A>.foldLeft(b: B, f: (B, A) -> B): B {
    TODO("not implemented")
  }

  override fun <A, B> Kind<Tuple2<K, V>, A>.foldRight(lb: Eval<B>, f: (A, Eval<B>) -> Eval<B>): Eval<B> {
    TODO("not implemented")
  }
}
i've seen that 
MapK
uses the partially applied type and only folds keys
I've just seen how you do unit tests
Copy code
with(intFold) {

      "Folding a list of ints" {
        forAll(Gen.list(<http://Gen.int|Gen.int>())) { ints ->
          fold(Int.monoid(), ints.k()) == ints.sum()
        }
      }
    }
👌
r
The Foldable instance for this map should be consistent with how MapK does it
even if this isn’t a Map
a
it doesn't work this way I just found out
this code is generated
Copy code
@JvmName("orEmpty")
@Suppress(
        "UNCHECKED_CAST",
        "USELESS_CAST",
        "EXTENSION_SHADOWED_BY_MEMBER",
        "UNUSED_PARAMETER"
)
fun <K, V, A> orEmpty(arg0: Applicative<Tuple2<K, V>>, arg1: Monoid<A>): Tuple2<K, V, A> =
        arrow.core.Tuple2
   .foldable<K, V>()
   .orEmpty<A>(arg0, arg1) as arrow.core.Tuple2<K, V, A>
r
The type of fold based on tuples is for the isomorphism between Map<K, V> and List<Tuple2<K, V>>
a
okay
r
that fold already exists for List
The code is generated because Tuple2 is not a valid generic there
a
why is that?
r
try implementing Foldable as Mapk does
a
ok
i'm just trying to understand why 
Foldable<Tuple2<K, V>>
is not working
r
Because Foldable is a higher kinded interface that expects a one type argument hole for any F
The F representation of Tuple2 is Tuple2PartialOf<A> ForTuple2
depending on how many type args you are applying
Foldable is like Functor, it expects types in one whole in them and you are giving it a concrete applied type but it wants a type constructor
a
oh I see
how do I assert for equality
?
i've checked some tests but in all of them the 
forAll {}
constuct is used
r
what are you trying to compare? 
==
or 
Eq
usually is the way
a
i'm sure i'm doing it the wrong way
but this test passes
Copy code
"Should be able to use fold as a filter" {

    val result = listOf(1, 2, 3, 4).k().foldLeft(listOf<Int>()) { list, next ->
        if (next == 2) {
            list
        } else list.plus(next)
    }

    with(result) {
        forAll {
            result == listOf(0, 3, 4)
        }
    }

}
result
is 
list(1, 3, 4)
i just copied this from 
FoldTest
i was trying to determine whether 
Foldable
is sufficient to implement 
remove
what we've been talking about yesterday
and it works!
i just can't figure out how to do a simple assertEquals
😄
s
You're not doing any now. Weird that 
forAll
passed but not sure how it work without arguments.
It's meant for properly based testing.
Here I'd rewrite everything starting from 
with(result)
, to 
result shouldBe listOf(0, 3, 4)
. Does it fail then?
a
i'll try
failed
good
so the only question now is how to implement remove
because 
Foldable
is not a 
Monoid
we don't have 
compose
nor 
identity
Copy code
fun <A> Kind<F, A>.remove(element: A): Kind<F, A> = foldLeft(???) { foldable, next ->
    if(element == next) {
      foldable
    } else foldable ??? next
  }
s
Right, so basically we could only have 
fun <A> Kind<F, A>.remove(element: A, MA: Monoid<A>): Kind<F, A>
in 
Foldable
.
And the more desired 
fun <A> Kind<F, A>.remove(element: A): Kind<F, A>
can only live in 
FunctorFilter
.
a
that's what I thought
but i'm not sure what goes here
Copy code
fun <A> Kind<F, A>.remove(element: A, monoid: Monoid<A>): Kind<F, A> = foldLeft(monoid.empty()) { foldable, next ->
    if(element == next) {
      foldable
    } else monoid.???
  }
I'm a bit lost here 😞
s
I’m still wondering if it’s possible 😄
a
well
you need two monoids
s
Ye that’s what I was going to say
a
one for Kind<F, A> and one for Kind<A>
s
You need 
MonoidK
for 
F
.
a
yes
s
Not sure how much sense it still makes at that point. I mean it’s definitely possible but to what extend would it still be user friendly instead of using 
FunctorFilter
.
a
i'd say user friendliness factor is around 
0.2%
😂 1
s
Grouping 
remove
with 
filter
makes more sense to me than grouping it with 
fold
.
a
yes
i'm also not sure how I can implement it with fold as 
combine
is an extension function
and there is no function to create a monoid and 
add
the next element to it
or is there?
Copy code
fun <A> Kind<F, A>.remove(element: A, MF: MonoidK<F>, MA: Monoid<A>): Kind<F, A> = MF.run {
    foldLeft(empty()) { acc, a ->
      if (a == element) {
        acc
      } else ???
    }
  }
you'd need some kind of monoid combinator
Monoid<MonoidK<F>>
?
😄
s
Copy code
fun <A> Kind<F, A>.remove(element: A,
                          monoid: Monoid<A>,
                          monoidK: MonoidK<F>,
                          AF: Applicative<F>): Kind<F, A> = AF.run {
  foldLeft(AF.just(monoid.empty())) { foldable: Kind<F, A>, next: A ->
    if (next == element) foldable
    else monoidK.run { foldable.combineK(AF.just(next)) }
  }
}
a
I still don't understand the use of 
Applicative
😞
s
MonoidK
is what you’re looking for, it’s meant to combine `F`s, 
* -> *
or constructors with a typehole.
Applicative is needed here because 
monoid.empty()
returns 
A
but the return type of our 
foldLeft
needs to be 
Kind<F, A>
so we need to lift it.
a
yep I use it in my example above
I was just not aware of the functionality 
Applicative
provides
s
Ah, it offers 
just
which can 
(A) -> Kind<F, A>
a
can you explain in a few words how 
Applicative
works? I'm kinda lost here
s
So we can lift 
A
into 
F
, and then we can use 
MonoidK
to combine 
F
. You can overload this function in 
Traverse
and default supply the 
Applicative
instance.
Let me add some intermediate steps with type info
a
👍
s
Copy code
fun <A> Kind<F, A>.remove(element: A,
                          monoid: Monoid<A>,
                          monoidK: MonoidK<F>,
                          AF: Applicative<F>): Kind<F, A> {
  val emptyValue: A = monoid.empty()
  val liftedEmpty: Kind<F, A> = AF.just(emptyValue) 
  
  return foldLeft(liftedEmpty) { foldable: Kind<F, A>, next: A ->
    if (next == element) foldable
    else monoidK.run {
      val liftedNext = AF.just(next)
      val newlyAccumulated = foldable.combineK(liftedNext)
      newlyAccumulated
    }
  }
}
a
so what 
just
does is it wraps a value in a context?
s
So Applicative is simply 
fun <A> just(a: A): List<A> = listOf(a)
a
which supplies the behavior
s
Exactly
a
just like 
Option.just(1)
s
Yep, and we need to stay in 
F
so we can accumulate the results in our collections. 
MonoidK.combineK
is append or 
+
for 
List
.
a
so that's why we need to keep lifting the 
next
values?
in whatever actual foldable the user provides
so this whole thing evaluates to 
listOf()
+ 
listOf(1)
+ 
listOf(3)
+ 
listOf(4)
?
s
While explaining I noticed there is a mistake and the solution is actually easier.
Give me a sec so I can properly write it down to now confuse you 😜
a
ok
you don't need AF.just
s
So here we 
foldLeft
over our original 
Kind<F, A>
, and as an initial value we pass an “empty context”. I thought the empty context could be constructed by using 
Monoid
+ 
Applicative
, but that’s inaccurate. 
Monoid<Int>
returns 
0
on 
empty
so wrapping it with 
Applicative#just
results in 
listOf(0)
instead of 
emptyList()
So what we want instead is simply 
MonoidK
, which it’s 
empty
returns 
emptyList()
.
a
because 
monoidK
has 
empty
s
Yes exactly
No need for 
Monoid
either.
You still need Applicative.
a
Copy code
fun <A> Kind<F, A>.remove(element: A,
                            monoidK: MonoidK<F>,
                            AF: Applicative<F>): Kind<F, A> {
    val emptyValue = monoidK.run {
      empty<A>()
    }

    return foldLeft(emptyValue) { foldable: Kind<F, A>, next: A ->
      if (next == element) foldable
      else monoidK.run {
        foldable.combineK(AF.just(next))
      }
    }
  }
s
Yes that’s it.
a
wait a sec
s
Copy code
val emptyValue = monoidK.run {
      empty<A>()
    }
Can simply be 
monoidK.empty<A>()
So this boils down to 
emptyList() + listOf(1) + listOf(3) + listOf(4)
for 
ListK.foldable().run { listOf(1, 2, 3, 4).k().remove(2) }
emptyList().combineK(listOf(1).combineK(listOf(3).combineK(listOf(4))))
=> 
monoidK.empty().combineK(just(1).combineK(just(3).combineK(just(4))))
If that still makes any sense 😄
a
can you explain in layman's terms what an 
Applicative
is?
yes it recursively yanks out the elements from the foldable and combines them in a new one
so 
Applicative
is for yanking?
s
Hmm I am thinking of a good description but it’s not easy for 
Applicative
😅 In Arrow it only adds the power to lift values into 
F
on top of 
Functor
.
a
seems like we're on the right track:
Copy code
"Should be able to remove from Foldable" {

    val result = ListK.foldable().run { listOf(1, 2, 3, 4).k().remove(2, ListK.monoidK(), ListK.applicative()) }

    result shouldBe listOf(1, 3, 4)
}
this passes
so it adds 
just
btw shouldn't we use 
Eq
instead of 
==
?
s
Exactly, https://github.com/arrow-kt/arrow/blob/master/modules/core/arrow-core-data/src/main/kotlin/arrow/typeclasses/Applicative.kt However it’s better know for 
ap
, which is not that useful in Kotlin and split off in 
Apply
. What is more interesting there is the derived functions which allow for combining N types wrapped in 
F
.
Copy code
ListK.applicative(listOf(1, 2), listOf(3, 4)) { (a, b) -> Tuple2(a, b) }
//ListK(list=[Tuple2(a=1, b=3), Tuple2(a=1, b=4), Tuple2(a=2, b=3), Tuple2(a=2, b=4)])
Ye we should use 
Eq
instead of 
==
but most of the tests that aren’t using 
Eq
have been there for a long time. We haven’t actively gone back to tests to rewrite them.
a
when i started my journey into FP I thought that monads will be the hardest concept to grasp
but it is applicatives
😄
I'm flabbergasted
s
Yes but functions wrapped in contexts aren’t very nice in Kotlin. It requires a bunch of manual currying and partial application which quickly becomes hard to read.
a
yep I saw it in VAVR.....
s
That’s why I mentioned that the derived functionality is much more interesting in Kotlin and probably VAVR.
a
take a look
man I need to learn Haskell now
but back to our topic
s
For example, let’s say we write a simple function that combines 2 
F
and turns them into a tuple.
Copy code
fun <F, A, B> Applicative<F>.tupled(fa: Kind<F, A>, fb: Kind<F, B>) : Kind<F, Tuple2<A, B>> {
  val ff: Kind<F, (B) -> Tuple2<A, B> = fa.map { a -> { b ->   Tuple2(a, b) } }
  return fb.ap(ff)
}
a
this is not very ergonomic: 
listOf(1, 2, 3, 4).k().remove(2, ListK.monoidK(), ListK.applicative())
s
We could’ve done the same with 
Monad
and 
flatMap
but that means it’ll always be sequential.
a
i'm not following
s
But for 
IO
we could write an 
Applicative
that uses 
parMapN
to combine 2 values in parallel.
This is ~~ similar to Either vs Validation with error accumulation.
a
the parallel part is a bit of a dark area for me
never done that with Arrow
s
It would be more ergonomic when the compiler can inject the instances, but we can also provide a more ergonomic 
FunctorFilter
alternative
Nobody has since the PR is not merged 😄
In the next version you can ask every 
Concurrent
typeclass for a 
parApplicative()
instance.
This’ll mean that you can run programs written with 
Applicative
in a concurrent/parallel manner with guarantees about cancelation, error handling and resource safety etc.
a
so i still not get it why an 
Applicative
is capable of doing that
s
In Haskell Applicative and Apply are 1. I am not sure about other langs but in Scala it’s also split.
a
i'm trying to make sense of this
oh I see
Apply
has no kdocs 😢
s
😢
a
but now I understand this part: 
fun <A, B> Kind<F, A>.ap(ff: Kind<F, (A) -> B>): Kind<F, B>
i'm going to improve the kdocs in a future pr
s
🙏 That would be awesome!
a
so what 
Apply
does is that it applies a function wrapped in a context to a value wrapped in a context
☝️ 1
👍
what i'm not 100% sure about is what is the utility of this?
man, Arrow kills IDEA on my crappy mac
s
hahaha. It can also kill the high-end model if you try 😜
a
i don't like macs to be honest
s
It’s a super popular operator in Haskell due to currying, it’s not used very often in Scala either.
a
so how do I get parallel decomposition with this?
s
?
a
oh wait a second I think I get it
because both the function and the value is wrapped we can exert fine-grained control over the actual value on both sides, right?
by "both sides" i mean input and output
s
Exactly
a
wow
thanks for the explanation
s
Glad I could help you out 👍
a
👍
how do you thing we could mix 
Eq
into this implementation of 
remove
?
s
I’d probably do something like this. 
Eq.any()
is 
==
.
Copy code
fun <A> Kind<F, A>.remove(element: A,
                          monoidK: MonoidK<F>,
                          AF: Applicative<F>,
                          eq: Eq<A> = Eq.any()): Kind<F, A> =
  foldLeft(monoidK.empty()) { foldable: Kind<F, A>, next: A ->
    if (eq.run { next.eqv(element) }) foldable
    else monoidK.run { foldable.combineK(AF.just(next)) }
  }
cc\ @raulraja we need KEEP-87 xD
a
😄
r
I’m working on it!
😘 2
as we speak!
Copy code
val MetaComponentRegistrar.typeClasses: List<ExtensionPhase>
  get() =
    meta(
      classOrObject(::isExtension) { ktClass ->
        val typeClass = ktClass.typeClassName()
        val typeArgs = ktClass.typeArgumentNames()
        val factoryName = typeClass.decapitalize()
        println("intercepted ${ktClass.name}")
        listOf(
          ktClass.text,
          "fun $factoryName(): $typeClass<${typeArgs..","}> = TODO()"
        )
      },
      IrGeneration { compilerContext, file, backendContext, bindingContext ->
        file.transformChildren(object: IrElementTransformer<Unit> {

        }, Unit)
      }
    )
xD
check out the collection of declarations spreads for templates 
typeArgs..","
where 
","
can be any other delimiter
s
😲
Is that range?
r
yes
s
love it
cool find
That was the worst thing ever in kapt
r
Copy code
private operator fun <A> List<A>.rangeTo(s: String): String =
  joinToString(s)
👌 1
a
where would you put this extension function?
Copy code
fun <A> Kind<ForListK, A>.remove(element: A) = remove(element, ListK.monoidK(), ListK.applicative())
i've put it here:
Copy code
@extension
interface ListKFoldable : Foldable<ForListK> {
  override fun <A, B> Kind<ForListK, A>.foldLeft(b: B, f: (B, A) -> B): B =
    fix().foldLeft(b, f)

  override fun <A, B> Kind<ForListK, A>.foldRight(lb: Eval<B>, f: (A, Eval<B>) -> Eval<B>): Eval<B> =
    fix().foldRight(lb, f)

  override fun <A> Kind<ForListK, A>.isEmpty(): kotlin.Boolean =
    fix().isEmpty()

  fun <A> Kind<ForListK, A>.remove(element: A) = remove(element, ListK.monoidK(), ListK.applicative())
}
as part of adding 
remove
to 
Foldable
I'm going to augment all implementations with this to keep it ergonomic
s
That function won’t be accessible since it’s only known in the 
ListKFoldable
interface.
a
my test passes
Copy code
"Should be able to remove from Foldable" {

  val result = ListK.foldable().run { listOf(1, 2, 3, 4).k().remove(2) }

  println(result)

  result shouldBe listOf(1, 3, 4)
}
oh wait a sec this is because it is int the context of 
Foldable
what is the best practice in this case?
I thought that 
@extension
will create an unboxed extension function
s
We typically put these either in the class of type itself as an instance method. Reason is that people mostly work either with polymoprhic with typeclasses or with concrete types.
a
this goes to 
ListK
then, thanks
s
It does but only for the functions defined in the typeclass, not for additional defined functions in the impl.
a
remove
would make 
ListK
invariant 😞
right now it is 
<out A>
s
Right, extension function below 
ListK
it is. The only way to walk around that problem now since Kotlin doesn’t allow for variance in functions.
p
jesus this thread
worth moving to a private room?
s
probably yes
➕ 1
a
this might be a stupid question
but I have trouble finding the 
remove
function we imlpemented
Copy code
fun <A> ListK<A>.remove(element: A): ListK<A> = this.??? // can't find it
fix()
doesn't help either
i've checked the other extension functions which are defined and they are using the functions defined in 
ListK
itself
is this because the 
Foldable
functions are implemented in 
ListKFoldable
?
s
Right, that’s not a stupid question. That’s what we’re trying to solve by implementing the KEEP-87 in compiler plugins. It should be under 
import arrow.core.extensions.listk.foldable.remove
We currently expose those functions with as global extension functions which resulted in horrible IDEA support and performance. So we compared a couple solutions and with compiler plugins we’ll be able to inject those functions directly in the concrete types.
a
I see
s
So with KEEP-87 and HKT plugin you’ll be able to implement a typeclass’s abstract behavior and you’ll also get all the derived behavior available in the concrete types on top of having it available using typeclasses.
a
btw to implement 
remove
for 
ListK
we could just use the wrapped `List`'s 
remove
ok I'll skip this for now then
s
Yes, that would be the efficient overload for that function.
a
as long as this works I'm fine for this preliminary implementation:
Copy code
"Should be able to remove from Foldable" {

  val result = ListK.foldable()
    .run { listOf(1, 2, 3, 4).k() }
    .remove(2, ListK.monoidK(), ListK.applicative())

  result shouldBe listOf(1, 3, 4)
}
I see no test class for 
Foldable
though
s
Those are in 
arrow-test
they’re implemented as an abstract test suite. Called 
FoldableLaws.laws(...)
a
I see
s
1 test suite for n implementations 🙂
a
👍
i'll try to implement a test for remove
what do you think about this 
PersistentMap
implementation?
Copy code
/**
 * A [PersistentMap] is an immutable [Map] which implements structural sharing.
 */
@higherkind
data class PersistentMap<K, V>(private val map: Map<K, V>) : PersistentMapOf<K, V> {

  val isEmpty: Boolean = map.isEmpty()
  val size: Int = map.size

  operator fun get(key: K): Option<V> = Option.fromNullable(map[key])

  fun getOrElse(key: K, defaultValue: V): V = map.getOrElse(key) { defaultValue }

  fun containsKey(key: K): Boolean = map.containsKey(key)

  fun put(key: K, value: V): PersistentMap<K, V> {
    TODO()
  }

  fun remove(key: K): PersistentMap<K, V> {
    TODO()
  }
}
p
getOrElse is implicit by using Option for get
get(1).orElse { 1 }
a
this is how it looks like now:
Copy code
/**
 * A [PersistentMap] is an immutable [Map] which implements structural sharing.
 */
@higherkind
data class PersistentMap<K, V>(private val map: HashArrayMappedTrie<K, V>) : PersistentMapOf<K, V> {

  val isEmpty: Boolean = map.isEmpty
  val size: Int = map.size

  operator fun get(key: K): Option<V> = map[key]

  fun containsKey(key: K): Boolean = map.containsKey(key)

  fun put(key: K, value: V): PersistentMap<K, V> {
    return PersistentMap(map.put(key, value))
  }

  fun remove(key: K): PersistentMap<K, V> {
    return PersistentMap(map.remove(key))
  }
}
I'm so psyched
i almost have it working
p
yay 😄
a
i've learned more in this last week about FP than in the last year combined
p
that's what you happen when you implement stuff hahaha
a
😄
so do we move this convo into a room?
just to reiterate:
the implementations I see in 
MapK
are necessary because we don't have KEEP-87 yet, right?
so I'll need to replicate them in 
PersistentMapK
s
No, that's because we cannot make the std Map extend 
Kind
.
Which you already do for 
PersistentMap
a
got it
so I only have to add the implementations for the typeclasses?
like in 
mapk.kt
although I'm not sure how that should work?
what do I have to do to make 
PersistentMapK
a 
Foldable
apart from this?
Copy code
@extension
interface MapKFoldable<K> : Foldable<PersistentMapKPartialOf<K>>
how do I know what I need to override?
s
Same as you'd do in oop, the onces that provide better performance than the default impl.
a
so just by adding this I've made it a 
Functor
?
Copy code
@extension
@undocumented
interface PersistentMapKFunctor<K> : Functor<PersistentMapKPartialOf<K>>
s
Ah sorry. There you should implement `Functor`'s abstract functions so 
PersistentMapKFunctor
becomes an interface with no abstract functions.
a
i'm a bit lost
s
For 
Functor
that's only 
map
if I'm not mistaken.
a
i can't call 
map
on my 
PersistentMapK<Int, Int>()
s
Sec
a
even though I have
Copy code
@extension
@undocumented
interface PersistentMapKFunctor<K> : Functor<PersistentMapKPartialOf<K>>
which I copied from 
mapk.kt
i tried the official docs but I didn't find a guide for implementing my own typeclasses
s
Copy code
@extension
@undocumented
interface PersistentMapKFunctor<K> : Functor<PersistentMapKPartialOf<K>> {
   override fun <A, B> PersistentMapKOf<A>.map(f: (A) -> B): PersistentMapK<B> =
     fix().map(f)
}
Now that you’ve implemented all abstract methods of 
interface Functor<F>
, we can no generate 
fun <K> PersistentMapK.Companion.functor(): Functor<PersistentMapKPartialOf<K>> = object : PersistentMapKFunctor<K> { }
r
fix().map
Damm Simon beat me
a
i'll try thanks
s
haha 😄 You can also overload other functions that 
Functor
provides with faster implementations, but that’s optional.
Did you implement 
map
on 
PersistentMapK
?
a
no
you said that I don't need it
r
You are gonna need roughly the same api MapK specializes map, fold etc
To implement Foldable, FunctorFilter etc
Each type class instance will delegate to the actual function via fix. This will change with compiler plugins and arrow meta at the end of the year
s
With KEEP-87 😕 Sorry if I was unclear. Our current strategy is to implement all abstract typeclass functions in the data types directly so that in the interface impl we can delegate to them by moving between kinded and concrete world using 
fix
. I.e. 
fix().map(f)
. So if we look at 
Option
it looks like this with only the Functor impl.
Copy code
@higherkind sealed class Option<out A> : OptionOf<A> {
  object None: Option<Nothing>()
  data class Just<A>(val a: A): Option<A>()
  fun <B> map(f: (A) -> B): Option<B> = ...
}

interface OptionFunctor : Functor<ForOption> {
   fun <A, B> OptionOf<A>.map(f: (A) -> B): Option<B> =
     fix() //returns Option<A>
       .map(f)
}
a
so then I do have to implement these functions just like in 
MapK
s
Sorry for the confusion
a
even though we can implement 
PersistentMapKOf
s
PersistentMapKOf
is simply 
typealias PersistentMapKOf<K, V> = Kind2<ForPersistentMapK, K, V>
What we can do with the compiler plugins is tell the compiler that 
PersistentMapK<K, V>
is equal to 
PersistentMapKOf<K, V>
and additionally we can tell the compiler that 
PersistentMapK
has all the functions that are implemented by the typeclasses for 
ForPersistentMapK
.
a
I mean you said
message has been deleted
s
With that last bit there won’t be the need to manually delegate
a
that I don't have to replicate them
but as it turns out I do have to?
s
Oh, I miss-understood you there.
a
😄
ok so is it enough if I implement 
map
like this:
Copy code
@extension
@undocumented
interface PersistentMapKFunctor<K> : Functor<PersistentMapKPartialOf<K>> {
  override fun <A, B> Kind<PersistentMapKPartialOf<K>, A>.map(f: (A) -> B): Kind<PersistentMapKPartialOf<K>, B> {
    TODO("not implemented")
  }
}
s
Yes, that is the minimum definition of a 
Functor
a
if I understood you correctly then yes, because 
PersistentMapK
is already a kind and kapt can work its magic
👍
why am I getting
Copy code
> Task :arrow-persistent-data-structures:kaptKotlin FAILED
e: error: Arrow's annotations can only be used on Kotlin classes. Not valid for error.NonExistentClass
after each build?
I need to manually remove 
PersistentMapKOf
from 
PersistentMapK
then rebuild then re-add it
s
Ai, you have 
@higherkind
and 
@extension
in the same module?
This is a kapt issue 😕 I’d suggest to just put the 
@higherkind
boilerplate in the module for now.
a
ok
i can't wait to get rid of kapt
➕ 1
I need to add a 
companion object
to 
PersistentMapK
just realized
do you have a doc somewhere for prospective typeclass implementors?
btw 
remove
is not going to work since 
Foldable
folds the values
but 
remove
works with the 
key
, not the value 😞
maybe I'm implementing 
Foldable
the wrong way
anyway my brain just melted for today so I'm gonna shelve this for now
s
Hmm... Actually for complex immutable structures I can also recommend looking 
Optics
.
You're not implementing 
Foldable
wrong. We don't know the type of the 
key
inside 
Foldable
.
a
I need to know the type of 
key
in order to implement an efficient 
remove
operation
s
We'll have the same problem with 
key
for 
FunctorFilter
.
a
although I already have a 
remove
function in 
PersistentMap
this is where i'm at right now with the fork
it works but it is a bit rough around the edges
s
And we don't know the type there. We'd have to create an 
IndexedFoldable
or 
IndexedFunctorFilter
a
most folks will use the 
remove(element)
function anyway
s
Yes, maps are indexed structures so they need indexed typeclasses but we don't have any of those.
Having this for other immutable structures would be great. Remove is much nicer when you would filter on a constant.
Nice work!
a
should I open a PR so you can review it?
s
That's probably easiest to make comments and talk code.
a
👍
is it possible that the build failed because of KTlint?
Copy code
Missing newline before ")"
I feel physical pain if I can't put the 
)
at the end of the line (just like in Clojure)
also why is this a build failure?
s
We rather wanted to have a CI controlled styled than a user controlled one.
Consistency or OCD. Pick one ;p
a
hehe
i'll fix this
although i've been pressing the format command
so there's something amyss here
the build succeeds locally but fails remotely 😞
@Imran/Malic
i
@addamsson did you fix your formating issue, if not it may lay here:
Copy code
fun <A> Kind<F, A>.remove(element: A,
	                            monoidK: MonoidK<F>,
	                            AF: Applicative<F>): Kind<F, A> {
I would rather inline it
s
./gradlew ktlintFormat
should fix all style isssues, and the onces it cannot like 
*
imports will get linked in the console.
a
I didn't have time since I opened the PR, but I'll fix it today evening!
s
No rush 🙂 Whenever you have time is great 👍
a
@Imran/Malic is there something specific which you wanted to talk about?
I'm not familiar with the 
Traverse
typeclass, but we discussed 
Foldable
with @simon.vergauwen
s
Traverse
inherits from 
Foldable
and 
Functor
and is a very popular and powerful typeclass to do operations.
Copy code
fun getUserById(id: Int): IO<User> = ...
val operations: List<IO<User>> = listOf(1, 2, 3).k().map(::getUserById)
val sequenced: IO<List<User>> = operations.sequence(IO.applicative())

val traversed: IO<List<User>> = listOf(1, 2, 3).k().traverse(IO.applicative()) { id -> getUserById(id) }
Having 
List<IO<User>>
is useless to work with so you need to be able to swap the order of the contexts.
☝️ using 
IO.parApplicative()
which we discussed earlier will automatically make this work in parallel. Which is exactly what we I did in that PR I shared, 
parTraverse
is just an alias for 
traverse
with 
parApplicative()
.
a
what is the use of 
IO
?
i'm not sure I understand the purpose of 
Traverse
when you do things in parallel how does it work under the hood?
s
It’s an effect type similar to 
io.reactivex.Single
, 
reactor.Mono
which are both pure and fairly principled. You can also see it as a FP version of 
kotlinx.coroutines.Deferred
, or Scala Future.
a
coroutines?
s
IO
uses coroutines for threading under the hood yes
a
@simon.vergauwen which one, 
IO
or 
Traverse
?
i
Traverse is the typeclass
a
I mean 
IO
~ 
Deferred
or 
Traverse
~ 
Deferred
?
s
IO
~ 
Deferred
i
IO is our main datatype in effects aka Fx
a
what's an effect?
i
Are you familiar with cats-effects
The one from scala
a
I have 
0
Scala knowledge
s
effect is just short for side-effect.
a
I came from a Clojure/Java background
s
Oh Clojure cool
a
there is a reason why I contribute persistent data structures 😄
s
Anyway, Traverse is useful when you are in context 
F
and you want to run functions that return 
G
. So in our example our original context was 
List
and we wanted to run functions that return 
IO
. But a simpler example maybe.
Copy code
fun getOptionalUser(id: Int): Option<User> = ..
listOf(1, 2, 3).k().traverse { id -> getOptionalUser(id) }
If we use map here then you’d end up with 
List<Option<User>>
but lets say I am not interested in having empty values (
None
) in my list. So I want to short-circuit just like `map`/`flatMap` for 
Option
and have an 
Option<List<User>>
which either contains all users or 
None
.
a
what will 
listOf(1, 2, 3).k().traverse { id -> getOptionalUser(id) }
return?
s
Option<List<User>>
a
so it not only maps (
Functor
) but also folds 
Foldable
?
s
Exactly, hence 
interface Traverse<F> : Functor<F>, Foldable<F>
a
hm
how does this relate to 
Applicative
?
or rather 
Apply
s
You need to supply 
Applicative<G>
so that you can use 
map2
to combine 2 
G
elements.
a
as it seems that this takes a wrapped value and returns a wrapped value
s
yes but it swap containers.
Copy code
fun Kind<G, Kind<F, A>>.sequence(AF: Applicative<F>): Kind<F, Kind<G, A>> = traverse(AF, :identity)

val listOfOptions: List<Option<Int>> = listOf(1.some(), 2.some())

listOfOptions.sequence() //Some([1, 2])
listOf(1.some(), None).sequence() // None
☝️ this is what made it click for me. Since 
listOf(1, 2).map { Some(it) }.sequence()
is the same as 
listOf(1, 2).traverse { Some(it) }
a
oh I see
👍
so can we move this convo to its own channel?
I've fixed the issues in the review
i'm going on a vacation for 2 weeks
i'll be back! 👍
s
Enjoy your vacation!
r
What are the laws of remove?
s
I'd imagine something like 
remove(a).find { a } == false
but currently we haven't defined any yet
r
Makes sense
@Imran/Malic I believe 'remove' belongs in Foldable and FunctorFilter if we can express a valid law for their type class
I think that is true for any other combinator unless it's overly specialized. Remove has clear semantics even if it can be expressed with just folds
And we are the ones making the law and shaping the typeclasses to how are best used.
i
@raulraja makes sense. Maybe there is a way to reconstruct some of the Foldable FunctorFilter Laws in away where remove is also tested. I post something here if I find something
10 Views
Open in Slack
PreviousNext
Powered by