CODEWITHSUNDEEP
f#
Hayden
Hayden

Reputation: 2988

Add elements to nested Map efficiently

I have a nested Map like so:

Map<int, Map<int, int>>

And I want to be able to add an element to the nested Map as efficiently and neatly as possible.

My current solution is something like this:

let AddStuff (collection:Map<int, Map<int, int>>) firstID secondID value = 
    let newValue = collection.[firstID].Add(secondID, value)
    let newCollection = collection.Add(firstID, newValue)
    newCollection

This to me doesn't seem to be the F# way of doing things so was wondering on what is the best way to add to a nested Map?

Edit Some expected input/output:

let aMap = map[(1, map[(1, 1)])]
let firstID = 1
let secondID = 2
let value = 2

let newMap = aMap firstID secondID value

// newMap = map[(1, map[(1, 1); (2, 2)])]

Edit 2

It seems that partialCollection had no effect on the output, so I've removed it from the function.

Upvotes: 1

Views: 477

Answers (4)

Just another metaprogrammer
Just another metaprogrammer

Reputation: 11577

You asked for efficiency and neatness. A rather neat approach is to use Lenses to update properties of an immutable type. 

module Lenses =
  // A Lens is a type that allows "focusing" on a property of a type
  //  A Lens consists of a get and set function

  // Inspired by: http://www.haskellforall.com/2012/01/haskell-for-mainstream-programmers_28.html

  //                          getter     setter
  type Lens<'T, 'V> = Lens of ('T -> 'V)*('V -> 'T -> 'T)

  let inline get  (Lens (g, _)) v     = g v
  let inline set  (Lens (_, s)) n v   = s n v

  // >-> chains two Lenses, allows focusing on property of a property of a type
  let ( >-> ) (f : Lens<'T, 'V>) (s : Lens<'V, 'U>) : Lens<'T, 'U> =
    Lens (get f >> get s, fun n v -> set f (set s n (get f v)) v)

  // fstL is a Lens that focuses on the first element in a pair
  let fstL<'T, 'U>  : Lens<'T*'U, 'T> = 
    Lens (fst, fun n v -> (n, snd v))
  // sndL is a Lens that focuses on the second element in a pair
  let sndL<'T, 'U>  : Lens<'T*'U, 'U> = 
    Lens (snd, fun n v -> (fst v, n))
  // mapzL is a Lens that focuses on an element in a map, z is the zero value if not present
  let mapzL k z     : Lens<Map<'K, 'V>, 'V> = 
    let get v = 
      match Map.tryFind k v with
      | Some e -> e
      | _ -> z
    let set = Map.add k
    Lens (get, set)
  // mapzL is a Lens that focuses on an element in a map
  let inline mapL k = mapzL k LanguagePrimitives.GenericZero

open Lenses

[<EntryPoint>]
let main argv =
  // Creates an empty map of a map
  let empty     : Map<string, Map<int, float>> = Map.empty

  // Uses Lenses to update the map
  //  Has to pass Map.empty to mapzL as Map doesn't have a Zero member
  let modified1 = empty     |> set (mapzL "A" Map.empty >-> mapL 2) 3.
  let modified2 = modified1 |> set (mapzL "B" Map.empty >-> mapL 3) 4.
  let modified3 = modified2 |> set (mapzL "B" Map.empty >-> mapL 4) 5.

  printfn "%A" empty
  printfn "%A" modified1
  printfn "%A" modified2
  printfn "%A" modified3

  0

Upvotes: 0

scrwtp
scrwtp

Reputation: 13577

There's one problem with the solutions you have so far. Asking for a key that's not in the map using the indexer throws - you can't add something that's not already in the top-level map that way. So a call like AddStuff aNewMap 7 11 3 will break.

Here's a neat way of doing it - first define a generic update function:

/// Update a value for key if it exists,
/// otherwise return a new map with that value  
let update key f maybeColl = 
    match maybeColl with
    | Some coll ->
        let maybeElem = Map.tryFind key coll
        Map.add key (f maybeElem) coll
    | None ->
        Map.ofList [key, f None]

Then compose your function from updates:

/// Given a two-level map, adds a value to the nested map.
let add2 firstKey secondKey value coll =
    (Some coll)
    |> update firstKey (
        update secondKey (fun _ -> value))

Making update easily composable means that you can easily write an add3 or a function that would map over a value in the nested map for for instance.

Upvotes: 1

rmunn
rmunn

Reputation: 36688

To be slightly more functional in style, you could replace those .Add method calls with calls to the Map.add function (a function on the Map module, not a method call on the individual Map objects). You might also want to move the collection argument for your AddStuff function to the last argument, so that it can be more easily used with the |> operator. Then it would look like:

let AddStuff firstID secondID value (collection:Map<int, Map<int, int>>) = 
    let newValue = collection.[firstID] |> Map.add secondID value
    collection |> Map.add firstID newValue

And you could use it like:

let newMap = aMap |> AddStuff firstID secondID value

Up to you to decide which style you like better, but I like the |> style better myself, as it lets me think in terms of "this data is getting piped through these operations".

Edit: That function might look a bit nicer with some whitespace:

let AddStuff firstID secondID value (collection:Map<int, Map<int, int>>) = 
    let newValue =
        collection.[firstID]
        |> Map.add secondID value
    collection |> Map.add firstID newValue

Upvotes: 1

Hayden
Hayden

Reputation: 2988

Alright, so as @rmunn said in the comment section, Map.Add is essentially "add or replace"

So my original function, which was:

let AddStuff (collection:Map<int, Map<int, int>>) firstID secondID value = 
    let newValue = collection.[firstID].Add(secondID, value)
    let partialCollection = collection.Remove(firstID)
    let newCollection = partialCollectioncollection.Add(firstID, newValue)
    newCollection

Now becomes:

let AddStuff (collection:Map<int, Map<int, int>>) firstID secondID value = 
    let newCollection = collection.Add(firstID, collection.[firstID].Add(secondID, value))
    newCollection

Upvotes: 0

Related Questions