Storing multidimensional points in F#

Question

I am currently porting some code from Java to F# that deals with multidimensional functions. It supports variable dimension, so in the original implementation each point is represented as an array of doubles. The critical function of the code is an optimisation routine, that basically generates a sequence of points based on some criteria, evaluates a given function at these points and looks for a maximum. This works for any dimension. The operations I need are:

check the dimension of a point
create a new point with the same dimension of a given point
set (in procedural or functional sense) a given coordinate of a point

In F# I could obviously also use arrays in the same way. I was wandering though if there is a better way. If the dimension was fixed in advance, the obvious choice would be to use tuples. Is it possible to use tuples in this dynamic setting though?

t0yv0 · Answer 1 · 2012-06-07T23:46:49.023

No, tuples will be fixed by dimension. Also note that .NET tuples are boxed. If you are operating on large collections of points with small dimension (such as arrays of 2d points), using structs may help.

If you really want to push the F#/.NET advantage over Java, have a look at generics. Writing code with generics allows to write code that works for any dimension, and use different representations for different dimensions (say structs for 1-3 dimensions, and vectors for larger dimensions):

let op<'T where 'T :> IVector> (x: 'T) =
    ...

This is only relevant though if you are willing to go a long way to get the absolutely best performance and generality. Most projects do not need that, stick with the simplest thing that works.

For the fun of it, here is an extended example of how to utilize generics and F# inlining:

open System.Numerics

type IVector<'T,'V> =
    abstract member Item : int -> 'T with get
    abstract member Length : int
    abstract member Update : int * 'T -> 'V

let lift<'T,'V when 'V :> IVector<'T,'V>> f (v: 'V) : 'V =
    if v.Length = 0 then v else
        let mutable r = v.Update(0, f v.[0])
        for i in 1 .. v.Length - 1 do
            r <- r.Update(i, f v.[i])
        r

let inline norm (v: IVector<_,_>) =
    let sq i =
        let x = v.[i]
        x * x
    Seq.sum (Seq.init v.Length sq)

let inline normalize (v: 'V) : 'V =
    let n = norm v
    lift (fun x -> x / n) v

[<Struct>]
type Vector2D<'T>(x: 'T, y: 'T) =
    member this.X = x
    member this.Y = y

    interface IVector<'T,Vector2D<'T>> with
        member this.Item
            with get (i: int) =
                match i with
                | 0 -> x
                | _ -> y
        member this.Length = 2
        member this.Update(i: int, v: 'T) =
            match i with
            | 0 -> Vector2D(v, y)
            | _ -> Vector2D(x, v)

    override this.ToString() =
        System.String.Format("{0}, {1}", x, y)

[<Sealed>]
type Vector<'T>(x: 'T []) =

    interface IVector<'T,Vector<'T>> with
        member this.Item with get (i: int) = x.[i]
        member this.Length = x.Length
        member this.Update(i: int, v: 'T) =
            let a = Array.copy x
            a.[i] <- v
            Vector(a)

    override this.ToString() =
        x
        |> Seq.map (fun e -> e.ToString())
        |> String.concat ", "

[<Struct>]
type C(c: Complex) =
    member this.Complex = c
    static member Zero = C(Complex(0., 0.))
    static member ( + ) (a: C, b: C) = C(a.Complex + b.Complex)
    static member ( * ) (a: C, b: C) = C(a.Complex * b.Complex)
    static member ( / ) (a: C, b: C) = C(a.Complex / b.Complex)
    override this.ToString() = string c

let v1 = Vector2D(10., 30.)
normalize v1
|> printfn "%O"

let v2 = Vector2D(C(Complex(1.25, 0.8)), C(Complex(0.5, -1.)))
normalize v2
|> printfn "%O"

let v3 = Vector([| 10.; 30.; 50.|])
normalize v3
|> printfn "%O"

Note that norm and normalize are fairly general, they cope with specialized 2D vectors and generalized N-dimensional vectors, and with different component types such as complex numbers (you can define your own). The use of generics and F# inlining ensure that while general, these algorithms perform well for the special cases, using compact representations. This is where F# and .NET generics shine compared to Java, where you are obliged to create specialized copies of your code to get decent performance.

I think it's worth putting more emphasis on the fact that the only reason instances of `Vector2D<>` aren't boxed when calling `norm` and `normalize` is because they're marked `inline`; if `inline` were absent, boxing would occur because interfaces have reference semantics. — ildjarn, Jun 07 '12 at 19:10
Are you sure it would? If these functions were not inline, then what you lose is F# compile-time arithmetic op overloading. But suppose, for simplicity, we drop `'T` and work with `double`. Then `norm` will not box the `Vector2D` struct if it is written as `norm<'T when 'T : IVector..>` (method generic with constraint). More difficult with `normalize`, it is harder to do func updates in this style. — t0yv0, Jun 07 '12 at 19:24
With `inline`, restricting the argument to be an `IVector<>` acts as a compile-time constraint, and the argument type is `Vector2D<>` (no boxing); _without_ `inline`, restricting the argument to be an `IVector<>` acts as a runtime constraint, and the argument type remains `IVector<>`, which has reference semantics (read: boxing) even though the underlying type is a value type. — ildjarn, Jun 07 '12 at 19:26
Related discussion: http://stackoverflow.com/questions/3032750/structs-interfaces-and-boxing — Daniel, Jun 07 '12 at 21:59
@ildjarn, I completely agree, except if your code does not restrict the argument to `IVector`, and make it generic instead, then it is resolved statically - no boxing. Simplest example: https://gist.github.com/ddb32c73cf9c6d8af575 — t0yv0, Jun 07 '12 at 23:31
@toyvo : You have no value types in that example, so I'm not sure how it pertains. :-] — ildjarn, Jun 07 '12 at 23:34
Just forgot `[]`, here you go, updated: https://gist.github.com/ddb32c73cf9c6d8af575 — t0yv0, Jun 07 '12 at 23:35
AFAIK methods get specialized by JIT for every value type instantiation of the generics, eliminating boxing - since memory layout is now known statically. — t0yv0, Jun 07 '12 at 23:38

Storing multidimensional points in F#

1 Answers1