Inside C# 4.0: dynamic typing, optional parameters, covariance and contravariance

Charles said:
Something that would be really cool would be launching a C9 screencast in VS and having the code in the video automatically written to your VS text editor. So, your text editor extensibly replaces the one in the video stream...
man, its been a while since briain tied my brain in a knot, ive missed that
Best way to attack the exercises is to open up the code samples and go through the C# code line-by-line, letter-by-letter, and compare it to the visio drawings. The transcription (modulo mistakes of course) is supposed to be faithful, one-to-one. The drawings are supposed to support the fundamental ideas that will help you crack the exercises. You may want to start each exercise by producing a new drawing from a copy of the old ones that reflects your ideas about how to proceed, then go over and write the code, maybe with a little back-and-forth to converge to a refined solution. Always keep copies of "where you started" because you will likely have some false starts.
Yes, those are cubes, but my collection is tiny compared to Erik Meijer's!
I have a question. I had assumed that the definition of "bad" would be "a function that has side effects". But Brian gives the key definition as of a mathematical function, which is one that returns the same value given the same arguments. This is much neater
because it means that you don't have to decide what "side effect" means (could mean a lot of things). But then I realised that this means that a mathematical function CAN have side effects! It just mustn't allow anything to affect what IT returns for a given
set of arguments - but it is okay for it to affect what other functions will return. Those other functions would not be mathematical, because they reveal the side effects. So a mathematical function doesn't reveal side effects via its return - this says nothing
about causing them.
So my question is, as long as "printf" returns the same value for a given argument, what does it matter if it has the side effect of printing text out to the console? Why can't I add it to my program harmlessly? Previously I was using all mathematical functions,
now I'm adding a printf call somewhere, that's also a mathematical function, so nothing has changed.
(Or can I deduce from this that haskell's equivalent of printf returns a new modified instance of the console every time you call it...? Semi-serious question!)
// F# Monadic tree labeller (using State Monad from http://cs.hubfs.net/forums/thread/7472.aspx) let rec private mNode (x) = match x with | Leaf(c) -> state { let! x = GetState do! SetState (x + 1) return Leaf(c,x) } | Node(l,r) -> state { let! l = mNode(l) let! r = mNode(r) return Node(l,r) } let mLabel x = Exec(mNode(x)) // F# Non-Monadic manual state passing tree labeller let Label a s = let rec Lab' a s =
match a with
|Leaf(c) -> (Leaf(c,s), s + 1)
|Node(l,r) -> let l' = Lab' l s
let r' = Lab' r (snd l') (Node(fst l', fst r'), (snd r'))
fst (Lab' a s)
//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
I see - so Haskell says "trust me, this won't last" and Haskell is undoubtedly correct!
// 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))
//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; }
//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); } }
// 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()
// 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 })
//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
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
// 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
"So... any solutions available for the exercises above?" <| Geez! Maybe I should look to see if pages of comments exist before displaying my stupidity to the world. Great work holoed!
Here's my solution to exercise 2 using F#:
The type defs:
type Rect =
{ Height: float;
Width: float;
Top: float;
Left: float }
with override r.ToString() = String.Format("Height: {0}, Width: {1}, Top: {2}, Left: {3}", r.Height, r.Width, r.Top, r.Left)
type Tree<'a> =
| Leaf of 'a
| Branch of Tree<'a> * Tree<'a>
// The show method already takes into account the tuples,
// unlike the show method that is overloaded in the C# version.
let show tree =
let rec printTree tree level =
let spacing = new string(' ', level * indentation)
printf "%A" spacing
match tree with
| Leaf(label, contents) ->
let labelString = label.ToString()
printfn "Leaf: %s, Contents: %A" labelString contents
| Branch(left, right) ->
printfn "Branch: "
printTree left (level + 1)
printTree right (level + 1)
printTree tree 0
The state monad builder:
(* StateMonad *)
type State<'S, 'a> = State of ('S -> 'S * 'a)
(* StateBuilder Bounder *)
let boundTree tree seed leftUpdater rightUpdater =
let rec labelTree t updater =
match t with
| Leaf(c) -> state { let! s = getState
let (next, curr) = updater s
do! setState next
return Leaf(curr, c) }
| Branch(l, r) -> state { let! l = labelTree l leftUpdater
let! r = labelTree r rightUpdater
return Branch(l, r) }
exec (labelTree tree leftUpdater) seed
let eval sm s =
match sm with
| State f -> f s |> fst
let exec sm s =
match sm with
| State f -> f s |> snd
The demo tree:
let demoTree = Branch(
Leaf("A"),
Branch(
Branch(
Leaf("B"),
Leaf("C")),
Leaf("D")))
The updaters and execution code:
let leftBounder =
fun (depth, rect) -> let newDepth = depth + 1.0
let multiplier = 2.0 * newDepth
( (newDepth,
{ Height = rect.Height
Width = rect.Width / multiplier
Top = rect.Top
Left = rect.Left + rect.Width / multiplier }),
{ Height = rect.Height
Width = rect.Width / multiplier
Top = rect.Top
Left = rect.Left } )
let rightBounder =
fun (depth, rect) -> let newDepth = depth - 1.0
( (newDepth,
{ Height = rect.Height
Width = rect.Width * 2.0
Top = rect.Top
Left = rect.Left + rect.Width }),
rect )
let initialDepth = 0.0
let initialRect = { Height = 100.0
Width = 100.0
Top = 0.0
Left = 0.0 }
let ex2Seed = (initialDepth, initialRect)
printfn "Bound tree to rects"
let bTree = boundTree demoTree ex2Seed leftBounder rightBounder
show bTree
This works, but I imagine there must be a better way. I'm open to suggestions.
This looks very nice. I don't see any ways right off the top of my head to make it shorter (shorter is almost always better
Thanks for including the visio diagrams. Will print them and look at the code...
Does the style of logic/flow diagraming (ie. in Visio) have a special name? It seems like a good way to reason about the problem and was hopinh to find out more information about it?