F#
Monades

.NET Framework algorithm ASP.NET C# Language Entity Framework Haskell Language GNU/Linux Scala Language Microsoft SQL Server wpf
Recherche…


Comprendre Monads vient de la pratique

Cette rubrique est destinée aux développeurs F # intermédiaires à avancés

"Que sont les Monads?" est une question commune. C'est facile à répondre, mais comme dans Hitchhikers guide to galaxy, nous réalisons que nous ne comprenons pas la réponse car nous ne savions pas ce que nous demandions après.

Beaucoup croient que la façon de comprendre Monads est de les pratiquer. En tant que programmeurs, nous ne nous soucions généralement pas des fondements mathématiques de ce que sont le principe de substitution de Liskov, ses sous-types ou sous-classes. En utilisant ces idées, nous avons acquis une intuition pour ce qu'ils représentent. La même chose est vraie pour les Monads.

Afin de vous aider à démarrer avec Monads, cet exemple montre comment créer une bibliothèque Monadic Parser Combinator . Cela pourrait vous aider à démarrer mais la compréhension viendra de l'écriture de votre propre bibliothèque Monadic.

Suffisamment de temps, temps pour le code

Le type de parseur: 

// A Parser<'T> is a function that takes a string and position
//  and returns an optionally parsed value and a position
//  A parsed value means the position points to the character following the parsed value
//  No parsed value indicates a parse failure at the position
type Parser<'T> = Parser of (string*int -> 'T option*int)

En utilisant cette définition d'un analyseur, nous définissons certaines fonctions d'analyse fondamentales 

// Runs a parser 't' on the input string 's'
let run t s =
  let (Parser tps) = t
  tps (s, 0)

// Different ways to create parser result
let succeedWith v p = Some v, p
let failAt        p = None  , p

// The 'satisfy' parser succeeds if the character at the current position 
//  passes the 'sat' function
let satisfy sat : Parser<char> = Parser <| fun (s, p) ->
  if p < s.Length && sat s.[p] then succeedWith s.[p] (p + 1)
  else failAt p

// 'eos' succeeds if the position is beyond the last character.
//  Useful when testing if the parser have consumed the full string
let eos : Parser<unit> = Parser <| fun (s, p) ->
  if p < s.Length then failAt p
  else succeedWith () p

let anyChar       = satisfy (fun _ -> true)
let char ch       = satisfy ((=) ch)
let digit         = satisfy System.Char.IsDigit
let letter        = satisfy System.Char.IsLetter

satisfy est une fonction qui donne une fonction sat un analyseur qui réussit si nous n'avons pas passé EOS et le caractère à la position actuelle passe la fonction sat . En utilisant satisfy nous créons un certain nombre d'analyseurs de caractères utiles.

En cours d'exécution dans FSI: 

> run digit "";;
val it : char option * int = (null, 0)
> run digit "123";;
val it : char option * int = (Some '1', 1)
> run digit "hello";;
val it : char option * int = (null, 0)

Nous avons des analyseurs fondamentaux en place. Nous allons les combiner en analyseurs plus puissants utilisant des fonctions de combinateur d'analyseur 

// 'fail' is a parser that always fails
let fail<'T>      = Parser <| fun (s, p) -> failAt p
// 'return_' is a parser that always succeed with value 'v'
let return_ v     = Parser <| fun (s, p) -> succeedWith v p

// 'bind' let us combine two parser into a more complex parser
let bind t uf     = Parser <| fun (s, p) ->
  let (Parser tps) = t
  let tov, tp = tps (s, p)
  match tov with
  | None    -> None, tp
  | Some tv ->
    let u = uf tv
    let (Parser ups) = u
    ups (s, tp)

Les noms et les signatures ne sont pas choisis arbitrairement mais nous ne nous en occuperons pas, voyons plutôt comment nous utilisons bind pour combiner un analyseur plus complexe: 

> run (bind digit (fun v -> digit)) "123";;
val it : char option * int = (Some '2', 2)
> run (bind digit (fun v -> bind digit (fun u -> return_ (v,u)))) "123";;
val it : (char * char) option * int = (Some ('1', '2'), 2)
> run (bind digit (fun v -> bind digit (fun u -> return_ (v,u)))) "1";;
val it : (char * char) option * int = (null, 1)

Cela nous montre que la bind nous permet de combiner deux analyseurs en un analyseur plus complexe. Comme résultat de bind est un analyseur qui à son tour peut être combiné à nouveau. 

