7 people like it.

Using units of measure for safe array access

A typical problem when working with arrays and indices is that it's easy to access an array with the wrong index. Units of measure in F# can be applied to integers, which makes it possible to abuse them to prevent this kind of error.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
/// An array whose index has a unit of measure
type MarkedArray<[<Measure>] 'K, 'T> = MarkedArray of 'T[]
with
    member this.Content =
        let (MarkedArray arr) = this
        arr

    member this.First : int<'K> =
        LanguagePrimitives.Int32WithMeasure 0

    member this.Last : int<'K> =
        let (MarkedArray arr) = this
        LanguagePrimitives.Int32WithMeasure (arr.Length - 1)

    member this.Item
        with get (i : int<'K>) =
            let (MarkedArray arr) = this
            arr.[int i]
        and set (i : int<'K>) (v : 'T) =
            let (MarkedArray arr) = this
            arr.[int i] <- v

[<RequireQualifiedAccess>]
module MarkedArray =
    let inline set (arr : MarkedArray<'K, 'T>) idx v =
        arr.[idx] <- v

    let inline get (arr : MarkedArray<'K, 'T>) idx =
        arr.[idx]

    /// arr.[idx] <- f (arr.[idx])
    let inline mutate f (arr, idx) =
        let v = get arr idx
        set arr idx (f v)

module Example =
    type Ship = Ship
    type Missile = Missile
    
    [<Measure>] type MissileIndex
    [<Measure>] type ShipIndex

    let missiles : MarkedArray<MissileIndex, _> = Array.create 42 (Some Missile) |> MarkedArray
    let ships : MarkedArray<ShipIndex, _> = Array.create 4 (Some Ship) |> MarkedArray

    // A missile hit the ship, destroy both
    let applyHit shipIdx missileIdx =
        missiles.[missileIdx] <- None
        ships.[shipIdx] <- None
    
Multiple items
type MeasureAttribute =
  inherit Attribute
  new : unit -> MeasureAttribute

Full name: Microsoft.FSharp.Core.MeasureAttribute

--------------------
new : unit -> MeasureAttribute
Multiple items
union case MarkedArray.MarkedArray: 'T [] -> MarkedArray<'K,'T>

--------------------
type MarkedArray<'K,'T> =
  | MarkedArray of 'T []
  member Content : 'T []
  member First : int<'K>
  member Item : i:int<'K> -> 'T with get
  member Last : int<'K>
  member Item : i:int<'K> -> 'T with set

Full name: Script.MarkedArray<_,_>


 An array whose index has a unit of measure
val this : MarkedArray<'K,'T>
member MarkedArray.Content : 'T []

Full name: Script.MarkedArray`1.Content
val arr : 'T []
member MarkedArray.First : int<'K>

Full name: Script.MarkedArray`1.First
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
module LanguagePrimitives

from Microsoft.FSharp.Core
val Int32WithMeasure : int -> int<'Measure>

Full name: Microsoft.FSharp.Core.LanguagePrimitives.Int32WithMeasure
member MarkedArray.Last : int<'K>

Full name: Script.MarkedArray`1.Last
property System.Array.Length: int
member MarkedArray.Item : i:int<'K> -> 'T with set

Full name: Script.MarkedArray`1.Item
val i : int<'K>
val set : elements:seq<'T> -> Set<'T> (requires comparison)

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.set
val v : 'T
Multiple items
type RequireQualifiedAccessAttribute =
  inherit Attribute
  new : unit -> RequireQualifiedAccessAttribute

Full name: Microsoft.FSharp.Core.RequireQualifiedAccessAttribute

--------------------
new : unit -> RequireQualifiedAccessAttribute
val set : arr:MarkedArray<'K,'T> -> idx:int<'K> -> v:'T -> unit

Full name: Script.MarkedArray.set
val arr : MarkedArray<'K,'T>
val idx : int<'K>
val get : arr:MarkedArray<'K,'T> -> idx:int<'K> -> 'T

Full name: Script.MarkedArray.get
val mutate : f:('a -> 'a) -> arr:MarkedArray<'u,'a> * idx:int<'u> -> unit

Full name: Script.MarkedArray.mutate


 arr.[idx] <- f (arr.[idx])
val f : ('a -> 'a)
val arr : MarkedArray<'u,'a>
val idx : int<'u>
val v : 'a
module Example

from Script
Multiple items
union case Ship.Ship: Ship

--------------------
type Ship = | Ship

Full name: Script.Example.Ship
Multiple items
union case Missile.Missile: Missile

--------------------
type Missile = | Missile

Full name: Script.Example.Missile
[<Measure>]
type MissileIndex

Full name: Script.Example.MissileIndex
[<Measure>]
type ShipIndex

Full name: Script.Example.ShipIndex
val missiles : MarkedArray<MissileIndex,Missile option>

Full name: Script.Example.missiles
Multiple items
union case MarkedArray.MarkedArray: 'T [] -> MarkedArray<'K,'T>

--------------------
module MarkedArray

from Script

--------------------
type MarkedArray<'K,'T> =
  | MarkedArray of 'T []
  member Content : 'T []
  member First : int<'K>
  member Item : i:int<'K> -> 'T with get
  member Last : int<'K>
  member Item : i:int<'K> -> 'T with set

Full name: Script.MarkedArray<_,_>


 An array whose index has a unit of measure
module Array

from Microsoft.FSharp.Collections
val create : count:int -> value:'T -> 'T []

Full name: Microsoft.FSharp.Collections.Array.create
union case Option.Some: Value: 'T -> Option<'T>
val ships : MarkedArray<ShipIndex,Ship option>

Full name: Script.Example.ships
val applyHit : shipIdx:int<ShipIndex> -> missileIdx:int<MissileIndex> -> unit

Full name: Script.Example.applyHit
val shipIdx : int<ShipIndex>
val missileIdx : int<MissileIndex>
union case Option.None: Option<'T>

More information

Link:http://fssnip.net/9I
Posted:12 years ago
Author:Johann Deneux
Tags: array , units of measure