We demonstrate how to build certain cyclic and other multi-linked structures in the lazy functional programming language Haskell. No explicit pointers are used in these constructions. Each task is accomplished by star...
详细信息
We demonstrate how to build certain cyclic and other multi-linked structures in the lazy functional programming language Haskell. No explicit pointers are used in these constructions. Each task is accomplished by starting with a suitable specification and then calculating the required program.
This article proposes a method for proving the correctness of graph algorithms by manipulating their spanning trees enriched with additional references. We illustrate this concept with a proof of the correctness of a ...
详细信息
ISBN:
(纸本)9783642205507
This article proposes a method for proving the correctness of graph algorithms by manipulating their spanning trees enriched with additional references. We illustrate this concept with a proof of the correctness of a (pseudo-)imperative version of the Schorr-Waite algorithm by refinement of a functional one working on trees. It is composed of two orthogonal steps of refinement - functional to imperative and tree to graph - finally merged to obtain the result. Our imperative specifications use monadic constructs and syntax sugar, making them close to common imperative languages. This work has been realized within the Isabelle/HOL proof assistant.
暂无评论