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 Liquid Haskell

The Diff source code can we checked with Liquid Haskell.

Liquid Haskell 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 Liquid Haskell checks are appreciated but not required at this point.