Diff

This is an implementation of the standard diff algorithm in Haskell.

Time complexity is O(ND) (input length * number of differences). Space complexity is O(D^2). Includes utilities for pretty printing.

Building & testing

Build with

cabal build

Test with

cabal test

Benchmark with

cabal bench

Checking Diff with LiquidHaskell

The Diff source code can we checked with LiquidHaskell.

LiquidHaskell requires ghc version 9.14.1, and an SMT solver. We have tested the checks with the Z3 SMT solver (versions 4.16, and 4.15.1).

cd Diff-liquidhaskell && cabal build

The Diff-liquidhaskell package is a device to avoid the circular dependency between liquidhaskell and the Diff package.

flowchart LR
    Diff --> liquidhaskell --> liquidhaskell-boot --> Diff

Loading

Contributions that update the LiquidHaskell checks are appreciated but not required at this point.

Acknowledgments

The LiquidHaskell static checks were designed and implemented with the support of Tweag, a part of Modus Create. Learn more in this blog post.