F # использование вычислительного выражения

Question

Я студент, который хочет изучать F # и логику функционального программирования, но у меня проблема с выражением вычислений.Я думаю, что не могу понять логику выражения вычислений, потому что я не могу решить этот вопрос, и я не вижу никакой полезной вещи об использовании выражения вычисления в этом вопросе.Я думаю, что это способ переопределить несколько основных функций F # и реализовать его по-своему, но в этом вопросе я не вижу смысла.Спасибо за ваше время и извините за задание длинного вопроса.

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

Чтобы действительно понять, насколько полезным может быть вычислительное выражение, вам нужно реализовать решение как с ним, так и без него.

Без выражения вычисления (CE)

При работе с монадами вам всегда нужноbind и функция возврата, которую здесь я буду называть rtn, потому что return - это ключевое слово:

let bind f reader = fun env -> f (reader env) env
let rtn x = fun _ -> x

Они являются лишь копией тех, что в упражнении.

чтобы реализовать выражение Sum с помощью bind и rtn, вы можете сделать это следующим образом

let rec eval e : Map<string,int> -> int =
    match e with
    ...
    | Sum(e1, e2) -> 
        eval     e1 |> bind (fun i1 -> 
            eval e2 |> bind (fun i2 -> 
               rtn (i1 + i2) ))
    ...

Этот код работает, но его трудно прочитать.

---

С операторами

Вы можете упростить монадический код, используя некоторые операторы для bind и map:

let (>>=) reader f = bind  f         reader
let (|>>) reader f = bind (f >> rtn) reader  // map

, и тогда eval может выглядеть следующим образом:

let rec eval e : Map<string,int> -> int = reader {
    match e with
    ...
    | Sum(e1, e2) -> 
        eval e1 >>= fun i1 -> 
        eval e2 |>> fun i2 -> 
        i1 + i2
    ...

, что является улучшением, но все же немного странно, если вы не привыкли к такому типу кода.

---

С CE

Вы можете сравнить его с выражением вычисленияв ответе @ kvb:

let rec eval e : Map<string,int> -> int = reader {
    match e with
    ...
    | Sum(e1, e2) ->
        let! i1 = eval e1
        let! i2 = eval e2
        return i1 + i2
    ...

Все элементы одинаковы bно СЕ немного проще и понятнее.Это выглядит как обычный код, а не как монадический код.

---

Без монады Reader

В качестве упражнения давайте посмотрим, как будет выглядеть eval, если бы мы не использовали монаду Reader и вместо этого должны были пройтиenv каждый раз:

let rec eval e (env: Map<string,int>) : int =
    match e with
    ...
    | Sum(e1, e2) -> 
        let i1 = eval e1 env
        let i2 = eval e2 env
        i1 + i2
    ...

Эй!Это выглядит почти так же, как код CE, за исключением взрыва !, return и env, которые в монаде читателя неявны.

Answer 2

Вычислительное выражение для чтения позволит вам неявно обрабатывать среду с помощью нескольких вычислений.Так, например, у вас может быть что-то вроде:

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
        ...
    }

Даже если полная подпись eval равна Expr -> Map<string,int> -> int, когда мы используем let! внутри выражения вычисления, нам нужно только передатьExpr in, и мы можем связать результат с int без необходимости явной передачи карты.

Обратите внимание, что для случаев Ident и Let вам необходимо иметь дело сс картой явно для поиска или установки значений идентификаторов - но вы можете использовать let! m = ask, чтобы вытащить карту из среды.

Конечно, вполне возможно написать реализацию eval, котораяне использует выражение reader, но вы можете обнаружить, что многопоточность среды повсюду просто добавляет утомительный шум в код, усложняя его выполнение.