New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add argmax,argmin equivalents to FSharp.Core #702

Open
dsyme opened this Issue Oct 5, 2018 · 19 comments

Comments

Projects
None yet
6 participants
@dsyme
Collaborator

dsyme commented Oct 5, 2018

NumPy has argmax and argmin to return the index of the maximum and minimum values in a collection.

I propose we add something similar to F#, either with these names of indexOfMax and indexOfMin

The existing way of approaching this problem in F# is a little painful. You have to find the max and then find the specific element with that max.

module List = 
    let indexOfMax xs = 
        let mx = List.max xs
        xs |> List.findIndex (fun v -> v = mx)

Not that bad but seems reasonable to have this in the core library, optimized appropriately and inlined to avoid the generic comparisons.

The functions occurs in basic machine learning samples like https://www.tensorflow.org/tutorials/keras/basic_classification

Pros and Cons

The advantages of making this adjustment to F# are simpler code in some scenarios

The disadvantages of making this adjustment to F# are added functions in FSharp.Core.

Open questions

  • are the names what they need to be? Would maxByIndex by better than indexOfMax? Should it be findIndexOfMax to fit with findIndex. Other suggestions?
  • should there by any similar functions, e.g. indexOfMaxBy seems reasonable.

Extra information

Estimated cost (XS, S, M, L, XL, XXL): S

Affidavit (please submit!)

Please tick this by placing a cross in the box:

  • This is not a question (e.g. like one you might ask on stackoverflow) and I have searched stackoverflow for discussions of this issue
  • I have searched both open and closed suggestions on this site and believe this is not a duplicate
  • This is not something which has obviously "already been decided" in previous versions of F#. If you're questioning a fundamental design decision that has obviously already been taken (e.g. "Make F# untyped") then please don't submit it.

Please tick all that apply:

  • This is not a breaking change to the F# language design
  • I or my company would be willing to help implement and/or test this

@dsyme dsyme changed the title from Add argmax,argmin to FSharp.Core to Add argmax,argmin equivalents to FSharp.Core Oct 5, 2018

@matthewcrews

This comment has been minimized.

Show comment
Hide comment
@matthewcrews

matthewcrews Oct 5, 2018

If I could give this a hundred upvotes I would. So many of the optimization papers I read have this as a fundamental concept.

I would love to have both indexOfMax/indexOfMin and indexOfMaxBy/indexOfMinBy. In Optimization and Data Analysis the need for these types of functions comes up frequently.

I would love to work with someone on implementing this. Since I have not contributed to the F# language in the past I would need some help and guidance.

matthewcrews commented Oct 5, 2018

If I could give this a hundred upvotes I would. So many of the optimization papers I read have this as a fundamental concept.

I would love to have both indexOfMax/indexOfMin and indexOfMaxBy/indexOfMinBy. In Optimization and Data Analysis the need for these types of functions comes up frequently.

I would love to work with someone on implementing this. Since I have not contributed to the F# language in the past I would need some help and guidance.

@cartermp

This comment has been minimized.

Show comment
Hide comment
@cartermp

cartermp Oct 5, 2018

Member

@matthewcrews since @dsyme created the issue I believe he intends on implementing the functions, but I think it would be illustrative to give some examples of how you'd use these functions in the context of your work.

It would also be helpful if there are other things you find missing from F#, or at least feel like something that ought to be a part of FSharp.Core list/array/seq combinators when working in optimization and data analysis. Separate suggestions can be created for things that make sense. From there, RFCs and/or trial implementations could advance if approved.

Member

cartermp commented Oct 5, 2018

@matthewcrews since @dsyme created the issue I believe he intends on implementing the functions, but I think it would be illustrative to give some examples of how you'd use these functions in the context of your work.

It would also be helpful if there are other things you find missing from F#, or at least feel like something that ought to be a part of FSharp.Core list/array/seq combinators when working in optimization and data analysis. Separate suggestions can be created for things that make sense. From there, RFCs and/or trial implementations could advance if approved.

@matthewcrews

This comment has been minimized.

Show comment
Hide comment
@matthewcrews

matthewcrews Oct 5, 2018

