Типы F # и динамическая оценка для базовых вычислений - PullRequest
Новая
       26

Типы F # и динамическая оценка для базовых вычислений

1 голос
/ 29 октября 2011

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

type Expr =
    | True
    | False
    | Not of Expr
    | And of Expr * Expr

и должно быть очевидно, чего я хочу достичь: иметь возможность инкапсулировать различные функции, такие как Not и And, для использования в одном вычислении, например And(And(True, Not(False)), True), но в настоящее время я не понимаю (это мой первый время написания такого «сложного» функционального кода) как использовать эту структуру и написать правильные методы, как, например, я могу написать для оценки 

let evalLogic (expr : Expr) : bool =
    match expr with
    | True  -> true
    | False -> false
    | _     -> false (* eval the expression which is not "atomic" *)

а затем как метод 

let And (left : Expr , right : Expr ) : Expr =
    let value = evalLogic(left) && evalLogic(right)
    match value with
    | true  -> True
    | false -> False

однако я знаю, что это дерьмо, а не правильный способ реализации этого! Можете ли вы дать мне подсказку, как добиться желаемого поведения, и описать, как его расширить?

Ответы [ 3 ]

6 голосов
/ 29 октября 2011

При написании функционального кода для представления и оценки выражений типичным шаблоном является определение типа выражения как различимого объединения (как вы это сделали!), А затем запись функции, которая принимает выражение и возвращает результат. Ваши логические выражения будут оцениваться как логические, поэтому вам нужна функция: 

evalLogic : Expr -> bool

В функции вам нужно написать регистр для каждого возможного выражения. Ваш пример обрабатывает False и True, а код Bluepixy показывает все остальное. Общая идея состоит в том, что функция может рекурсивно оценивать все подвыражения - если у вас есть And(e1, e2), то вы можете вычислить e1 и e2 до двух логических значений и затем объединить их (используя &&).

Ваша функция And не нужна, поскольку вся оценка выполняется в функции evalLogic. Это типичный способ работы в функциональном стиле (поскольку тип выражения не должен часто меняться). Тем не менее, вы также можете поддерживать больше бинарных операций, используя: 

type Expr = 
  | Constant of bool
  | Unary of Expr * (bool -> bool)
  | Binary of Expr * Expr * (bool -> bool -> bool)

Здесь идея состоит в том, что выражение является либо константой, либо приложением некоторого двоичного или унарного логического оператора. Например, чтобы представить true && not false, вы можете написать: 

Binary(Constant(true), Unary(Constant(false), not), (&&))

Теперь дерево выражений также содержит функцию, которую следует использовать, поэтому для оценки нужно просто вызвать функцию (и вы можете легко использовать все стандартные логические операторы). Например, чехол для Binary выглядит так: 

let rec evalLogic e =
  // pattern matching
  |  Binary(e1, e2, op) -> op (evalLogic e1) (evalLogic e2)
3 голосов
/ 29 октября 2011 
let rec evalLogic (expr : Expr) : bool =
    match expr with
    | True  -> true
    | False -> false
    | Not (exp ) -> not (evalLogic exp)
    | And (expL, expR) -> evalLogic expL && evalLogic expR

ДЕМО 

> evalLogic <| And(And(True, Not(False)), True);;
val it : bool = true
2 голосов
/ 29 октября 2011

Ваш вопрос "как мне продлить evalLogic для Not и And?"

Если это так, то вам нужно расширить сопоставление с образцом в выражении let, чтобы сопоставить два других конструктора: 

let evalLogic (expr : Expr) : bool =
    match expr with
    | True  -> true
    | False -> false
    | Not (myexpr) -> ... (* match constructor `Not`, bind the expression to `myexpr`)
    | And (lefte, righte) -> ...

Затем вы можете заполнить правые части кодом F #.

Вот некоторая информация о сопоставлении с образцом в F #.

...