How to use high order functions to filter and matc

Question

So a bit of context is required just to understand my issue. In an RPG, I consider the equipment as a record with optional fields, which means, while they're None that nothing was attributed yet. Equipment is constructed by the game items of the game that represents either weaponry or character protection (helmets and etc) which will be seen in the snippet below. The functionalities are removed and the domain model reduced to make it easier to read.

type ConsummableItem =
    | HealthPotion
    | ManaPotion 

type Weaponry = 
    | Sword 
    | Spear 
    | BattleAxe 

type CharaterProtection = 
    | Helmet 
    | Gloves 
    | Boots 

type GameItem = 
    | Consumable of ConsummableItem * int
    | Weapon of Weaponry * int
    | Protection of CharacterProtection * int

 type Inventory = {
     Bag : GameItem array 
 }
 with // code omitted in the add function
     member x.addSingleItem (item: GameItem) = 
         let oItemIndex = x.Bag |> Array.tryFindIndex(fun x -> x = gi)
         match oItemIndex with
         | Some index ->
             let item = x.Bag.[index]
             let bag =  x.Bag
                    bag.[index] <- item
                    { x with Bag = bag }
         | None ->
             let newBag = x.Bag |> Array.append [|gi|]
             { x with Bag = newBag }

type Equipment = { 
     Helmet : Protection option 
     Weapon : Weapon option
     Boot   : Protection option
     Hands  : Protection option 
     Loot1  : Consummable option
     Loot2  : Consummable option
}

What I'm having a problem with is the following: once a player buys an item from the store, he may want to transfer the item directly in a character equipment. So, I'm designing a function to put an item in the equipment. If that field was busy, then I would to send the item from the equipment back to the inventory and update the character's equipment with the store's item.

To start to solve my problem, I thought I could put the fields as a list of GameItem option and find out which were Some and see, while iterating in that list, if I could find an item which was of the same type as the one I'm trying to add to the equipment. I have some problems, I don't really know while pattern matching out to check if two items are of the same type. Also, I'm not so sure that my design is the best way to go in order to achieve what I'm want to do.

Right now, I'm have this snippet which is obviously not compiling and I'm looking for a way to make it not only compiling but readable also.

I've seen this post that does some pattern matching directly on the whole record, but I was wondering if there were any other way to do so with high order functions ?

Pattern match on records with option type entries in OCaml

UPDATE 1

I forgot we could pattern match on more than a single element, so my problem really becomes about how to validate dynamically the Some values in the fields of my record and be able to do it via high order functions.

// Updated function sendBackToInventory

member x.sendBackToInventory (gi: GameItem) =
        let mutable itemFound = false
        let equipmentFields = [ Protection(x.Hat.Value, 0) ; Protection(x.Armor.Value,0); Protection(x.Legs.Value,0); Protection(x.Hands.Value,0); Protection(x.Ring.Value,0); Protection(x.Shield.Value,0) ]
        equipmentFields 
        |> List.iter(fun item ->   
            match item, gi with 
            | (:? Consummable as c1, :? Consummable as c2)  -> 
            | (:? Protection as p1, :? Protection as p2)  -> 
            | (:? Weaponry as w1, :? Weaponry as w2)  -> 
            // match oItem with 
            // | Some item -> 
            //     if item = gi then 
            //         itemFound <- true 
            //         x.InventoryManager <! AddSingleItem gi
            //     else 
            //         ()
            // | None -> ()
        )

UPDATE 2