@cartermp Will do. Here are some common use cases for what I have to do. This is focused on working with numbers so I'm not taking being able to operate on the generic case. I'll leave that to the professionals :)

These all come from me starting to work on a Linear Programming solver. There are actually four different variations on this concept which come up often. Below I show the different cases and what my initial thoughts are on what it would be like to work with them.

let vector = [|1..10|]

// Case 1: I need the index of the Max or Min value

// a should be 0
let a = Array.indexOfMin vector

// b should be 9
let b = Array.indexOfMax vector

// Case 2: I need to perform a function on the elements and get
// the index where the result is the Max or Min

let analysisFunction x =
    -1.0 * x

// a should be 9
let a = Array.indexOfMinBy analysisFunction vector

// b should be 0
let b = Array.indexOfMaxBy analysisFunction vector

// Case 3: I need to only consider a subset of the elements
// and return the Min or Max index where the condition holds

let filterFunction x =
    x >= 5.0 && x <= 6.0

// a should be 4
let a = Array.indexOfMinWhere filterFunction vector

// b should be 5
let b = Array.indexOfMaxWhere filterFunction vector


// Case 4: I need to consider only a subset of the elements
// and then compute a value for each element which passes
// the condition. Of those, I want the index of the element
// which gave the Min or Max value for the given function.

let analysisFunction x =
    -1.0 * x

let filterFunction x =
    x >= 5.0 && x <= 6.0

// a should be 5
let a = Array.indexOfMinByWhere filterFunction analysisFunction vector

// b should be 4
let b = Array.indexOfMaxByWhere filterFunction analysisFunction vector

matthewcrews commented Oct 5, 2018

@cartermp Will do. Here are some common use cases for what I have to do. This is focused on working with numbers so I'm not taking being able to operate on the generic case. I'll leave that to the professionals :)

These all come from me starting to work on a Linear Programming solver. There are actually four different variations on this concept which come up often. Below I show the different cases and what my initial thoughts are on what it would be like to work with them.

let vector = [|1..10|]

// Case 1: I need the index of the Max or Min value

// a should be 0
let a = Array.indexOfMin vector

// b should be 9
let b = Array.indexOfMax vector

// Case 2: I need to perform a function on the elements and get
// the index where the result is the Max or Min

let analysisFunction x =
    -1.0 * x

// a should be 9
let a = Array.indexOfMinBy analysisFunction vector

// b should be 0
let b = Array.indexOfMaxBy analysisFunction vector

// Case 3: I need to only consider a subset of the elements
// and return the Min or Max index where the condition holds

let filterFunction x =
    x >= 5.0 && x <= 6.0

// a should be 4
let a = Array.indexOfMinWhere filterFunction vector

// b should be 5
let b = Array.indexOfMaxWhere filterFunction vector


// Case 4: I need to consider only a subset of the elements
// and then compute a value for each element which passes
// the condition. Of those, I want the index of the element
// which gave the Min or Max value for the given function.

let analysisFunction x =
    -1.0 * x

let filterFunction x =
    x >= 5.0 && x <= 6.0

// a should be 5
let a = Array.indexOfMinByWhere filterFunction analysisFunction vector

// b should be 4
let b = Array.indexOfMaxByWhere filterFunction analysisFunction vector
@matthewcrews

This comment has been minimized.

Show comment
Hide comment
@matthewcrews

matthewcrews Oct 5, 2018

I could also make the case that an i version of these functions would be helpful. These would be akin to the Array.mapi or Array.iteri functions. I completely understand if the sentiment is that it would crowd the module but I do have use cases where I need to know the index that I am currently iterating on.

When formulating problems or performing analysis over arrays I often have to index into another array. These are all things I'm going to have to write for myself if they are not in FSharp.Core. The examples here are silly but they show some of my common usage patterns.

// The i version of the Max and Min functions
let vector = [1..10]
let otherVector = [11..20]
let analysisFunction (index:int) x ->
    otherVector.[index] + x

// Min and Max Byi functions
let a = indexOfMinByi analysisFunction vector

let b = indexOfMaxByi analysisFunction vector


// Min and Max By i Where functions
let a = indexOfMinByiWhere filterFunction analysisFunction vector

