Casting between list and IROL needed?

[ArbilGit]

Hi! A quick question please, something I've struggled to make work for some time. I have

type Wrapped = {nums: int list}
let numsL p = Optic.lens (fun w -> w.nums) (fun v w -> {w with nums = v}) p
let wrapped = {nums = [1;7]}

Now this composition doesn't compile

Optic.collect (numsL << Optic.elemsT) wrapped

with The type 'int list' does not match the type 'Optic.IROL<'a>'

Do I need explicit casting here, or an isomorphism? Thanks!

[polytypic]

The idea in this draft/prototype would be to use the IROL<_> or IReadOnlyList<_> type for read-only collections like that. So, then you'd just change the definition of Wrapped:

type Wrapped = {nums: IROL<int>}

This way you are not forced to use list<_>, which is typically inefficient, and still communicate that the nums collection is supposed to be immutable.

In case you can't change the Wrapped type (I assume this is just a minimal example to reproduce the difficulty), you could use an isomorphism:

Optic.collect (numsL << listAsIrolI << Optic.elemsT) wrapped

The code in this draft/prototype doesn't provide a listAsIrolI out of the box, but there is an rolistI for arrays.

[ArbilGit]

Thank you. Yup, just a minimal example.

Do you think the approach could benefit from FsharpPlus pseudo-typeclasses like Traversable or Indexable (or SRTP in general), for greater genericness and less copying of data? I'm thinking of dabbling in that.

[polytypic]

Hmm... I don't think I've considered using SRTPs in this context. It is entirely possible that you could use SRTPs or some other techniques to refine the interface in some cases.

Like the README says, I came up with the basic implementation technique when working on a C# project - so no such thing were available - and similar implementation techniques could be used in many other languages like Standard ML and OCaml that do not give you higher-kinded types. This is actually the thing that makes this interesting to me personally. In FP you often see people coming up with a particular implementation technique for some general concept and then more or less confusing the implementation with the general concept. It seems to me going something like "One can implement optics using this particular collection of types so this must be what optics are", but I think that is completely wrong. So, it is nice when people then later find alternative implementations that make different trade-offs. Looking at optics, in particular, there have been many different kinds of implementations and I doubt that we have yet seen all of them.

Note that the NetOptics.Optic module signature does not reveal any inline functions. This has the benefit that it can be separately compiled.

Internally the library actually tries to avoid copying collections. If you look at rolistI, you can see that it uses asList and asArray and those are casts (without copying) when the runtime types allow.

The internal implementation has also been designed to allow optic compositions to operate without requiring allocations per element. See the elemsT implementation, for example. In the inner loops A and B there are no allocations.

One thing that could be improved in elemsT is the casting logic, which kind of assumes that IROL<_>s are arrays (that is intention) as that is, for most use cases (manipulating arrays of at most few thousands of elements), going to be the fastest data structure for collections anyway. But one could specialize the code so that no extra copy is made.

While copying is (and can be further) avoided, the implementation is not inlining friendly. The calls, p.Invoke (...) to other optics in the "pipeline", almost certainly are not inlined by F# or .NET (which both traditionally have been rather simple compilers not doing any really fancy optimizations). Perhaps with a mostly inline function based implementation technique you could get the F# compiler to fuse optics, but the F# compiler has not in the past been very aggressive in inlining higher order functions.

[ArbilGit]

In FP you often see people (...) confusing the implementation with the general concept

Yup. It's a particular case of confusing a model with reality. It's just that in natural sciences one starts with reality and creates its model, while here one starts with a model (concept of a lens), and creates reality (its particular implementation).

You're right that the code doesn't do many copies. SRTPs would be more beneficial if we wanted to work with concrete types instead of IROLs, or if the lenses were mutating.

The implementation is impressively fast, especially given it uses only basic language features. Similar in speed to Scala's quicklens which is macro based. ~20 us for NetOptics, similar for quicklens, for a simple function generic over input shape. Comparison below, if you're curious.

NetOptics

// Every giver gives amount to every taker, generic on world shape
let manyToManyTransfer world givers takers amount =
  let giversList = Optic.collect givers world
  let totalReceive = amount*Seq.length giversList
  let totalGive = amount*(Optic.collect takers world |> Seq.length)
  if giversList |> Seq.forall (fun a -> a >= totalGive) then
      world
      |> Optic.over givers (fun a -> a - totalGive)
      |> Optic.over takers (fun a -> a + totalReceive)
  else failwith "Not enough funds"

type Bank = {Funds:int}
type Person = {Money:int; Name: string}
type World = {People: Person IROL; Bank: Bank}

let peopleL = Optic.lens (fun world -> world.People) (fun v world -> {world with People = v})
let moneyL = Optic.lens (fun person -> person.Money) (fun v person -> {person with Money = v})
let bankL = Optic.lens (fun world -> world.Bank) (fun v world -> {world with Bank = v})
let fundsL = Optic.lens (fun bank -> bank.Funds) (fun v bank -> {bank with Funds = v})

let world = {
  Bank = {Funds = 5}
  People = [|
      {Name = "Alice"; Money = 3}
      {Name = "John"; Money = 4}
  |]
}

let main _ =
  //Everyone pays 1 to the bank 
  let people = peopleL << Optic.elemsT << moneyL
  let bank = bankL << fundsL
  //Warmup with switched arguments
  for i = 1 to 1_000 do
      manyToManyTransfer world bank people 2
  time (fun() -> manyToManyTransfer world people bank 1)

quicklens

def transfer[W](world: W, givers: PathLazyModify[W, Int], receivers: PathLazyModify[W, Int], amt: Int) =
  val giversList = givers.get(world)
  val totalReceive = amt * giversList.length
  val totalGive = amt * receivers.length(world)

  if giversList.forall(_ >= totalGive) then
    world
    |> givers.using(_ - totalGive)
    |> receivers.using(_ + totalReceive)
  else throw new IllegalArgumentException

case class World(bank: Bank, people: List[Person])
case class Person(money: Int, name: String)
case class Bank(funds: Int)

val world = 
  World(
      Bank(5),
      List(
        Person(3, "Alice"), 
        Person(4, "John"))
      )

val users = modifyLens[World] (_.people.each.money)
val bank = modifyLens[World] (_.bank.funds)

for i <- 1 to 1_000 do
  transfer(world, bank, users, 2)
time(transfer(world, users, bank, 1))