Edmondo Pentangelo

Brian Beckman: The Zen of Stateless State - The State Monad - Part 1

Dec 13, 2008 at 11:58 AM

// The List Monad in F#

#light

type List<'a> = List of ('a -> 'a list)

type ListMonad() =
    member o.Bind(  (m:'a list), (f: 'a -> 'b list) ) = List.concat( List.map (fun x -> f x) m )
    member o.Return(x) = [x]

let list = ListMonad()

let cartesian = list { let! x = [1..3]
                       let! y = [4..6]
                       return (x,y) }

printf "%A" cartesian

Brian Beckman: The Zen of Stateless State - The State Monad - Part 1
Dec 06, 2008 at 11:47 AM

Thank you Charles

I've updated my profile:

http://channel9.msdn.com/Niners/holoed/

Edmondo Pentangelo

Deutsche Bank

London, UK
Brian Beckman: The Zen of Stateless State - The State Monad - Part 1
Dec 06, 2008 at 11:43 AM

Thank you Brian

I love this stuff. I've been an OO developer for a long time and it is only thank to F# and videos like yours that I started appreciating the beauty of functional ideas. I think my coding at work is improving as a result of this exposure.

I plan to have exercise 10 ready before the end of the year ))

HoloEd

Brian Beckman: The Zen of Stateless State - The State Monad - Part 1

Dec 02, 2008 at 6:54 PM

//F# Monadic Parser - Calculator Example :))) 

// Grammar
//expr ::= expr addop term j term
//term ::= term mulop factor j factor
//factor ::= digit j ( expr )
//digit ::= 0 j 1 j : : : j 9
//addop ::= + j -
//mulop ::= * j /

let addOp = parser { let! _ = symb "+" 
                     return (+) } +++ parser { let! _ = symb "-" 
                                               return (-) } 
let mulOp = parser { let! _ = symb "*" 
                     return (*) } +++ parser { let! _ = symb "/" 
                                               return (/) }  
let digit = parser { let! x = token (sat (fun ch -> Char.IsDigit(ch)))
                     return Char.GetNumericValue(x) - Char.GetNumericValue('0') }

let rec expr   = chainl1 term addOp
and     term   = chainl1 factor mulOp
and     factor = digit +++ parser { let! _ = symb "("
                                    let! n = expr
                                    let! _ = symb ")"
                                    return n }
                                    
let parse s = match apply expr s  with
              | [] -> failwith "failed to parse"
              | (ret, _)::xs -> ret

Brian Beckman: The Zen of Stateless State - The State Monad - Part 1

Dec 02, 2008 at 6:51 PM

// F# Parsers combinators :))

//A parser which successfully consumes the first character
//if the argument string is non-empty, and fails otherwise.
let item = Parser (fun cs -> match cs with
                             | "" -> []
                             | cs -> [cs.[0], cs.Substring(1)])
                            
//A combinator sat that takes a predicate, and yields a parser that
//consumes a single character if it satisfies the predicate, and fails otherwise.
let sat p = parser { let! c = item
                     if p c then
                      return c }
                      
//A parser for specific characters
let char c = sat (fun s -> c = s)
                                            
//Parse a specific string
let rec stringp s = match s with
                    | "" -> parser { return [] }
                    | xs -> parser { let! c = char xs.[0]
                                     let! cs = stringp (xs.Substring(1))
                                     return c::cs }                        
                                                          
//The many combinator permits zero
//or more applications of p, while many1 permits one or more.
let rec many1 p = parser { let! x = p
                           let! xs = many p
                           return (x::xs) }
and many p = (many1 p) +++ parser { return [] }

                            
//Parse repeated applications of a parser p, separated by applications of a parser
//op whose result value is an operator that is assumed to associate to the left,
//and which is used to combine the results from the p parsers.
and chainl1 p op = 
    let rec rest a = parser { let! f = op
                              let! b = p
                              return! rest (f a b) } +++ parser { return a }
    parser { let! a = p
             return! rest a } 
           
//Parse a string of spaces.
let space = many (sat (fun s -> Char.IsWhiteSpace s))

//Parse a token using a parser p, throwing away any trailing space.
let token p = parser { let! a = p
                       let! _ = space
                       return a }

//Parse a symbolic token:
let symb cs = token (stringp cs)

//Apply a parser p, throwing away any leading space:
let apply p = extract (parser { let! _ = space
                                let! r = p
                                return r })

