Entries:
Comments:
Posts:

Loading User Information from Channel 9

Something went wrong getting user information from Channel 9

Latest Achievement:

Loading User Information from MSDN

Something went wrong getting user information from MSDN

Visual Studio Achievements

Latest Achievement:

Loading Visual Studio Achievements

Something went wrong getting the Visual Studio Achievements

Edmondo Pentangelo

Edmondo Pentangelo holoed

Niner since 2008

Coding for fun :))
  • Brian Beckman: The Zen of Stateless State - The State Monad - Part 1

    // 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

    Thank you Charles Smiley

    I've updated my profile:

    Edmondo Pentangelo
    Deutsche Bank 
    London, UK
  • Brian Beckman: The Zen of Stateless State - The State Monad - Part 1

    Thank you Brian Smiley

    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 Wink))

    HoloEd

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

    //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

    // 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

    
    // 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

    //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

    //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

    // 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


    //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…