> run (bind digit (fun v -> bind digit (fun w -> bind digit (fun u -> return_ (v,w,u))))) "123";;
val it : (char * char * char) option * int = (Some ('1', '2', '3'), 3)

bind sera la manière fondamentale de combiner les analyseurs bien que nous définissions des fonctions d’aide pour simplifier la syntaxe.

Une des choses qui peut simplifier la syntaxe sont les expressions de calcul . Ils sont faciles à définir: 

type ParserBuilder() =
  member x.Bind       (t, uf) = bind      t   uf
  member x.Return     v       = return_   v
  member x.ReturnFrom t       = t

// 'parser' enables us to combine parsers using 'parser { ... }' syntax
let parser = ParserBuilder()

FSI 

let p = parser {
          let! v = digit
          let! u = digit
          return v,u
        }
run p "123"
val p : Parser<char * char> = Parser <fun:bind@49-1>
val it : (char * char) option * int = (Some ('1', '2'), 2)

Ceci est équivalent à: 

> let p = bind digit (fun v -> bind digit (fun u -> return_ (v,u)))
run p "123";;
val p : Parser<char * char> = Parser <fun:bind@49-1>
val it : (char * char) option * int = (Some ('1', '2'), 2)

Un autre combinateur d'analyseur fondamental que nous allons utiliser est orElse : 

// 'orElse' creates a parser that runs parser 't' first, if that is successful
//  the result is returned otherwise the result of parser 'u' is returned
let orElse t u    = Parser <| fun (s, p) ->
  let (Parser tps) = t
  let tov, tp = tps (s, p)
  match tov with
  | None    -> 
    let (Parser ups) = u
    ups (s, p)
  | Some tv -> succeedWith tv tp

Cela nous permet de définir letterOrDigit comme ceci: 

> let letterOrDigit = orElse letter digit;;
val letterOrDigit : Parser<char> = Parser <fun:orElse@70-1>
> run letterOrDigit "123";;
val it : char option * int = (Some '1', 1)
> run letterOrDigit "hello";;
val it : char option * int = (Some 'h', 1)
> run letterOrDigit "!!!";;
val it : char option * int = (null, 0)

Une note sur les opérateurs Infix

Une préoccupation commune à la PF est l'utilisation d'opérateurs infixes inhabituels tels que >>= , >=> , <- et ainsi de suite. Cependant, la plupart ne sont pas préoccupés par l'utilisation de + , - , * , / et % , ce sont des opérateurs bien connus utilisés pour composer des valeurs. Cependant, une grande partie de la planification familiale consiste à composer non seulement des valeurs, mais aussi des fonctions. Pour un développeur de FP intermédiaire, les opérateurs infixes >>= , >=> , <- sont bien connus et devraient avoir des signatures spécifiques ainsi que des sémantiques.

Pour les fonctions que nous avons définies jusqu'à présent, nous définirions les opérateurs infixes suivants utilisés pour combiner les analyseurs syntaxiques: 

let (>>=)   t   uf  = bind t uf
let (<|>)   t   u   = orElse t u

Donc >>= signifie bind et <|> signifie orElse .

Cela nous permet de combiner les analyseurs plus succincts: 

let letterOrDigit = letter <|> digit
let p = digit >>= fun v -> digit >>= fun u -> return_ (v,u)

Afin de définir des combinateurs d'analyse avancés qui nous permettront d'analyser des expressions plus complexes, nous définissons quelques combinateurs d'analyseurs plus simples: 

// 'map' runs parser 't' and maps the result using 'm'
let map m t       = t >>= (m >> return_)
let (>>!) t m     = map m t
let (>>%) t v     = t >>! (fun _ -> v)

// 'opt' takes a parser 't' and creates a parser that always succeed but
//  if parser 't' fails the new parser will produce the value 'None'
let opt t         = (t >>! Some) <|> (return_ None)

// 'pair' runs parser 't' and 'u' and returns a pair of 't' and 'u' results
let pair t u      = 
  parser {
    let! tv = t
    let! tu = u
    return tv, tu
  }

Nous sommes prêts à définir many et plus sepBy car ils appliquent les analyseurs d’entrée jusqu’à ce qu’ils échouent. Puis many et sepBy renvoie le résultat agrégé: 

// 'many' applies parser 't' until it fails and returns all successful
//  parser results as a list
let many t =
  let ot = opt t
  let rec loop vs = ot >>= function Some v -> loop (v::vs) | None -> return_ (List.rev vs)
  loop []

