Eliminating my explicit state passing via like, monads and stuff

Question

I'm working through the book Land of Lisp in F# (yeah weird, I know). For their first example text adventure, they make use of global variable mutation and I'd like to avoid it. My monad-fu is weak, so right now I'm doing ugly state passing like this:

let pickUp player thing (objects: Map<Location, Thing list>) =
    let objs = objects.[player.Location]
    let attempt = objs |> List.partition (fun o -> o.Name = thing)
    match attempt with
    | [], _ -> "You cannot get that.", player, objs
    | thing :: _, things ->
        let player' = { player with Objects = thing :: player.Objects }
        let msg = sprintf "You are now carrying %s %s" thing.Article thing.Name
        msg, player', things

let player = { Location = Room; Objects = [] }   

let objects =
    [Room, [{ Name = "whiskey"; Article = "some" }; { Name = "bucket"; Article = "a" }];
    Garden, [{ Name = "chain"; Article = "a length of" }]]
    |> Map.ofList

let msg, p', o' = pickUp player "bucket" objects
// etc.

How can I factor out the explicit state to make it prettier? (Assume I have access to a State monad type if it helps; I know there is sample code for it in F# out there.)

Edp

The idiomatic thing to do in F# would be using some mutable variables on the class or module level. But I understand that you are probably interested in using a state monad for pedagogical reasons? – Pyre

@wmeyer, you're correct. Though if you post an answer with the idiomatic version I'll upvote it nonetheless, for the sake of others who might want to know how to do it the "right way for F#" – Edp

"Programming F#" by Chris Smith has a section on this. You can see much (but not all) of the section in the preview on Google Books. (I'm writing this as a comment instead of an answer, because it is not a complete answer, but just a reference.) – Pyre

Answer 1

If you want to use the state monad to thread the player's inventory and world state through the pickUp function, here's one approach:

type State<'s,'a> = State of ('s -> 'a * 's)

type StateBuilder<'s>() =
  member x.Return v : State<'s,_> = State(fun s -> v,s)
  member x.Bind(State v, f) : State<'s,_> =
    State(fun s ->
      let (a,s) = v s
      let (State v') = f a
      v' s)

let withState<'s> = StateBuilder<'s>()

let getState = State(fun s -> s,s)
let putState v = State(fun _ -> (),v)

let runState (State f) init = f init

type Location = Room | Garden
type Thing = { Name : string; Article : string }
type Player = { Location : Location; Objects : Thing list }

let pickUp thing =
  withState {
    let! (player, objects:Map<_,_>) = getState
    let objs = objects.[player.Location]
    let attempt = objs |> List.partition (fun o -> o.Name = thing)    
    match attempt with    
    | [], _ -> 
        return "You cannot get that."
    | thing :: _, things ->    
        let player' = { player with Objects = thing :: player.Objects }        
        let objects' = objects.Add(player.Location, things)
        let msg = sprintf "You are now carrying %s %s" thing.Article thing.Name
        do! putState (player', objects')
        return msg
  }

let player = { Location = Room; Objects = [] }   
let objects =
  [Room, [{ Name = "whiskey"; Article = "some" }; { Name = "bucket"; Article = "a" }]
   Garden, [{ Name = "chain"; Article = "a length of" }]]    
  |> Map.ofList

let (msg, (player', objects')) = 
  (player, objects)
  |> runState (pickUp "bucket")

Aesthetically

Wow, that's more straightforward than I thought! Thanks! – Edp

Answer 2

If you want to use mutable state in F#, then the best way is just to write a mutable object. You can declare a mutable Player type like this:

type Player(initial:Location, objects:ResizeArray<Thing>) =
  let mutable location = initial
  member x.AddThing(obj) =
    objects.Add(obj)
  member x.Location 
    with get() = location
    and set(v) = location <- v

Using monads to hide mutable state isn't as common in F#. Using monads gives you essentially the same imperative programming model. It hides the passing of state, but it doesn't change the programming model - there is some mutable state that makes it impossible to parallelize the program.

If the example uses mutation, then it is probably because it was designed in an imperative way. You can, change the program architecture to make it more functional. For example, instead of picking the item (and modifying the player), the pickUp function could just return some object representing a request to pick the item. The world would then have some engine that evaluates these requests (collected from all players) and calculates the new state of the world.

Hyson

But the state monad approach is pure, doesn't that count for something? Still, in the end I'll probably go with your method, as it is the most idiomatic. Makes me feel like I'm writing C# and not F#, though :) – Edp

@J Cooper: The monad approach forces you to write the program in a sequential way, which is why it matters in Haskell. You don't really need that in F#. Just like mutability, it makes the state implicit, so if you reorder lines that don't depend on each other (directly) you may get different program behavior (because of the state). – Hyson

You can write program in a more functional way if you make all objects immutable and all operations build a new state of the object or the world. Then you'll probably want to use slightly different architecture though. – Hyson

Also, you can benefit from functional style even if you use mutable objects - when implementing some computations or processing algorithms, the functional style will help. – Hyson

How would you build the new state of the world? Imagining the world has several players and you need to change some state of one of the players would you return a new World with a list of players made by replacing 1 player in old list? It feels very inefficient. – Unrepair