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]


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


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.

Leave a comment