// 'sepBy' applies parser 't' separated by 'sep'. 
//  The values are reduced with the function 'sep' returns
let sepBy t sep     =
  let ots = opt (pair sep t)
  let rec loop v = ots >>= function Some (s, n) -> loop (s v n) | None -> return_ v
  t >>= loop

Création d'un analyseur d'expression simple

Avec les outils que nous avons créés, nous pouvons maintenant définir un analyseur pour des expressions simples telles que 1+2*3

Nous commençons par le bas en définissant un analyseur pour les entiers pint 

// 'pint' parses an integer
let pint = 
  let f s v = 10*s + int v - int '0'
  parser {
    let! digits = many digit
    return! 
      match digits with
      | [] -> fail
      | vs -> return_ (List.fold f 0 vs)
  }

Nous essayons d'analyser autant de chiffres que possible, le résultat est une char list . Si la liste est vide, nous fail , sinon nous plions les caractères en un entier.

Test de pint en FSI: 

> run pint "123";;
val it : int option * int = (Some 123, 3)

En outre, nous devons analyser les différents types d’opérateurs utilisés pour combiner des valeurs entières: 

// operator parsers, note that the parser result is the operator function 
let padd      = char '+' >>% (+)
let psubtract = char '-' >>% (-)
let pmultiply = char '*' >>% (*)
let pdivide   = char '/' >>% (/)
let pmodulus  = char '%' >>% (%)

FSI: 

> run padd "+";;
val it : (int -> int -> int) option * int = (Some <fun:padd@121-1>, 1)

Tout attacher ensemble: 

// 'pmullike' parsers integers separated by operators with same precedence as multiply
let pmullike  = sepBy pint (pmultiply <|> pdivide <|> pmodulus)
// 'paddlike' parsers sub expressions separated by operators with same precedence as add
let paddlike  = sepBy pmullike (padd <|> psubtract)
// 'pexpr' is the full expression
let pexpr     =
  parser {
    let! v = paddlike
    let! _ = eos      // To make sure the full string is consumed
    return v
  }

Tout faire en FSI: 

> run pexpr "2+123*2-3";;
val it : int option * int = (Some 245, 9)

Conclusion

En définissant l’ Parser<'T> , return_ , bind et en s’assurant qu’ils obéissent aux lois monadiques, nous avons construit un framework simple mais puissant de Combinator Monadic Parser.

Les monades et les analyseurs vont de pair car les analyseurs sont exécutés dans un état analyseur. Monads nous permet de combiner des analyseurs tout en masquant l'état de l'analyseur, réduisant ainsi l'encombrement et améliorant la composabilité.

Le framework que nous avons créé est lent et ne génère aucun message d'erreur, ceci afin de garder le code succinct. FParsec fournit à la fois des performances acceptables et d'excellents messages d'erreur.

Cependant, un exemple seul ne peut pas donner une compréhension de Monads. Il faut pratiquer les Monades.

Voici quelques exemples sur Monads que vous pouvez essayer d’implémenter pour atteindre vos objectifs:

  1. State Monad - Autorise le transport implicite de l'état d'environnement caché
  2. Tracer Monad - Permet de tracer implicitement l'état de trace. Une variante de State Monad
  3. Tortue Monade - Une Monade pour créer des programmes Tortue (Logos). Une variante de State Monad
  4. Continuation Monad - Une coroutine Monad. Un exemple de ceci est async dans F #

La meilleure chose à faire pour apprendre serait de créer une application pour Monads dans un domaine avec lequel vous êtes à l'aise. Pour moi c'était des parseurs.

Code source complet: 

// A Parser<'T> is a function that takes a string and position
//  and returns an optionally parsed value and a position
//  A parsed value means the position points to the character following the parsed value
//  No parsed value indicates a parse failure at the position
type Parser<'T> = Parser of (string*int -> 'T option*int)

// Runs a parser 't' on the input string 's'
let run t s =
  let (Parser tps) = t
  tps (s, 0)

// Different ways to create parser result
let succeedWith v p = Some v, p
let failAt        p = None  , p

// The 'satisfy' parser succeeds if the character at the current position 
//  passes the 'sat' function
let satisfy sat : Parser<char> = Parser <| fun (s, p) ->
  if p < s.Length && sat s.[p] then succeedWith s.[p] (p + 1)
  else failAt p

// 'eos' succeeds if the position is beyond the last character.
//  Useful when testing if the parser have consumed the full string
let eos : Parser<unit> = Parser <| fun (s, p) ->
  if p < s.Length then failAt p
  else succeedWith () p

