therning.org/ magnus

• Computation wraps a result of a function in a type.
• augment strips the type, applies a function to the result. The function must wrap the end result in the type again.
• combine “joins” two results together.

Making [] and instance of Computation illustrates it the best. Maybe and Failable are a bit “funny” because the combine works like or, i.e. they take the first success x and run with it.

Getting searchAll to work requires a type definition.

 searchAll :: Graph  v e -> Int Int -> Maybe [Int]

or

 searchAll :: Graph  v e -> Int Int -> Failable [Int]

or

 searchAll :: Graph  v e -> Int Int -> [[Int]]

How I think about searchAll:

1. src == dst is a successful end state. The result is [src] wrapped in success.
2. Running out of edges in the inner function (search') is an unsuccessful end state. The result is a string wrapped in failure.
3. The first recursive step for search' (src == u) walks us one step on the way (u -> v).
   1. The call to searchAll returns a wrapped result (i.e. path(s) from v to dst),
   2. we augment this result by sticking u in front of it (for the list-based Computation that means mapping u: on each path, for the others it means dropping the “wrapper type” and calling (u:) on the actual result), then
   3. we wrap it all up again.
   4. Finally we combine it with the result of a search' on the other edges. The combine in the case of lists is concatenation, i.e. we add our list of current results to all other results. For the other two combine is a “pick first” operation.
4. The other recursive step for search' simply looks for results in all remaining edges since the current edge isn’t part of our path.

Now I can go on to read about monads.

Close Bookmark and Share This Page

Save to Browser Favorites / Bookmarks

Ask backflip blinklist BlogBookmark Bloglines BlogMarks Blogsvine BuddyMarks BUMPzee! CiteULike co.mments Connotea del.icio.us

Digg diigo DotNetKicks DropJack dzone Facebook Fark Faves Feed Me Links Friendsite folkd.com Furl Google

Hugg Jamespot Jeqq Kaboodle kirtsy linkaGoGo LinkedIn LinksMarker Ma.gnolia Mister Wong Mixx MySpace MyWeb

Netvouz Newsvine oneview OnlyWire PlugIM Propeller Reddit Rojo Segnalo Shoutwire Simpy Slashdot Sphere

Sphinn Spurl Squidoo StumbleUpon Technorati ThisNext Twitter Webride Windows Live Worlds Movies Yahoo!

Email This to a Friend

Copy HTML: 

 If you like this then please subscribe to the RSS Feed.

Powered by Bookmarkify™

More »