F# - Treating a function like a map

Question

Long story short, I came up with this funny function set, that takes a function, f : 'k -> 'v, a chosen value, k : 'k, a chosen result, v : 'v, uses f as the basis for a new function g : 'k -> 'v that is the exact same as f, except for that it now holds that, g k = v.

Here is the (pretty simple) F# code I wrote in order to make it:

let set : ('k -> 'v) -> 'k -> 'v -> 'k -> 'v = 
    fun f k v x ->
        if x = k then v else f x

My questions are:

Does this function pose any problems?

I could imagine repeat use of the function, like this

let kvs : (int * int) List = ... // A very long list of random int pairs.
List.fold (fun f (k,v) -> set f k v) id kvs

would start building up a long list of functions on the heap. Is this something to be concerned about?

Is there a better way to do this, while still keeping the type?

I mean, I could do stuff like construct a type for holding the original function, f, a Map, setting key-value pairs to the map, and checking the map first, the function second, when using keys to get values, but that's not what interests me here - what interest me is having a function for "modifying" a single result for a given value, for a given function.

Answer 1

Potential problems:

1. The set-modified function leaks space if you override the same value twice:

   let huge_object = ...
   let small_object = ...
   
   let f0 = set f 0 huge_object
   let f1 = set f0 0 small_object
   

   Even though it can never be the output of f1, huge_object cannot be garbage-collected until f1 can: huge_object is referenced by f0, which is in turn referenced by the f1.

2. The set-modified function has overhead linear in the number of set operations applied to it.

I don't know if these are actual problems for your intended application.

If you wish set to have exactly the type ('k -> 'v) -> 'k -> 'v -> 'k -> 'v then I don't see a better way(*). The obvious idea would be to have a "modification table" of functions you've already modified, then let set look up a given f in this table. But function types do not admit equality checking, so you cannot compare f to the set of functions known to your modification table.

(*) Reflection not withstanding.