Thanks to everyone who attended – hope you got something out of it (besides the free food and drinks…).
Here are the slides I used, as well as the (completed) demo project. There are some extra slides and some extra parts to the demo which I didn’t present. Apparently the whole thing will also appear on MSDN chopsticks, at which point I’ll update this post with the link.
I’m not in the habit of posting links, but this essay by Willam R. Cook on the difference between ADTs and objects made such an excellent and humbling read... Humbling because in my arrogance I had assumed that I knew the difference – after all this is basic stuff. Excellent because despite the humbling experience, it’s a very enjoyable read.
Enjoy.
| Share this post : |  |  |  |  |  |  |  |
Sorry for the horrendous search keyword-driven title, but I’ve been trying to get this to work for ages.
Here’s a step by step guide, along with some potential pitfalls.
1) Download TortoiseHg. I used 0.9.1.1. with Mercurial 1.4.1. Do not use the windows Mercurial command line only distribution – we’ll need to modify a zip file later and for some reason the zip file with the command line distribution cannot be modified with either WinRar, Winzip or 7-zip.
2) Install TortoiseHg as usual.
3) Download dulwich 0.4.0.
4) Add the directory called ‘dulwich’ inside the dulwich download (the one with the file __init__.py in it) to the library.zip file in the TortoiseHg folder (normally just C: \Program Files\TortoiseHg) using your favorite zip utility.
5) Download the tip of an up to date hg-git fork. I used http://bitbucket.org/gwik/hg-git/.
6) Put the hg-git directory in the TortoiseHg directory.
7) Add the following lines to your Mercurial.ini file:
bookmarks =
hggit = C:\Program Files\TortoiseHg\hg-git\hggit
That’s it. I finally managed to clone the ClojureClr repository with the above install:
> hg clone git://github.com/richhickey/clojure-clr.git destination directory: clojure-clr.git importing Hg objects into Git Counting objects: 4001, done. Compressing objects: 100% (1816/1816), done. Total 4001 (delta 3153), reused 2774 (delta 2148) importing Git objects into Hg at: 0/307 at: 100/307 at: 200/307 at: 300/307 updating to branch default 313 files updated, 0 files merged, 0 files removed, 0 files unresolved
And with this we’re back to functional programming languages ;)
I didn’t test this any further.
Good luck!
| Share this post : | |
|
|
|
|
|
|
Last time I showed a few ways of implementing insert into an unbalanced binary tree, as an implementation of a set data structure. This post adds an implementation that is similar in functionality to the example that uses call/cc, but using the more familiar exceptions to avoid allocating elements needlessly:
let insertExc x t = try let rec insertRec x t = match t with | Empty -> cont { return Elem(empty,x,empty) } | Elem (left,e,right) when x < e -> cont { let! t' = insertRec x left return Elem(t',e,right) } | Elem (left,e,right) when x > e -> cont { let! t' = insertRec x right return Elem(left,e,t') } | Elem _ -> failwith "alreadyExists" insertRec x t id with e –> t
A comment on the last post indicated that exceptions should be much slower (on .NET, at least) than the callCC approach. Furthermore, I said that callCC was necessary to avoid re-allocating elements needlessly on the search path to an already existing element. Let’s put these claims to the test with a simple benchmark:
let longList = let r = new System.Random() let l = 100000 [ for i in 1..l -> r.Next(0,l) ] let insertALot f nbRuns = for i in 1..nbRuns do longList |> List.fold (fun t elem -> f elem t) empty
How many duplicates are in the long list (i.e. how much can we expect to gain by using callCC/exceptions):
> longList |> Seq.distinct |> Seq.length;; val it : int = 63362So about 35% duplicates. The results:
> insertALot insert 100;; Real: 00:01:38.717, CPU: 00:01:37.516, GC gen0: 2247, gen1: 520, gen2: 8 val it : unit = () > insertALot insert' 100;; Real: 00:01:44.583, CPU: 00:01:37.251, GC gen0: 4050, gen1: 1444, gen2: 18 val it : unit = () > insertALot insertM 100;; Real: 00:02:35.101, CPU: 00:02:29.792, GC gen0: 12698, gen1: 1875, gen2: 24 val it : unit = () > insertALot insertCallCC 100;; Real: 00:01:09.410, CPU: 00:01:02.540, GC gen0: 12149, gen1: 7, gen2: 0 val it : unit = () > insertALot insertExc 100;; - Interrupt
Observe that:
| Share this post : | Technet! |
del.icio.us it! |
del.iri.ous! |
digg it! |
dotnetkicks it! |
reddit! |
technorati! |
Prompted by exercise 2.3 in Purely Functional Data Structures, by Chris Okasaki.
type Tree<'a> = Empty | Elem of 'a Tree * 'a * 'a Tree let empty = Empty
let rec insert x t = match t with | Empty -> Elem(empty,x,empty) | Elem (left,e,right) when x < e -> Elem (insert x left,e,right) | Elem (left,e,right) when x > e -> Elem (left,e, insert x right) | Elem _ –> t
let insert' x t = let rec cont x t k = match t with | Empty -> k (Elem(empty,x,empty)) | Elem (left,e,right) when x < e -> cont x left (fun t' -> k <| Elem (t',e,right)) | Elem (left,e,right) when x > e -> cont x right (fun t' -> k <| Elem (left,e,t')) | Elem _ -> k t cont x t id
type Cont<'a,'r> = ('a -> 'r) -> 'r type ContBuilder() = member x.Return (a):Cont<'a,'r> = fun k -> k a member x.Bind (c:Cont<'a,'r>, f:'a -> Cont<'b,_>) = (fun k -> c (fun a -> f a k)) member this.Delay(f) = f() let cont = ContBuilder()
let insertM x t = let rec insertRecM x t = match t with | Empty -> cont { return Elem(empty,x,empty) } | Elem (left,e,right) when x < e -> cont { let! t' = insertRecM x left return Elem(t',e,right) } | Elem (left,e,right) when x > e -> cont { let! t' = insertRecM x right return Elem(left,e,t') } | Elem _ -> cont { return t } insertRecM x t id
let callCC (f:('a -> Cont<'b,'r>) -> Cont<'a,'r>) : Cont<'a,'r> = fun k -> f (fun a _ -> k a) k
let insertCallCC x t = callCC (fun alreadyExists -> let rec insertRecCallCC x t = match t with | Empty -> cont { return Elem(empty,x,empty) } | Elem (left,e,right) when x < e -> cont { let! t' = insertRecCallCC x left return Elem(t',e,right) } | Elem (left,e,right) when x > e -> cont { let! t' = insertRecCallCC x right return Elem(left,e,t') } | Elem _ -> alreadyExists t insertRecCallCC x t ) id
Please note that the complexity of the last implementation is not obfuscation – it avoids recreating nodes on the path to an already existing element (exercise 2.3 actually asks to do it using exceptions, which works just as well).
| Share this post : | Technet! |
del.icio.us it! |
del.iri.ous! |
digg it! |
dotnetkicks it! |
reddit! |
technorati! |
I found out about Ohloh recently and decided to play around with it by adding FsCheck. From FsCheck’s Ohloh page we learn that:
It seems that the appraisal of an open source project can not be replaced by a small shell script…
Anyway, it’s nice to see how many related projects there are (and how many projects in general). If you’re in the neighborhood, come say hi, add a rating, add a user, whatever…
