"Subsetting" a dictionary in F#

Question

I'm a beginner in F# and I'm trying to write a function to subset a dictionary given list, and return the result.

I tried this, but it doesn't work.

let Subset (dict:Dictionary<'T,'U>) (sub_list:list<'T>) =
    let z = dict.Clear
    sub_list |> List.filter (fun k -> dict.ContainsKey k)
             |> List.map (fun k -> (k, dict.TryGetValue k) )
             |> List.iter (fun s -> z.Add s)

|> List.iter (fun s -> z.Add s);;
  --------------------------------------^^^

stdin(597,39): error FS0039: The field, constructor or member 'Add' is not defined

Perhaps there is a native function in F# to do that ?

thanks

EDIT thanks to @TheInnerLight for his answer below can you just educate me a bit more, and tell me how i should adapt that function if i want to return the original variable being modified ? (of course it would be possible to go from where we call that function, call it with a temp variable, and reassign)

TheInnerLight · Accepted Answer · 2016-01-08T01:54:50.307

You have written:

let z = dict.Clear

z is of type unit->unit yet you are calling z.Add.

I suspect you want to write

let subset (dict:Dictionary<'T,'U>) (sub_list:list<'T>) =
    let z = Dictionary<'T,'U>() // create new empty dictionary
    sub_list |> List.filter (fun k -> dict.ContainsKey k)
             |> List.map (fun k -> (k, dict.[k]) )
             |> List.iter (fun s -> z.Add s)
    z

TryGetValue is going to return something of type bool*'U in F#, which I suspect you don't want if already filtering by ContainsKey so you probably want to look up directly with dict.[k].

Note that Dictionary is a mutable collection so if you were to actually call dict.Clear(), it wouldn't return a new empty dictionary, it would mutate the existing one by clearing all elements. The immutable F# data structure usually used for key-value relationships is Map, see https://msdn.microsoft.com/en-us/library/ee353880.aspx for things you can do with Map.

Here is a map version (this is the solution I recommend):

let subset map subList =
    subList 
    |> List.choose (fun k -> Option.map (fun v -> k,v) (Map.tryFind k map))
    |> Map.ofList

Edit (in response to the question edit about modifying the input variable):

It's possible to update an existing dictionary using the destructive update operator <- on a mutable variable.

Option 1:

let mutable dict = Dictionary<Key,Value>() // replace this with initial dictionary
let lst = [] // list to check against
dict <- sublist dict lst

Likewise, my first function could be changed to perform only a side effect (removing unwanted elements).

Option 2:

let subset (d : System.Collections.Generic.Dictionary<'T,'U>) (sub_list : list<'T>) =
    sub_list 
    |> List.filter (d.ContainsKey >> not)
    |> List.iter (d.Remove >> ignore)

For an F# beginner I don't really recommend Option 1 and I really don't recommend Option 2.

The functional approach is to favour immutable values, pure functions, etc. This means you will be better off thinking of your functions as defining data transformations rather than as defining a list of instructions to be performed.

Because F# is a multi-paradigm language, it's easy to fall back on the imperative in the early stages but you will probably gain the most from learning your new language if you force yourself to adopt the standard paradigm and idioms of that language even if those idioms feel strange and uncomfortable to begin with.

The immutable data structures like Map and list are pretty efficient at sharing data as well as providing good time complexity so these are really the go-to collections when working in F#.

@FaguiCurtain No problem. Have, updated my answer in response to your second question. — TheInnerLight, Jan 08 '16 at 02:01
but if i need mutable values, i should use dictionary instead of map right ? would your function in your proposed solution with map take a dictionary as an argument ? — Fagui Curtain, Jan 08 '16 at 05:30
@FaguiCurtain The main use for `Dictionary` in F# would probably be for use with classes, epecially if you're working in a mix of C#/F#. `Map` has a `comparison` requirement which most types used in F# will give you automatically but classes will not. There is always a way to express your program logic without using mutable state. Once you've mastered that, you should have a better idea of when it's favourable to apply a little mutability. You can read more about `Map`s (and `Set`s) here: https://en.wikibooks.org/wiki/F_Sharp_Programming/Sets_and_Maps — TheInnerLight, Jan 08 '16 at 12:12
could you give one or a few examples (or link to) such logic. how to avoid using mutable state... — Fagui Curtain, Jan 08 '16 at 12:24
@FaguiCurtain This answer can give you an overview: http://stackoverflow.com/a/1020862/5438433 Here is a more in depth tutorial: http://fsharpforfunandprofit.com/posts/thinking-functionally-intro/ If you prefer a book to read, you might want to take a look at "Real World Functional Programming" — TheInnerLight, Jan 08 '16 at 13:28

"Subsetting" a dictionary in F#

1 Answers1