let b = indexOfMaxByiWhere filterFunction analysisFunction vector

matthewcrews commented Oct 5, 2018

I could also make the case that an i version of these functions would be helpful. These would be akin to the Array.mapi or Array.iteri functions. I completely understand if the sentiment is that it would crowd the module but I do have use cases where I need to know the index that I am currently iterating on.

When formulating problems or performing analysis over arrays I often have to index into another array. These are all things I'm going to have to write for myself if they are not in FSharp.Core. The examples here are silly but they show some of my common usage patterns.

// The i version of the Max and Min functions
let vector = [1..10]
let otherVector = [11..20]
let analysisFunction (index:int) x ->
    otherVector.[index] + x

// Min and Max Byi functions
let a = indexOfMinByi analysisFunction vector

let b = indexOfMaxByi analysisFunction vector


// Min and Max By i Where functions
let a = indexOfMinByiWhere filterFunction analysisFunction vector

let b = indexOfMaxByiWhere filterFunction analysisFunction vector
@matthewcrews

This comment has been minimized.

Show comment
Hide comment
@matthewcrews

matthewcrews Oct 5, 2018

I took a couple of minutes to write up what I think I would expect from the type signatures:

// Function signatures

// 'T [] -> int
Array.indexOfMin

// 'T [] -> int
Array.indexOfMax

// ('T1 -> 'T2) -> 'T1 [] -> int
Array.indexOfMinBy

// ('T1 -> 'T2) -> 'T1 [] -> int
Array.indexOfMaxBy

// ('T -> bool) -> 'T [] -> int
Array.indexOfMinWhere

// ('T -> bool) -> 'T [] -> int
Array.indexOfMaxWhere

// ('T1 -> 'T2) -> ('T1 -> bool) -> 'T1 [] -> int
Array.indexOfMinByWhere

// ('T1 -> 'T2) -> ('T1 -> bool) -> 'T1 [] -> int
Array.indexOfMaxByWhere

// The i version of the functions. Same as the ones above except the index 
// of the current element is passed to the function as the first argument to the input functions

// (int -> 'T1 -> 'T2) -> 'T1 [] -> int
Array.indexOfMinByi

// (int -> 'T1 -> 'T2) -> 'T1 [] -> int
Array.indexOfMaxByi

// (int -> 'T -> bool) -> 'T [] -> int
Array.indexOfMinWherei

// (int -> 'T -> bool) -> 'T [] -> int
Array.indexOfMaxWherei

// (int -> 'T1 -> 'T2) -> (int -> 'T1 -> bool) -> 'T1 [] -> int
Array.indexOfMinByWherei

// (int -> 'T1 -> 'T2) -> (int -> 'T1 -> bool) -> 'T1 [] -> int
Array.indexOfMaxByWherei

matthewcrews commented Oct 5, 2018

I took a couple of minutes to write up what I think I would expect from the type signatures:

// Function signatures

// 'T [] -> int
Array.indexOfMin

// 'T [] -> int
Array.indexOfMax

// ('T1 -> 'T2) -> 'T1 [] -> int
Array.indexOfMinBy

// ('T1 -> 'T2) -> 'T1 [] -> int
Array.indexOfMaxBy

// ('T -> bool) -> 'T [] -> int
Array.indexOfMinWhere

// ('T -> bool) -> 'T [] -> int
Array.indexOfMaxWhere

// ('T1 -> 'T2) -> ('T1 -> bool) -> 'T1 [] -> int
Array.indexOfMinByWhere

// ('T1 -> 'T2) -> ('T1 -> bool) -> 'T1 [] -> int
Array.indexOfMaxByWhere

// The i version of the functions. Same as the ones above except the index 
// of the current element is passed to the function as the first argument to the input functions

// (int -> 'T1 -> 'T2) -> 'T1 [] -> int
Array.indexOfMinByi

// (int -> 'T1 -> 'T2) -> 'T1 [] -> int
Array.indexOfMaxByi

// (int -> 'T -> bool) -> 'T [] -> int
Array.indexOfMinWherei

// (int -> 'T -> bool) -> 'T [] -> int
Array.indexOfMaxWherei

