对可变数据结构进行操作的函数可以是引用透明的吗？

Question

我正在开发一个网络应用程序并设计了以下特征来从远程机器读取文件：

trait ReadFileAlg[F[_], Dataset[_], Context]{
  def read(path: String, ctx: Context): F[Dataset[String]]
}

final class NetworkContext{
  private var fileDescriptor: Int = _
  private var inputStream: InputStream = _
  //etc
}

final class ReadFromRemoteHost[F[_]: Sync] extends ReadFileAlg[F, List, NetworkContext]{
  override def read(path: String, ctx: NetworkContext): F[List[String]] = Sync[F].delay(
    //read data from the remote host
  )
}

我在这里看到的问题是该实现接受 NetworkContext 作为参数，它是可变的并且包含与网络连接相关的 fileDescriptor 等字段。

这个函数read引用透明吗？

我认为是的，因为函数本身不提供对可变状态的直接访问（它在 Sync[F].delay 下），即使它接受可变数据结构作为参数。

Answer 1

IMO，read 的语义是

"When you apply me I am pure, however when you run me I have a side-effect."

有人说这是一种sleight of hand:

...we simply declare that a function returning an IO type may have arbitrary effects without going into detail in how these come about. The scheme has two consequences: First, the type of a function tells you whether it is referentially transparent or has side-effects when run.

例如，考虑以下具有可变状态的对象

object Foo {
  var x = 42
}

def f(foo: Foo.type): Int = foo.x

我们可以确认 f 不是引用透明的，因为

assert(f(Foo) == 42) // OK
assert(f(Foo) == 42) // OK
...
Foo.x = -11
...
assert(f(Foo) == 42) // boom! Expression f(Foo) suddenly means something else

但是重新实现 f 以达到 "suspend" 效果

def f(foo: Foo.type): IO[Int] = IO(foo.x)

类似于

def f(foo: Foo.type): Unit => Int = _ => foo.x

然后

magicalAssert(f(Foo) == (_ => foo.x)) // OK
magicalAssert(f(Foo) == (_ => foo.x)) // OK
...
Foo.x = -11
...
magicalAssert(f(Foo) == (_ => foo.x)) // Still OK! Expression f(Foo) did not change meaning

这里神奇的断言就像人脑一样，不会遇到停止问题，因此能够推断出函数行为的相等性，也就是说，应用 f 计算出值 (_ => foo.x)，这确实总是等于值 (_ => foo.x) 即使在某些时候 Foo.x 被突变为 -11.

但是，运行f的效果我们有

assert(f(Foo)() == 42) // OK
assert(f(Foo)() == 42) // OK
...
Foo.x = -11
...
assert(f(Foo)() == 42) // boom! expression f(Foo)() suddenly means something else

（注意我们如何通过 f(Foo)() 中的额外括号模拟 IO.run）

因此表达式 f(Foo) 是引用透明的，但是表达式 f(Foo)() 不是。

对可变数据结构进行操作的函数可以是引用透明的吗？

Can a function operating upon mutable data structure be referentially transparent?

functional-programming

scala

referential-transparency

scala-cats

cats-effect