let anyChar       = satisfy (fun _ -> true)
let char ch       = satisfy ((=) ch)
let digit         = satisfy System.Char.IsDigit
let letter        = satisfy System.Char.IsLetter

// 'fail' is a parser that always fails
let fail<'T>      = Parser <| fun (s, p) -> failAt p
// 'return_' is a parser that always succeed with value 'v'
let return_ v     = Parser <| fun (s, p) -> succeedWith v p

// 'bind' let us combine two parser into a more complex parser
let bind t uf     = Parser <| fun (s, p) ->
  let (Parser tps) = t
  let tov, tp = tps (s, p)
  match tov with
  | None    -> None, tp
  | Some tv ->
    let u = uf tv
    let (Parser ups) = u
    ups (s, tp)

type ParserBuilder() =
  member x.Bind       (t, uf) = bind      t   uf
  member x.Return     v       = return_   v
  member x.ReturnFrom t       = t

// 'parser' enables us to combine parsers using 'parser { ... }' syntax
let parser = ParserBuilder()

// 'orElse' creates a parser that runs parser 't' first, if that is successful
//  the result is returned otherwise the result of parser 'u' is returned
let orElse t u    = Parser <| fun (s, p) ->
  let (Parser tps) = t
  let tov, tp = tps (s, p)
  match tov with
  | None    -> 
    let (Parser ups) = u
    ups (s, p)
  | Some tv -> succeedWith tv tp

let (>>=) t uf    = bind t uf
let (<|>) t u     = orElse t u

// 'map' runs parser 't' and maps the result using 'm'
let map m t       = t >>= (m >> return_)
let (>>!) t m     = map m t
let (>>%) t v     = t >>! (fun _ -> v)

// 'opt' takes a parser 't' and creates a parser that always succeed but
//  if parser 't' fails the new parser will produce the value 'None'
let opt t         = (t >>! Some) <|> (return_ None)

// 'pair' runs parser 't' and 'u' and returns a pair of 't' and 'u' results
let pair t u      = 
  parser {
    let! tv = t
    let! tu = u
    return tv, tu
  }

// 'many' applies parser 't' until it fails and returns all successful
//  parser results as a list
let many t =
  let ot = opt t
  let rec loop vs = ot >>= function Some v -> loop (v::vs) | None -> return_ (List.rev vs)
  loop []

// 'sepBy' applies parser 't' separated by 'sep'. 
//  The values are reduced with the function 'sep' returns
let sepBy t sep     =
  let ots = opt (pair sep t)
  let rec loop v = ots >>= function Some (s, n) -> loop (s v n) | None -> return_ v
  t >>= loop

// A simplistic integer expression parser

// 'pint' parses an integer
let pint = 
  let f s v = 10*s + int v - int '0'
  parser {
    let! digits = many digit
    return! 
      match digits with
      | [] -> fail
      | vs -> return_ (List.fold f 0 vs)
  }

// operator parsers, note that the parser result is the operator function 
let padd      = char '+' >>% (+)
let psubtract = char '-' >>% (-)
let pmultiply = char '*' >>% (*)
let pdivide   = char '/' >>% (/)
let pmodulus  = char '%' >>% (%)

// 'pmullike' parsers integers separated by operators with same precedence as multiply
let pmullike  = sepBy pint (pmultiply <|> pdivide <|> pmodulus)
// 'paddlike' parsers sub expressions separated by operators with same precedence as add
let paddlike  = sepBy pmullike (padd <|> psubtract)
// 'pexpr' is the full expression
let pexpr     =
  parser {
    let! v = paddlike
    let! _ = eos      // To make sure the full string is consumed
    return v
  }

Les expressions de calcul fournissent une syntaxe alternative à la chaîne Monads

En relation avec les monades sont des expressions de calcul F# ( CE ). Un programmeur implémente généralement un CE pour fournir une approche alternative à l'enchaînement des Monads, c'est-à-dire au lieu de cela: 

let v = m >>= fun x -> n >>= fun y -> return_ (x, y)

Vous pouvez écrire ceci: 

let v = ce {
    let! x = m
    let! y = n
    return x, y
  }

Les deux styles sont équivalents et cela dépend de la préférence du développeur.

Afin de démontrer comment implémenter un CE imaginez que toutes les traces incluent un identifiant de corrélation. Cet identifiant de corrélation aidera à corréler les traces appartenant au même appel. Ceci est très utile lorsque des fichiers journaux contiennent des traces d'appels simultanés.