Brian Beckman: The Zen of Stateless State - The State Monad - Part 1

Dec 02, 2008 at 6:48 PM


// F# Parser Monad (http://www.cs.nott.ac.uk/~gmh/pearl.pdf)

type Parser<'a> = Parser of (string ->('a * string) list)

let extract(Parser(f)) = f

type ParserMonad() = 
        member b.Bind(p, f) = Parser (fun cs -> 
                                                let r = extract(p) cs
                                                let r' = List.map (fun (a,cs') -> extract(f a) cs') r
                                                List.concat r')
        member b.Return(x) = Parser (fun cs -> [x,cs])
        member b.Zero() = Parser (fun cs -> [])


let (++) p q = Parser(fun cs -> List.append (extract p cs) (extract q cs))
let (+++) p q = Parser(fun cs -> match (extract(p ++ q) cs) with
                                 | [] -> []
                                 | x::xs -> [x])

let parser = ParserMonad()

Brian Beckman: The Zen of Stateless State - The State Monad - Part 1

Nov 30, 2008 at 5:16 PM

//LINQ State Monad implementation


public delegate StateContentPair<T> StateMonad<T>(int state);

public static class LinqStateMonad
{
    public static StateMonad<U> Select<T, U>(this StateMonad<T> p, Func<T, U> selector)
    {
        return state => new StateContentPair<U>(selector(p(state).Content), state);
    }
    public static StateMonad<V> SelectMany<T, U, V>(this StateMonad<T> p, Func<T, StateMonad<U>> selector, Func<T, U, V> projector)
    {
        return state =>
        {
            var first = p(state);
            var second = selector(first.Content)(first.State);
            var content = projector(first.Content, second.Content);
            return new StateContentPair<V>(content, second.State);
        };
    }

    public static StateMonad<int> GetState()
    {
        return s => new StateContentPair<int>(s, s);
    }

    public static StateMonad<T> SetState<T>(int s1)
    {
        return s => new StateContentPair<T>(default(T), s1);
    }
}

Brian Beckman: The Zen of Stateless State - The State Monad - Part 1

Nov 30, 2008 at 5:05 PM

//LINQ Monadic Labelling of a Binary Tree

public static StateMonad<BTree> MLabel(BTree tree)
{
    var branch = tree as BBranch;
    var leaf = tree as BLeaf;

    StateMonad<BTree> ret = null;

    if (leaf != null)
    {
        var q = from x in LinqStateMonad.GetState()
                from f in LinqStateMonad.SetState<int>(x + 1)
                select new BLeaf { Content = leaf.Content, State = x };
        ret = s => { var r = q(s); return new StateContentPair<BTree>(r.Content, r.State); };
    }

    if (branch != null)
    {
        var q = from l in MLabel(branch.Left)
                from r in MLabel(branch.Right)
                select new BBranch() { Left = l, Right = r };
        ret = s => { var r = q(s); return new StateContentPair<BTree>(r.Content, r.State); };
    }

    return ret;
}

Brian Beckman: The Zen of Stateless State - The State Monad - Part 1

Nov 27, 2008 at 4:47 PM

// F# Monadically label n-ary tree

let MMap f xs = 
            let rec MMap' (f, xs', out) = 
                state {
                        match xs' with
                        | h :: t -> let! h' = f(h)
                                    return! MMap'(f, t, List.append out [h'])
                        | [] -> return out
                      }
            MMap' (f, xs, [])


let rec private MNNode (x) =
    match x with
    | NLeaf(c) -> state { let! x = GetState
                          do! SetState (x + 1)
                          return NLeaf(c,x) }
                         
    | NNode(xs) -> state { let! xs' = MMap MNNode xs
                           return NNode(xs')  } 
                    
let MNLabel x = Execute(MNNode(x))

Brian Beckman: The Zen of Stateless State - The State Monad - Part 1

Nov 25, 2008 at 6:34 PM


//F# State Monad

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

type StateMonad() = 
        member b.Bind(m, f) = State (fun s -> let r = match m with
                                                      | State f -> f s
                                              match r with
                                              | (v,s) -> match f v with
                                                         | State f -> f s)    
        member b.Return(x) = State (fun s -> x, s)

let state = StateMonad()

let GetState = State (fun s -> s, s)
let SetState s = State (fun _ -> (), s)  

let Execute m s = match m with
                  | State f -> let r = f s
                               match r with
                               |(x,_) -> x

See more comments…

Staff