By adding a new discriminated union to represent the category of game item it could be, which makes it, in my opinion, a bit redundant with the domain model, I've overcame my issue somehow but it's not a behaviour that I'd like to keep... There's a lot of boilerplate code that shouldn't be there, but I want at least the functionality to be there.

    type ItemCategory = 
        | Weapon 
        | Shield 
        | Loot 
        | Head 
        | Body 
        | Pant 
        | Finger 
        | Hand

    type Equipment = {
        Hat :   GameItem option
        Armor : GameItem option
        Legs  : GameItem option
        Gloves : GameItem option
        Ring  : GameItem option
        Weapon : GameItem option
        Shield : GameItem option
        Loot1  : GameItem option
        Loot2  : GameItem option 
        Loot3  : GameItem option 
        InventoryManager : IActorRef
    }
    with 
        member x.canAddMoreLoot() = 
            not (x.Loot1.IsSome && x.Loot2.IsSome && x.Loot3.IsSome)

        member x.putItemInEquipment 
            (gi: GameItem) 
            (cat: ItemCategory) = 
            let mutable equipment = x 
            match cat with 
            | Head -> 
                 equipment <-  { x with Hat = Some gi } 
                 match x.Hat with 
                 | None ->  ()
                 | Some h ->  x.InventoryManager <! AddItem h

            | Weapon -> 
                 equipment <- { x with Weapon = Some gi } 
                 match x.Weapon with 
                 | None -> () 
                 | Some w -> x.InventoryManager <! AddItem w

            | Shield -> 
                 equipment <- { x with Weapon = Some gi } 
                 match x.Shield with 
                 | None -> () 
                 | Some sh -> x.InventoryManager <! AddItem sh

            | Loot -> 
                 if not (x.canAddMoreLoot()) then x.InventoryManager <! AddItem gi
                 else 
                    match x.Loot1 with 
                    | Some l -> 
                        match x.Loot2 with 
                        | Some l -> equipment <- { x with Loot3 = Some gi } 
                        | None -> equipment <- { x with Loot2 = Some gi }
                    | None -> equipment <- { x with Loot1 = Some gi } 

            | Finger -> 
                equipment <- { x with Ring = Some gi } 
                match x.Ring with
                | None -> () 
                | Some r -> x.InventoryManager <! AddItem r 

            | Body -> 
                equipment <- { x with Armor = Some gi } 
                match x.Armor with 
                | None -> () 
                | Some a -> x.InventoryManager <! AddItem a 
            | Pant ->
                equipment <- { x with Legs = Some gi } 
                match x.Legs with 
                | None -> () 
                | Some l -> x.InventoryManager <! AddItem l 
            | Hand -> 
                equipment <- { x with Gloves = Some gi } 
                match x.Gloves with 
                | None -> () 
                | Some g -> x.InventoryManager <! AddItem g 
            equipment

Answer 1

I've taken the code from your original update and tweaked it a bit to correct a couple of mistakes you made. I'll talk about those mistakes in a bit, but first, let's look at the corrected code:

type ConsumableItem =
    | HealthPotion
    | ManaPotion 

type Weaponry = 
    | Sword 
    | Spear 
    | BattleAxe 

type CharacterProtection = 
    | Helmet 
    | Gloves 
    | Boots 

type GameItem = 
    | Consumable of ConsumableItem
    | Weapon of Weaponry
    | Protection of CharacterProtection

type Equipment = { 
     Helmet : CharacterProtection option 
     Weapon : Weaponry option
     Boot   : CharacterProtection option
     Hands  : CharacterProtection option 
     Loot1  : ConsumableItem option
     Loot2  : ConsumableItem option
}

// type Inventory omitted for space

First, note that I corrected the spelling of ConsumableItem. It would have compiled just fine, so I won't spend more time on this. Just be aware that the spelling changed, so that if you copy and paste anything from this answer into your code, you'll know to adjust the spelling as appropriate.

Second, I removed the * int from your GameItem DU. It seems to me that that belongs in a different type, say a single-case DU called ItemStack:

type ItemStack = ItemStack of item:GameItem * count:int

