YAHT: Computation class (note to self)

  • 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.

Share

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>