Le problème est qu'il est fastidieux d'inclure l'ID de corrélation comme argument pour toutes les fonctions. Comme Monads permet de porter un état implicite, nous définirons un Log Monad pour masquer le contexte du journal (c'est-à-dire l'ID de corrélation).

Nous commençons par définir un contexte de journal et le type d'une fonction qui trace avec le contexte du journal: 

type Context =
  {
    CorrelationId : Guid
  }
  static member New () : Context = { CorrelationId = Guid.NewGuid () }

type Function<'T> = Context -> 'T

// Runs a Function<'T> with a new log context
let run t = t (Context.New ())

Nous définissons également deux fonctions de trace qui se connecteront avec l’identifiant de corrélation du contexte du journal: 

let trace v   : Function<_> = fun ctx -> printfn "CorrelationId: %A - %A" ctx.CorrelationId v
let tracef fmt              = kprintf trace fmt

trace est une Function<unit> qui signifie qu’elle sera transmise à un contexte de journal lorsqu’elle est appelée. A partir du contexte du journal, nous prenons l'identifiant de corrélation et le trace avec v

De plus, nous définissons bind et return_ et comme ils suivent les lois de la monade, cela forme notre Log Monad. 

let bind t uf : Function<_> = fun ctx ->
  let tv = t ctx  // Invoke t with the log context
  let u  = uf tv  // Create u function using result of t
  u ctx           // Invoke u with the log context

// >>= is the common infix operator for bind
let inline (>>=) (t, uf) = bind t uf

let return_ v : Function<_> = fun ctx -> v

Enfin, nous définissons LogBuilder qui nous permettra d’utiliser la syntaxe CE pour chaîner Log Monads. 

type LogBuilder() =
  member x.Bind   (t, uf) = bind t uf
  member x.Return v       = return_ v

// This enables us to write function like: let f = log { ... }
let log = Log.LogBuilder ()

Nous pouvons maintenant définir nos fonctions qui doivent avoir le contexte de journal implicite: 

let f x y =
  log {
    do! Log.tracef "f: called with: x = %d, y = %d" x y
    return x + y
  }

let g =
  log {
    do! Log.trace "g: starting..."
    let! v = f 1 2
    do! Log.tracef "g: f produced %d" v
    return v
  }

Nous exécutons g avec: 

printfn "g produced %A" (Log.run g)

Quelles impressions: 

CorrelationId: 33342765-2f96-42da-8b57-6fa9cdaf060f - "g: starting..."
CorrelationId: 33342765-2f96-42da-8b57-6fa9cdaf060f - "f: called with: x = 1, y = 2"
CorrelationId: 33342765-2f96-42da-8b57-6fa9cdaf060f - "g: f produced 3"
g produced 3

Notez que le CorrelationId est implicitement porté de run à g vers f ce qui nous permet de corréler les entrées du journal lors du dépannage.

CE a beaucoup plus de fonctionnalités mais cela devrait vous aider à définir votre propre CE : s.

Code complet: 

module Log =
  open System
  open FSharp.Core.Printf

  type Context =
    {
      CorrelationId : Guid
    }
    static member New () : Context = { CorrelationId = Guid.NewGuid () }

  type Function<'T> = Context -> 'T

  // Runs a Function<'T> with a new log context
  let run t = t (Context.New ())

  let trace v   : Function<_> = fun ctx -> printfn "CorrelationId: %A - %A" ctx.CorrelationId v
  let tracef fmt              = kprintf trace fmt

  let bind t uf : Function<_> = fun ctx ->
    let tv = t ctx  // Invoke t with the log context
    let u  = uf tv  // Create u function using result of t
    u ctx           // Invoke u with the log context

  // >>= is the common infix operator for bind
  let inline (>>=) (t, uf) = bind t uf

  let return_ v : Function<_> = fun ctx -> v

  type LogBuilder() =
    member x.Bind   (t, uf) = bind t uf
    member x.Return v       = return_ v

// This enables us to write function like: let f = log { ... }
let log = Log.LogBuilder ()

let f x y =
  log {
    do! Log.tracef "f: called with: x = %d, y = %d" x y
    return x + y
  }

let g =
  log {
    do! Log.trace "g: starting..."
    let! v = f 1 2
    do! Log.tracef "g: f produced %d" v
    return v
  }

[<EntryPoint>]
let main argv =
  printfn "g produced %A" (Log.run g)
  0


Modified text is an extract of the original Stack Overflow Documentation
Sous licence CC BY-SA 3.0
Non affilié à Stack Overflow