// (int -> 'T1 -> 'T2) -> (int -> 'T1 -> bool) -> 'T1 [] -> int
Array.indexOfMinByWherei

// (int -> 'T1 -> 'T2) -> (int -> 'T1 -> bool) -> 'T1 [] -> int
Array.indexOfMaxByWherei
@matthewcrews

This comment has been minimized.

Show comment
Hide comment
@matthewcrews

matthewcrews commented Oct 5, 2018

This is what I ended up doing for working with Arrays:
https://github.com/matthewcrews/Scratchpad/blob/master/ArrayIndexing.fsx

@dsyme

This comment has been minimized.

Show comment
Hide comment
@dsyme

dsyme Oct 5, 2018

Collaborator

Matthew please feel free to make a trial implementation.

However I think we would not include the indexed or indexOf..Where. The former because there are other functions that would get an indexed version before these would, and the latter because it is a design principle of fsharp core not to have filtering variations, eg mapWhere.

Collaborator

dsyme commented Oct 5, 2018

Matthew please feel free to make a trial implementation.

However I think we would not include the indexed or indexOf..Where. The former because there are other functions that would get an indexed version before these would, and the latter because it is a design principle of fsharp core not to have filtering variations, eg mapWhere.

@matthewcrews

This comment has been minimized.

Show comment
Hide comment
@matthewcrews

matthewcrews Oct 5, 2018

Sounds good. The reason for the indexOf..Where functions was to cover cases that the R data.table library provides for that I have found useful in the past. They are advanced use cases but they have come up. I can just offer them in a separate library on Nuget.

matthewcrews commented Oct 5, 2018

Sounds good. The reason for the indexOf..Where functions was to cover cases that the R data.table library provides for that I have found useful in the past. They are advanced use cases but they have come up. I can just offer them in a separate library on Nuget.

@matthewcrews

This comment has been minimized.

Show comment
Hide comment
@matthewcrews

matthewcrews Oct 6, 2018

Did we want this for anything besides Array and List? I could see having this for Map as well since it is a data structure with index lookup.

matthewcrews commented Oct 6, 2018

Did we want this for anything besides Array and List? I could see having this for Map as well since it is a data structure with index lookup.

@dsyme

This comment has been minimized.

Show comment
Hide comment
@dsyme

dsyme Oct 9, 2018

Collaborator

@matthewcrews Yes, that makes sense.

Collaborator

dsyme commented Oct 9, 2018

@matthewcrews Yes, that makes sense.

@PatrickMcDonald

This comment has been minimized.

Show comment
Hide comment
@PatrickMcDonald

PatrickMcDonald Oct 9, 2018

We should do Seq also for consistency.

Although longer, findIndexOfMax[By] seems a better fit given we already have other findIndex methods (findIndex and findIndexBack)

PatrickMcDonald commented Oct 9, 2018

We should do Seq also for consistency.

Although longer, findIndexOfMax[By] seems a better fit given we already have other findIndex methods (findIndex and findIndexBack)

@matthewcrews

This comment has been minimized.

Show comment
Hide comment
@matthewcrews

matthewcrews Oct 10, 2018

I don't know if that would be a good idea. A Seq could be potentially infinite in length and therefore these functions may never return. That was why I was not planning on implementing them.

matthewcrews commented Oct 10, 2018

I don't know if that would be a good idea. A Seq could be potentially infinite in length and therefore these functions may never return. That was why I was not planning on implementing them.

@dsyme

This comment has been minimized.

Show comment
Hide comment
@dsyme

dsyme Oct 10, 2018

Collaborator

There are many Seq functions like that, including Seq.exists for example. So we should include Seq

Collaborator

dsyme commented Oct 10, 2018

There are many Seq functions like that, including Seq.exists for example. So we should include Seq

@matthewcrews

This comment has been minimized.

Show comment
Hide comment
@matthewcrews

matthewcrews Oct 11, 2018

I'm happy to add it for Seq as well. Right now my problem is that I can't find any guidance on getting testing setup and running for solution. I added functions for List and Array and unit tests for them but it says it fails because they aren't registered anywhere. Is there any documentation about how to properly add and run tests for this solution? I'd love to help by adding these functions but there's not a lot of guidance that I can find.

