F# usage of computational expression

Question

I am a student who wants to learn F# and functional programming logic but I have a problem about computation expression. I think I can not understand the logic of computation expression because I cannot solve this question and I do not see any useful thing about using computation expression in this question. I am thinking that it is a way to override several basic functionality of F# and implement in our own way but in this question I cannot see the point. Thank you for your time and sorry for asking long question.

A function from a type 'env to a type 'a can be seen as a computation that
computes a value of type 'a based on an environment of type 'env. We call such
a computation a reader computation, since compared to ordinary computations,
it can read the given environment. Below you find the following:

    • the definition of a builder that lets you express reader computations
    using computation expressions

    • the definition of a reader computation ask : 'env -> 'env that returns the
    environment

    • the definition of a function runReader : ('env -> 'a) -> 'env -> 'a that
    runs a reader computation on a given environment

    • the definition of a type Expr of arithmetic expressions

Implement a function eval : Expr -> Map<string, int> -> int that evaluates
an expression using an environment which maps identifiers to values.

NB! Use computation expressions for reader computations in your implementation.

Note that partially applying eval to just an expression will yield a function of
type map <string, int> -> int, which can be considered a reader computation.
This observation is the key to using computation expressions.

The expressions are a simplified subset based on
Section 18.2.1 of the F# 4.1 specification:
https://fsharp.org/specs/language-spec/4.1/FSharpSpec-4.1-latest.pdf

*)

type ReaderBuilder () =
member this.Bind   (reader, f) = fun env -> f (reader env) env
member this.Return x           = fun _   -> x

let reader = new ReaderBuilder ()

let ask = id

let runReader = (<|)

type Expr =
| Const  of int          // constant
| Ident  of string       // identifier
| Neg    of Expr         // unary negation, e.g. -1
| Sum    of Expr * Expr  // sum 
| Diff   of Expr * Expr  // difference
| Prod   of Expr * Expr  // product
| Div    of Expr * Expr  // division
| DivRem of Expr * Expr  // division remainder as in 1 % 2 = 1
| Let    of string * Expr * Expr // let expression, the string is the identifier.


let eval (e:Expr) : (Map<string, int> -> int) = failwith "not yet implemented"

// //Example:
// //keeping in mind the expression: let a = 5 in (a + 1) * 6
// let expr = Let ("a",Const 5, Prod(Sum(Ident("a"),Const 1),Const 6))
// eval expr Map.empty<string,int>
// should return 36     
`

Answer 1

The reader computation expression will allow you to implicitly thread an environment through multiple computations. So for instance, you might have something like:

let rec eval e : Map<string,int> -> int =
    reader {
        match e with
        ...
        | Add(e1, e2) ->
            let! i1 = eval e1 // implicitly thread environment through
            let! i2 = eval e2 // same here
            return i1 + i2
        ...
    }

Even though eval's full signature is Expr -> Map<string,int> -> int, when we're using let! inside the computation expression we only need to pass the Expr in, and we can bind the result to an int without needing to explicitly pass the map around.

Note that for the Ident and Let cases, you need to actually deal with the map explicitly to look up or set identifiers' values - but you can use let! m = ask to pull the map out of the environment.

It is of course perfectly possible to write an implementation of eval that doesn't use a reader expression, but you might find that threading the environment everywhere just adds tedious noise to the code, making it harder to follow.