Third, I adjusted the types of your Equipment record, which would not have compiled. The cases of a discriminated union are not types; they are constructors. The DU itself is a type. (For more information, see http://fsharpforfunandprofit.com/posts/discriminated-unions/ and particularly the section titled "Constructing a value of a union type"). So you can't have a field Helmet of type Protection, because the name Protection does not refer to a type. The field would have to be of type GameItem. But what you're actually trying to do is ensure that the Helmet field will only ever hold a protection item — so making it of type CharacterProtection works. That still doesn't quite reach the level of making illegal states unrepresentable, because you could put boots in the Helmet slot. But to fully make illegal states unrepresentable, you'd end up with something like this:

type Helmet = Helmet of armorValue:int // Plus any other properties you want
type Boots  = Boots  of armorValue:int
type Gloves = Gloves of armorValue:int

type CharacterProtection =
    | Helmet of Helmet
    | Gloves of Gloves
    | Boots  of Boots

type Equipment = {
    Head  : Helmet option
    Feet  : Boots option
    Hands : Gloves option
    // And so on for weapon, potions, etc.
}

I'll call that the "complex" game model, and your original code (with my fixes) I'll call the "simple" game model. Both can be valuable, it just depends on where you end up with your code.

Okay, now let's forget about the "complex" game model I just showed you and go back to the "simple" game model. The problem you're trying to solve is that when the player buys, say, a helmet from the store, you want to auto-equip the helmet if he didn't have a helmet already equipped. If he did have a helmet equipped, you want the purchased helmet to go in the bag and let him equip it later. (Alternatively, you could offer him the option to auto-equip the helmet that he's just bought, putting the previously-equipped helmet in the bag.)

What you probably want to do, then, is something like this:

let addToInventory newItem inventory =
    let newBag = inventory.Bag |> Array.append [|newItem|]
    { inventory with Bag = newBag }

let playerWantsToAutoEquip newItem =
    // In real game, you'd pop up a yes/no question for the player to click on
    printfn "Do you want to auto-equip your purchase?"
    printfn "Actually, don't bother answering; I'll just assume you said yes."
    true

let equipPurchasedProtection newItem (inventory,equipment) =
    match newItem with
    | Helmet ->
        match equipment.Helmet with
        | None ->
            let newEquipment = { equipment with Helmet = Some newItem }
            (inventory,newEquipment)
        | Some oldHelm
            if (playerWantsToAutoEquip newItem) then
                let newEquipment = { equipment with Helmet = Some newItem }
                let newInventory = inventory |> addToInventory oldHelm
                (newInventory,newEquipment)
            else
                let newInventory = inventory |> addToInventory newItem
                (newInventory,equipment)
    | Gloves ->
        match equipment.Hands with
        | None ->
            let newEquipment = { equipment with Hands = Some newItem }
            (inventory,newEquipment)
        | Some oldGloves
            if (playerWantsToAutoEquip newItem) then
                let newEquipment = { equipment with Hands = Some newItem }
                let newInventory = inventory |> addToInventory oldGloves
                (newInventory,newEquipment)
            else
                let newInventory = inventory |> addToInventory newItem
                (newInventory,equipment)
    | Boots ->
        match equipment.Feet with
        | None ->
            let newEquipment = { equipment with Boot = Some newItem }
            (inventory,newEquipment)
        | Some oldBoots
            if (playerWantsToAutoEquip newItem) then
                let newEquipment = { equipment with Boot = Some newItem }
                let newInventory = inventory |> addToInventory oldBoots
                (newInventory,newEquipment)
            else
                let newInventory = inventory |> addToInventory newItem
                (newInventory,equipment)

let equipPurchasedWeapon newItem (inventory,equipment) =
    // No need to match against newItem here; weapons are simpler
    match equipment.Weapon with
    | None ->
        let newEquipment = { equipment with Weapon = Some newItem }
        (inventory,newEquipment)
    | Some oldWeapon
        if (playerWantsToAutoEquip newItem) then
            let newEquipment = { equipment with Weapon = Some newItem }
            let newInventory = inventory |> addToInventory oldWeapon
            (newInventory,newEquipment)
        else
            let newInventory = inventory |> addToInventory newItem
            (newInventory,equipment)

// I'll skip defining equipPurchasedConsumable since it's very similar

let equipPurchasedItem gameItem (inventory,equipment) =
    let funcToCall =
        match gameItem with
        | Consumable of potion -> equipPurchasedConsumable potion
        | Weapon of weapon     -> equipPurchasedWeapon weapon
        | Protection of armor  -> equipPurchasedProtection armor
    (inventory,equipment) |> funcToCall

Now, there's still some redundancy in those functions. The match cases in equipPurchasedPotion all look very, very similar. So let's abstract out what we can:

let equipHelmet newHelm equipment =
    { equipment with Helmet = Some newHelm }
let getOldHelmet equipment = equipment.Helmet

let equipGloves newGloves equipment =
    { equipment with Hands = Some newGloves }
let getOldGloves equipment = equipment.Hands

let equipBoots newBoots equipment =
    { equipment with Boots = Some newBoots }
let getOldBoots equipment = equipment.Boots

let equipWeapon newWeapon equipment =
    { equipment with Weapon = Some newWeapon }
let getOldWeapon equipment = equipment.Weapon

let genericEquipFunction (getFunc,equipFunc) newItem equipment =
    let oldItem = equipment |> getFunc
    let newEquipment = equipment |> equipFunc newItem
    match oldItem with
    | None -> (None,newEquipment)
    | Some _ ->
        if playerWantsToAutoEquip newItem then
            (oldItem,newEquipment)
        else
            (newItem,equipment)

let equipPurchasedProtection newItem (inventory,equipment) =
    let equipFunction =
        match newItem with
        | Helmet -> genericEquipFunction (getOldHelmet,equipHelmet)
        | Gloves -> genericEquipFunction (getOldGloves,equipGloves)
        | Boots  -> genericEquipFunction (getOldBoots, equipBoots)
    let itemForInventory,newEquipment = equipFunction newItem equipment
    match itemForInventory with
    | None -> (inventory,newEquipment)
    | Some item ->
        let newInventory = inventory |> addToInventory item
        (newInventory,newEquipment)

let equipPurchasedWeapon newItem (inventory,equipment) =
    // Only one possible equipFunction for weapons
    let equipFunction = genericEquipFunction (getOldWeapon,equipWeapon)
    let itemForInventory,newEquipment = equipFunction newItem equipment
    match itemForInventory with
    | None -> (inventory,newEquipment)
    | Some item ->
        let newInventory = inventory |> addToInventory item
        (newInventory,newEquipment)

In fact, now we're able to combine the equipPurchasedProtection and equipPurchasedWeapon functions into a single generic equipPurchasedItem function! The type has to change: now the newItem parameter is going to be of type GameItem. But you can still match against multiple "levels" of nested DUs at once, like so:

let equipPurchasedItem newItem (inventory,equipment) =
    let equipFunction =
        match newItem with
        | Protection Helmet -> genericEquipFunction (getOldHelmet,equipHelmet)
        | Protection Gloves -> genericEquipFunction (getOldGloves,equipGloves)
        | Protection Boots  -> genericEquipFunction (getOldBoots, equipBoots)
        | Weapon _ -> genericEquipFunction (getOldWeapon,equipWeapon)
        // getOldLoot1 and similar functions not shown. Just pretend they exist.
        | Consumable HealthPotion -> genericEquipFunction (getOldLoot1,equipLoot1)
        | Consumable ManaPotion   -> genericEquipFunction (getOldLoot2,equipLoot2)
    let itemForInventory,newEquipment = equipFunction newItem equipment
    match itemForInventory with
    | None -> (inventory,newEquipment)
    | Some item ->
        let newInventory = inventory |> addToInventory item
        (newInventory,newEquipment)

This technique of having a generic get and set function, and pairing them up in a tuple that you can pass around, is usually called a "lens". Using lenses can often let you write much more generic code that doesn't have to worry about how you update a particular part of your data structures. You can just write generic code that does your business logic, and then tells the lens "Here's the new data that should go into the structure. I don't care how you do it, just put it in there somehow". This allows better separation of concerns: the code that decides what to do is separate from the code that knows how to do it. Here's how that code would have looked using lenses:

type Lens<'r,'a> = getter:('r -> 'a) * setter:('a -> 'r -> 'r)

let equipHelmet newHelm equipment =
    { equipment with Helmet = Some newHelm }
let getOldHelmet equipment = equipment.Helmet
// Convention for lenses is to give them a name that ends with one underscore
let Helmet_ = (getOldHelmet,equipHelmet)
// Now Helmet_ has type Lens<CharacterProtection,Equipment>

let equipGloves newGloves equipment =
    { equipment with Hands = Some newGloves }
let getOldGloves equipment = equipment.Hands
let Gloves_ = (getOldGloves,equipGloves)
// Gloves_ also has type Lens<CharacterProtection,Equipment>

let equipBoots newBoots equipment =
    { equipment with Boots = Some newBoots }
let getOldBoots equipment = equipment.Boots
let Boots_ = (getOldBoots,equipBoots)
// Boots_ also has type Lens<CharacterProtection,Equipment>

let equipWeapon newWeapon equipment =
    { equipment with Weapon = Some newWeapon }
let getOldWeapon equipment = equipment.Weapon
let Weapon_ = (getOldWeapon,equipWeapon)
// Weapon_ has a different type: Lens<Weaponry,Equipment>

// And so on for getOldLoot1,equipLoot1, and so on

let equipWithLens itemLens newItem equipment =
    let oldItem = equipment |> itemLens.getter
    let newEquipment = equipment |> itemLens.setter newItem
    match oldItem with
    | None -> (None,newEquipment)
    | Some _ ->
        if playerWantsToAutoEquip newItem then
            (oldItem,newEquipment)
        else
            (newItem,equipment)

let equipPurchasedProtection newItem (inventory,equipment) =
    let lens =
        match newItem with
        | Protection Helmet -> Helmet_
        | Protection Gloves -> Gloves_
        | Protection Boots  -> Boots_
        | Weapon -> Weapon_
        | Consumable HealthPotion -> Loot1_
        | Consumable ManaPotion   -> Loot2_
    let itemForInventory,newEquipment = equipWithLens lens newItem equipment
    match itemForInventory with
    | None -> (inventory,newEquipment)
    | Some item ->
        let newInventory = inventory |> addToInventory item
        (newInventory,newEquipment)

I hope that's enough to give you an idea of how to apply this concept to things like rings, chest armor, leg armor, and so on.

WARNING: All of this code was just typed into the StackOverflow edit window; I did NOT test any of it in F# Interactive. So there may be typos. The general idea should work, though.

UPDATE: Looking through my code, I see a type error that I made consistently throughout. The getters and setters for the various kinds of equipment (helmet, gloves, etc.) are expecting two different kinds of values! For example, for helmets, the getter is just returning equipment.Helmet, which is a CharacterProtection option. But the setter is assigning Some newItem to the Helmet field. That means that it's expecting newItem to be a CharacterProtection — but the way I wrote the generic equip functions, I'm getting the item from the equipment record and then passing that to the setter. So I'm getting a CharacterProtection option, and passing that to the setter which tries to assign Some newItem — so my setter is trying to assign a CharacterProtection option option! Oops.

To fix this mistake, take all the setter functions and remove the Some from them. Then the type they're expecting won't be a CharacterProtection, it'll be a CharacterProtection option — just like the getters. That's the key: the getters and setters should be expecting the same type.

UPDATE 2: As promised, I'll discuss design a little bit. Let's look at what the Helmet_ lens looks like if it's a member of the record, and what it looks like if it's a function.

type Equipment = { 
     Helmet : CharacterProtection option 
     Weapon : Weaponry option
     Boot   : CharacterProtection option
     Hands  : CharacterProtection option 
     Loot1  : ConsumableItem option
     Loot2  : ConsumableItem option }
     with
        member x.getHelmet () = x.Helmet
        member x.equipHelmet newHelm = { x with Helmet = newHelm }
        member x.Helmet_ = (x.getHelmet, x.equipHelmet)

let getHelmetFun e = e.Helmet
let equipHelmetFun newHelm e = { e with Helmet = newHelm }
let HelmetFun_ = (getHelmetFun, equipHelmetFun)

So far, the only visible difference is that the external functions need an explicit parameter, whereas the instance methods have it "baked in". That's the point of instance methods, so this is no surprise. But let's look at what it's like to use these two different lens implementations as parameters to some other function:

let getWithInstanceLens lens =
    let getter = fst lens
    getter ()

let getWithExternalLens lens record =
    let getter = fst lens
    getter record

Again, no real surprises here. The lens that's an instance variable has its instance "baked in", so we don't need to pass it any parameters. The lens that was defined as an external function doesn't have any "baked in" record, so it needs to be passed one. Note that it's a completely generic function (both of these are completely generic), which is why I named the parameter record instead of equipment: it can handle any lens and matching record (and the getWithInstanceLens can handle any lens whose instance is "baked in" to the getter).

But when we try to use these as parameters to, say, List.map, we discover something interesting. Let's look at the code, then talk about it.

let sampleEquipment = { Helmet = Some Helmet
                        Weapon = Some BattleAxe
                        Boot   = Some Boots
                        Hands  = Some Gloves
                        Loot1  = Some HealthPotion
                        Loot2  = None }

let noHelm = { sampleEquipment with Helmet = None }
let noBoots = { noHelm with Boot = None }
let noWeapon = { noBoots with Weapon = None }

let progressivelyWorseEquipment = [ sampleEquipment; noHelm; noBoots; noWeapon ]

let demoExternal equipmentList =
    equipmentList
    |> List.map (getWithExternalLens HelmetFun_)

let demoInstance equipmentList =
    equipmentList
    |> List.map (fun x -> getWithInstanceLens x.Helmet_)

demoExternal progressivelyWorseEquipment
demoInstance progressivelyWorseEquipment
// Both return [Some Helmet; None; None; None]

The first thing we notice is that because the instance lens has its instance "baked in", it's actually slightly uglier to pass it as an argument to higher-order functions like List.map. We have to explicitly construct a lambda to call it, and we can't take advantage of F#'s nice partial-application syntax. But there's another problem. It won't become obvious until you actually copy this code into your F# IDE — but this version of demoInstance won't compile! I lied when I said that both functions return a value; in fact, the F# compiler complains about the x.Helmet_ expression in demoInstance, producing the following error message:

Lookup on object of indeterminate type based on information prior to this program point. A type annotation may be needed prior to this program point to constrain the type of the object. This may allow the lookup to be resolved.

With the demoInstance function, F#'s type inference can't help us out! All it knows at that point is that the equipmentList is a list of some type (if you hover over it in your IDE, the tooltip will show you that it's of type 'a list), and that the unknown 'a type must have an instance called Helmet_. But the F# compiler doesn't know enough at this point to produce correct CIL bytecode — and at the end of the day, that's its main job. There could be many different classes with a Helmet_ instance, so it has to ask you for more information. And so you have to provide an explicit type annotation on your function, which now looks like this:

let demoInstance (equipmentList : Equipment list) =
    equipmentList
    |> List.map (fun x -> getWithInstanceLens x.Helmet_)

For contrast, here's the demoExternal function again:

let demoExternal equipmentList =
    equipmentList
    |> List.map (getWithExternalLens HelmetFun_)

As you can see, it's much cleaner to use external functions.

On the other hand, using static methods in your record definition gets you the best of both worlds, pretty much: the lenses are strongly associated with the record type, and the way you use them is pretty much identical to using external functions:

type Equipment = {
     Helmet : CharacterProtection option
     Weapon : Weaponry option
     Boot   : CharacterProtection option
     Hands  : CharacterProtection option
     Loot1  : ConsumableItem option
     Loot2  : ConsumableItem option }
     with
        static member getHelmet x = x.Helmet
        static member equipHelmet newHelm x = { x with Helmet = newHelm }
        static member Helmet_ = (Equipment.getHelmet, Equipment.equipHelmet)

let demoStatic equipmentList =
    equipmentList
    |> List.map (getWithExternalLens Equipment.Helmet_)

Here, there's no disadvantage in terms of ease of use; this looks pretty much identical to the "external functions" example. Personally, I'd prefer either this approach, or else the "define them in a module" approach:

module EquipmentLenses =
    let getHelmet e = e.Helmet
    let equipHelmet hewNelm e = { e with Helmet = newHelm }
    let Helmet_ = (getHelmet,equipHelmet)

let demoModule equipmentList =
    equipmentList
    |> List.map (getWithExternalLens EquipmentLenses.Helmet_)

Between static methods and external modules, it's really just a matter of personal preference — how you prefer to organize your code. Either one is a good solution.