YAHT: Computation class (note to self)
- Magnus Therning
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
:
src == dst
is a successful end state. The result is[src]
wrapped insuccess
.- Running out of edges in the inner function (
search'
) is an unsuccessful end state. The result is a string wrapped infailure
. - The first recursive step for
search'
(src == u
) walks us one step on the way (u
->v
).- The call to
searchAll
returns a wrapped result (i.e. path(s) fromv
todst
), - we
augment
this result by stickingu
in front of it (for the list-basedComputation
that meansmap
pingu:
on each path, for the others it means dropping the “wrapper type” and calling(u:)
on the actual result), then - we wrap it all up again.
- Finally we
combine
it with the result of asearch'
on the other edges. Thecombine
in the case of lists is concatenation, i.e. we add our list of current results to all other results. For the other twocombine
is a “pick first” operation.
- The call to
- 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.