matthewcrews commented Oct 11, 2018

I'm happy to add it for Seq as well. Right now my problem is that I can't find any guidance on getting testing setup and running for solution. I added functions for List and Array and unit tests for them but it says it fails because they aren't registered anywhere. Is there any documentation about how to properly add and run tests for this solution? I'd love to help by adding these functions but there's not a lot of guidance that I can find.

@Richiban

This comment has been minimized.

Show comment
Hide comment
@Richiban

Richiban Oct 11, 2018

@dsyme

it is a design principle of fsharp core not to have filtering variations, eg mapWhere.

Isn't that Choose?

Richiban commented Oct 11, 2018

@dsyme

it is a design principle of fsharp core not to have filtering variations, eg mapWhere.

Isn't that Choose?

@gusty

This comment has been minimized.

Show comment
Hide comment
@gusty

gusty Oct 11, 2018

I think choose is not exactly a filter or a Where. It's a kind of flatten for a Collection of options (or something that maps to option).

Having said that, I think the name should have been chooseBy for consistency.

gusty commented Oct 11, 2018

I think choose is not exactly a filter or a Where. It's a kind of flatten for a Collection of options (or something that maps to option).

Having said that, I think the name should have been chooseBy for consistency.

@Richiban

This comment has been minimized.

Show comment
Hide comment
@Richiban

Richiban Oct 11, 2018

Perhaps there are different interpretations, but the way I read it is that it performs a map on a sequence to some sequence of options, filtering out the Nones and lifting the Somes. It's a map and a filter at the same time.

It's incredibly useful and one of my favourite Seq / List / Array functions, but I did always wonder why it wasn't just called filterMap or something similar.

Richiban commented Oct 11, 2018

Perhaps there are different interpretations, but the way I read it is that it performs a map on a sequence to some sequence of options, filtering out the Nones and lifting the Somes. It's a map and a filter at the same time.

It's incredibly useful and one of my favourite Seq / List / Array functions, but I did always wonder why it wasn't just called filterMap or something similar.

@matthewcrews

This comment has been minimized.

Show comment
Hide comment
@matthewcrews

matthewcrews Oct 11, 2018

Per Don Syme, I will not be including the indexOf...Where functions. I will be adding them for myself and hope to publish it as a separate Nuget library.

Conceptually you can think of the indexOf...Where functions as a map then choose but that implementation would be terribly inefficient. My understanding was that we wanted a fast implementation of these functions which is why I use mutable variables to track the Min/Max as I iterate through the collections.

I need the indexOf...Where functions for implementing an LP Solver which does a lot of index searching over arrays.

matthewcrews commented Oct 11, 2018

Per Don Syme, I will not be including the indexOf...Where functions. I will be adding them for myself and hope to publish it as a separate Nuget library.

Conceptually you can think of the indexOf...Where functions as a map then choose but that implementation would be terribly inefficient. My understanding was that we wanted a fast implementation of these functions which is why I use mutable variables to track the Min/Max as I iterate through the collections.

I need the indexOf...Where functions for implementing an LP Solver which does a lot of index searching over arrays.

@dsyme

This comment has been minimized.

Show comment
Hide comment
@dsyme

dsyme Oct 12, 2018

Collaborator

I think choose is not exactly a filter or a Where. It's a kind of flatten for a Collection of options (or something that maps to option).

The specific design decision I was referring to was not to have extra "where" versions that take a boolean-valued predicate. It's true that choose sneaks past this by providing an option-valued projection. So you could imagine a

findIndexOfMaxBy : ('T -> 'U option) -> int

However that would still result in quite a proliferation of functions.

So choose and pick are basically the only places we do this.

Collaborator

dsyme commented Oct 12, 2018

I think choose is not exactly a filter or a Where. It's a kind of flatten for a Collection of options (or something that maps to option).

The specific design decision I was referring to was not to have extra "where" versions that take a boolean-valued predicate. It's true that choose sneaks past this by providing an option-valued projection. So you could imagine a

findIndexOfMaxBy : ('T -> 'U option) -> int

However that would still result in quite a proliferation of functions.

So choose and pick are basically the only places we do this.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment