文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
首页
学习
活动
专区
圈层
工具
MCP广场
返回腾讯云官网
社区首页 >问答首页 >如何表达不变性担保

问如何表达不变性担保
EN

Stack Overflow用户
提问于 2014-09-05 15:02:26
回答 3查看 181关注 0票数 2

下面的代码显示了由两个相同签名(RwA -> RwA)的函数处理某些记录的情况。然而，根据该变更器函数的实现，传递给它的数据可能被更改或不更改。

在一个更大的项目中，这样的事情是昂贵的。可能在维护或优化期间，函数的实现发生了更改，或者添加了更多的更改函数，程序看起来仍然相同，但突然以意想不到的方式运行。

因此，问题是:在这个示例中是否有任何方法来呈现代码，很明显(并检查了编译器)，类型为RwAChanger的函数可以也可能不会更改作为参数传递的数据？

请不要回答“不要使用数组”，因为这可能是大量的数据，例如三维网格的顶点或类似的，其中的性能将是一个问题。此外，我相信还可以找到其他示例，这些示例不涉及产生相同类型问题的数组。

代码语言：javascript
运行
复制
// A record with arrays...
type RwA =
    {
        A : int array
        I : int array
    }

let x = [| for i in 0..10 -> i |]

let init a =
    { A = a; I = Array.map (fun v -> -v ) a }

// This function creates a new array as member A in RwA
let change (o : RwA) : RwA =
    { o with A = Array.map (fun v -> v + 42) o.A }

// This function modifies the value of the array in member A of an RwA instance.
let change2 (o: RwA) : RwA =
    o.A.[0] <- 666
    o

let dump (o : RwA) =
    printfn "{ A = %A; I = %A; }" o.A o.I
    o

let dumpA (a : int array) : int array =
    printfn "x = %A" x
    a

// Is there a way to express a contract about immutability?
type RwAChanger = RwA -> RwA

let transmogrify (changer : RwAChanger) a =
    a
    |> dumpA
    |> init
    |> dump
    |> changer
    |> dump
    |> ignore

let test() = 
    transmogrify change x
    dumpA x |> ignore
    transmogrify change2 x    
    dumpA x |> ignore

do test()
f#
EN

回答 3

Stack Overflow用户

回答已采纳

发布于 2014-09-07 15:47:36

因此，问题是:在这个示例中是否有任何方法来呈现代码，很明显(并检查了编译器)，类型为RwAChanger的函数可以也可能不会更改作为参数传递的数据？

答案基本上是肯定的；通常可以对属性进行编码，例如一个对象是否可以使用类型被某个特定的函数更改。最基本的技术是使用抽象类型。您定义了一组类型，一种类型对应于您希望区分的每种不同类型的访问，以及这些类型上的相关操作。

例如，在这种情况下，可以定义两种类型。首先，定义一个与只读视图相对应的类型：

代码语言：javascript
运行
复制
// Read-only objects
module RA =
  type RA
  val change: RA -> RA
  // and other operations on read-only objects

在上面的签名中，重要的是RA类型是左抽象的。只有在签名中定义的操作才能用于操作RA类型的对象。

然后，您还将定义另一个与读写视图相对应的类型：

代码语言：javascript
运行
复制
// Read-write objects
module RwA =
  type RwA
  val change: RwA -> RwA
  // and other operations on read-write objets

此签名还保留RwA抽象类型。此外，还允许将RwA对象视为RA对象：

代码语言：javascript
运行
复制
val readonly: RwA -> RA

反之亦然！

现在，只使用读操作的函数将被赋予接受RA类型对象的类型，而使用写操作的函数将被赋予接受RwA对象的类型。

上述方案的一个不便之处在于，为了对读-写对象使用只读操作，需要使用readonly操作显式地将读-写对象转换为只读对象：

代码语言：javascript
运行
复制
RwA.readonly (x: RwA.RwA) |> RA.change

有一个叫做幻影类型的技巧，它通常可以消除这种显式转换的需要。不是定义多个抽象类型，而是向抽象类型中添加一个或多个额外的类型参数来编码所需的属性。

作为幻影类型的一个例子，让我们为读-写数组定义一个类型，RWArray<'rw, 't>，它允许一个人区分一个操作是否可以修改数组的元素。首先，这是签名：

代码语言：javascript
运行
复制
// RWArray.fsi

type R
type W
type RWArray<'rw, 't>

module RWArray =
  val zeroCreate: int -> RWArray<W, 't>
  val readonly: RWArray<_, 't> -> RWArray<R, 't>
  val length: RWArray<_, 't> -> int
  val get: RWArray<_, 't> -> int -> 't
  val set: RWArray<W, 't> -> int -> 't -> unit

RWArray<'rw, 't>类型具有类型参数'rw，用于编码一个对象是否可以修改。在这种情况下，只有一个变异操作，即set操作，它要求类型参数可以与W统一。其他操作允许类型参数为任意类型。换句话说，对于幻影类型参数'rw，只读操作是多态的.

花点时间找出(或尝试使用编译器)下列函数定义的类型：

代码语言：javascript
运行
复制
let modify xs x2x =
  for i=0 to RWArray.length xs - 1 do
    RWArray.set xs i << x2x <| RWArray.get xs i

let map xs x2y =
  let ys = RWArray.zeroCreate (RWArray.length xs)
  for i=0 to RWArray.length xs - 1 do
    RWArray.set ys i << x2y <| RWArray.get xs i
  ys

如您所见，modify操作的类型需要一个可写数组，而map操作不需要。现在，在定义高阶操作时，可以约束作为参数的函数，使其不允许数组发生变异。下面是一个示例：

代码语言：javascript
运行
复制
let sillyExample (effect: RWArray<R, int> -> unit) : unit =
  let rwa = RWArray.zeroCreate 1
  RWArray.set rwa 0 31
  effect (RWArray.readonly rwa)
  RWArray.set rwa 0 (RWArray.get rwa 0 + 10)
  effect (RWArray.readonly rwa)

在上面的函数定义中知道的是，对effect的调用不能修改作为参数给出的数组(嗯，不使用反射)。注意，在上面，需要使用readonly操作将数组交给effect函数，但是对RWArray.get的调用不需要它。

可以避免使用readonly，方法是为effect操作使用另一种类型，该类型将要求该效果相对于'rw参数具有多态性：

代码语言：javascript
运行
复制
type Effect =
  abstract Invoke: RWArray<'rw, int> -> unit

let sillyExample2 (effect: Effect) : unit =
  let rwa = RWArray.zeroCreate 1
  RWArray.set rwa 0 31
  effect.Invoke rwa
  RWArray.set rwa 0 (RWArray.get rwa 0 + 10)
  effect.Invoke rwa

上述变化与以前的变化本质上具有相同的性质。换句话说，众所周知，对effect.Invoke的调用不能修改数组。

RWArray模块和相关类型的实现非常简单：

代码语言：javascript
运行
复制
// RWArray.fs

type R = | R
type W = | W
type RWArray<'rw, 't> = {RWArray: array<'t>}

module RWArray =
  let zeroCreate n : RWArray<W, 't> = {RWArray = Array.zeroCreate n}
  let readonly (rwa: RWArray<_, _>) : RWArray<R, _> = {RWArray = rwa.RWArray}
  let length rwa = rwa.RWArray.Length
  let get rwa i = rwa.RWArray.[i]
  let set (rwa: RWArray<W, _>) i x = rwa.RWArray.[i] <- x

术语“幻影类型”背后的原因是类型参数'rw只显示为类型参数。如您所见，它不在RWArray<'rw, 't>类型定义的右侧使用。

这种方法的实际实现可能会定义更多的操作。

有许多有趣的论文描述了使用ML样式类型系统编码属性的技术。我只提到一篇论文：没有更长的外国:教一个ML编译器说C“本地”。。我还要提到我几年前写的一篇文章：编码任意有限关系的幻影布尔函数。

这里有一个练习：设计，这是读写数组的一个更精化的版本，可以指定可以读取数组长度和

  • 没有其他的，或者
  • 也可以写入数组，或
  • 也只能从数组读取，或
  • 也可以从数组中读取和写入数组。
票数 2
EN

Stack Overflow用户

发布于 2014-09-05 15:48:41

我认为没有办法告诉编译器，现有的可变类型应该是不可变的，也不能像@mydogisbox在注释中提到的那样使用Contracts。

但是，您可以从ImmutableArray记录中的Microsoft.Bcl.Immutable包中使用RwA。数组访问的性能差异应该是最小的。

票数 4
EN

Stack Overflow用户

发布于 2014-09-06 09:03:34

如果希望编译器错误区分更改的值和未更改的值，这很大程度上意味着不能对这两种函数使用相同的签名。

所以你不能使用：

代码语言：javascript
运行
复制
type RwAChanger = RwA -> RwA

但你可以选择这样的东西：

代码语言：javascript
运行
复制
type RwAChanger = RwA -> Changed RwA
type RwAUnchanger = RwA -> Unchanged RwA

它能准确地指示函数所做的事情。用你的例子：

代码语言：javascript
运行
复制
type Changed<'T> = Changed of 'T
type Unchanged<'T> = Unchanged of 'T

let change2 (o: RwA) : RwA =
    o.A.[0] <- 666
    Changed o

let dump (o : RwA) =
    printfn "{ A = %A; I = %A; }" o.A o.I
    Unchanged o

您还可以创建一些帮助程序来执行类型安全的map和bind。下面是一个小型库的示例：

代码语言：javascript
运行
复制
module ChangeLib =

   type Changed<'T> = Changed of 'T
   type Unchanged<'T> = Unchanged of 'T

   type Changer<'T> = 'T -> Changed<'T>
   type Unchanger<'T> = 'T -> Unchanged<'T>

   let mapC f (Changed v) = Changed (f v) 
   let mapU f (Unchanged v) = Unchanged (f v) 

   /// if input is Unchanged and f returns a Changed, 
   /// the whole expression is Changed
   let bindUC (f:'a Changer) (Unchanged v) = f v 

   /// if input is Unchanged and f returns a Unchanged, 
   /// the whole expression is Unchanged
   let bindUU (f:'a Unchanger) (Unchanged v) = f v 

   /// if input is Changed and f returns a Unchanged, 
   /// the whole expression is Changed
   let bindCU (f:'a Unchanger) (Changed v) = 
        let (Unchanged u) = f v 
        Changed u

   /// if input is Changed and f returns a Changed, 
   /// the whole expression is Changed
   let bindCC (f:'a Changer) (Changed v) = f v

下面是一个使用该库的示例：

代码语言：javascript
运行
复制
module Example =       
    open ChangeLib

    let change (o: int[]) =
        o.[0] <- 42
        Changed o

    let copy (o: int[]) =
        let o' = o |> Array.map (fun i -> i + 1)
        Unchanged o'

    let dump (o: int[])=
        printfn "%A" o
        Unchanged o

    // has signature "int[] -> Changed int[]"
    let transmogrifyWithChanges x = 
        x 
        |> change
        |> bindCU dump

    // has signature "int[] -> Unchanged int[]"        
    let transmogrifyWithoutChanges x =
        x
        |> copy
        |> bindUU dump

    // mixing and matching will preserve state
    // so this function returns a Changed
    // and has signature "int[] -> Changed int[]"        
    let transmogrify x =
        x
        |> transmogrifyWithoutChanges
        |> bindUC transmogrifyWithChanges

    // do some tests            
    let a = [| 1;2;3 |]

    let changedA = 
        a |> transmogrifyWithChanges

    let unchangedA = 
        a |> transmogrifyWithoutChanges

    let changedA2 = 
        a |> transmogrify

是的，必须使用不同类型的bind函数是很尴尬的，但是如果您想要编译器错误，这就是您所付出的代价！

使用重载或内联可能有一些技巧，可以让所有绑定函数都具有相同的名称，但就我个人而言，我喜欢让函数名指示类型的明确性。

至于性能，我不认为包装数组会造成很大的损失。

票数 3
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：

https://stackoverflow.com/questions/25688825

复制
相关文章

相似问题

领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档