16

I'm starting down the road of defining my own operators for Cartesian products and matrix multiplication.

With matrices and vectors aliased as lists:

type Matrix = float list list
type Vector = float list

I can write my own initialisation code (and get a Cartesian product into the bargain) by writing

let inline (*) X Y =
    X |> List.collect (fun x -> Y |> List.map (fun y -> (x, y)))

let createVector size f = 
    [0..size - 1] |> List.map (fun i -> f i)

let createMatrix rows columns f =
    [0..rows - 1] * [0..columns - 1] |> List.map (fun i j -> f i j)

So far so good. The problem is that my definition of * wipes out the normal definition, even though my version is only defined for Lists, which don't have their own multiplication operator.

The documentation http://msdn.microsoft.com/en-us/library/vstudio/dd233204.aspx states that "newly defined operators take precedence over the built-in operators". However, I wasn't expecting all of the numerical incarnations to be wiped out -- surely static typing would take care of this?

I know it is possible to define a global operator that respects types, because MathNet Numerics uses * for matrix multiplication. I would also like to go down that road, which would require the typing system to prioritise matrix multiplication over the Cartesian product of Matrix types (which are themselves lists).

Does anyone know how to do this in F#?

Rob Lyndon
  • 12,089
  • 5
  • 49
  • 74

2 Answers2

15

Here is the (non idiomatic) solution:

type Mult = Mult with
    static member inline ($) (Mult, v1: 'a list) = fun (v2: 'b list) -> 
        v1 |> List.collect (fun x -> v2 |> List.map (fun y -> (x, y))) : list<'a * 'b>
    static member inline ($) (Mult, v1:'a      ) = fun (v2:'a) -> v1 * v2 :'a

let inline (*) v1 v2 = (Mult $ v1) v2
Gus
  • 25,839
  • 2
  • 51
  • 76
  • Dude, that is super-cool. I ran it in F# interactive, and then did `let prod = [1..3] * ["Hello"; "World"]` and `let x = 2 * 5`. The results were `[(1, "Hello"); (1, "World"); (2, "Hello"); (2, "World"); (3, "Hello"); (3, "World")]` and 10 respectively. – Rob Lyndon Oct 30 '13 at 15:51
  • 3
    Yes, if you want to know more about this, I did a project which use a refinement of this technique https://github.com/gmpl/FsControl – Gus Oct 30 '13 at 15:58
  • 1
    Looks very interesting. As I said to Tomas, I think you might have to pay for this with a pattern-matching operation every time you perform a redefined `*` operation, but even if that is the case, I'm sure the cost is tiny. I wonder if this can be made to work inside the CUDA monad... – Rob Lyndon Oct 30 '13 at 16:05
  • You pay the cost at compile-time rather than run-time. Which CUDA Monad are you using? Indeed I'm using this technique to define generic monadic code. – Gus Oct 30 '13 at 16:14
  • I'm using Alea.cuBase at the moment. I'd be interested to see your work on monadic code. – Rob Lyndon Oct 30 '13 at 17:35
  • In the last few days I ran into references for FsControl a few times so I finally stated looking at it closely and like what I see. If you had only given it a better name I might have been using it for a few years now. Every time I saw FsControl I would think Windows Form controls and say, I don't need this. I give it vote to have a name change. :) – Guy Coder Feb 28 '16 at 16:28
  • @GuyCoder I agree. Control comes from the Haskell libraries that inspired the project but I would be happy to put a better name, I invite you to open an issue suggesting a name change. – Gus Feb 28 '16 at 17:58
12

The idiomatic solution is to define Matrix as a new type and add operators as static members:

type Matrix = 
  | MatrixData of float list list
  static member (*) (MatrixData m1, MatrixData m2) = (...)

Operators defined using let are useful when you know that the definition does not conflict with anything else, or when you're defining the operator locally in a small scope (within a function).

For custom types, it is a good idea to define operators as static members. Another benefit of this approach is that your type will be usable from C# (including the operators).

To do this in your example, I had to change the type definition from type alias (which is not a stand-alone type and so it cannot have its own static members) to a single-case discriminated union, which can have members - but this is probably a good idea anyway.

Tomas Petricek
  • 240,744
  • 19
  • 378
  • 553
  • Thanks Tomas. This gives me a nice way to multiply matrices, as the MathNet Numerics package does. I think I will go down that route, but in the meantime, is there a nice way to redefine the global operator so that it can perform a Cartesian product operation on a `(List<'a>, List<'b>)` pair of arguments? There is an answer using an intermediate `Mult` class in http://stackoverflow.com/questions/14121556/overloading-measure-operator?rq=1, but that seems incomplete because I get a type exception when trying to implement it. – Rob Lyndon Oct 30 '13 at 13:52
  • Gustavo gave a really interesting answer. I've only got one question about it: does his solution mean that the redefined `*` operator performs a pattern match every time it is invoked? Would that have any noticeable effect on large-scale matrix multiplication? – Rob Lyndon Oct 30 '13 at 15:54
  • 1
    @RobLyndon No, it does the overloading resolution at compile time, then inlines the code of the function at the calling site. So you don't loose performance. – Gus Oct 30 '13 at 16:03
  • 5
    Who cares if it is idiomatic - maybe with respect to .NET. I like Gustavo's solution more, it's type safe, it's more elegant, more functional and it afford 'type classes' in F# and that all matter! Maybe F# would deserve better support of this technique in a future version. – tomasK Oct 30 '13 at 22:58
  • 10
    "Who cares if it is idiomatic?" - Well everyone who will have to read, maintain & extend the code... – Tomas Petricek Jul 08 '14 at 20:58