Skip to content
Haskell and C implementation of practicable Aligned Induction
Haskell C
Branch: master
Clone or download

Latest commit

Fetching latest commit…
Cannot retrieve the latest commit at this time.


Type Name Latest commit message Commit time
Failed to load latest commit information.


The AlignmentRepa repository is a fast Haskell and C implementation of some of the practicable inducers described in the paper The Theory and Practice of Induction by Alignment at The AlignmentRepa repository depends on the Alignment repository for the underlying model framework. The slower implementations of some of the practicable inducers in the Alignment repository can be used to verify the correctness of equivalent faster implementations in AlignmentRepa.

The AlignmentRepa repository uses high performance arrays. Single-dimensional arrays are defined in the vector library. See Numeric Haskell. Multi-dimensional shape polymorphic parallel arrays are defined in the repa library. In addition, some compute-intensive array processing is implemented in C using the Foreign Function Interface. See also FFI and Data.Vector.Storable.

The induced models are made persistent using the JSON format which is implemented in the aeson library.

There are a couple of useful libraries that should be installed along with repa and aeson to ensure consistent package versions:

zlib: Compression and decompression in the gzip and zlib formats

cassava: A CSV parsing and encoding library


The Haskell implementation of fast Practicable Inducers discusses the implementation of the inducers using this repository.


The AlignmentRepa module requires the Haskell platform to be installed.

For example in Ubuntu,

sudo apt-get update
sudo apt-get install haskell-platform

Now the libaries not included in Haskell platform must be installed,

cabal update
cabal install repa repa-io vector-algorithms zlib cassava aeson aeson-pretty

Then download the zip files or use git to get the AlignmentRepa repository and the underlying Alignment repository -

git clone
git clone


Typically we wish to force compilation in ghci in order to have the highest performance. See Compiling to object code inside GHCi. Load AlignmentDevRepa to import the modules and define various useful abbreviated functions,

cd ../Alignment
rm *.o *.hi

cd ../AlignmentRepa
rm *.o *.hi

gcc -fPIC -c AlignmentForeign.c -o AlignmentForeign.o -O3
ghci -i../Alignment -i../AlignmentRepa ../AlignmentRepa/AlignmentForeign.o
:set -fobject-code
:set +m
:l AlignmentDevRepa

let aa = regdiag 2 2

rp $ aa
"{({(1,1),(2,1)},1 % 1),({(1,2),(2,2)},1 % 1)}"

Histogram (fromList [(State (fromList [(VarInt 1,ValInt 1),(VarInt 2,ValInt 1)]),1 % 1),(State (fromList [(VarInt 1,ValInt 2),(VarInt 2,ValInt 2)]),1 % 1)])

aaar (sys aa) aa
HistogramRepa {histogramRepasVectorVar = [VarInt 1,VarInt 2], histogramRepasMapVarInt = fromList [(VarInt 1,0),(VarInt 2,1)], histogramRepasArray = AUnboxed [2,2] [1.0,0.0,0.0,1.0]}

Note that if forcing compilation causes functions to be unresolved, for example,

rp $ Set.fromList [1,2,3]

<interactive>:9:1: Not in scope: Set.fromList


rp $ fudEmpty

<interactive>:10:6: Not in scope: fudEmpty

then either (a) import the modules explicitly, for example,

import qualified Data.Set as Set
import qualified Data.Map as Map
import Alignment

rp $ Set.fromList [1,2,3]

rp $ fudEmpty

or (b) interpret module AlignmentDevRepa by itself. Exit ghci and then delete AlignmentDevRepa.o,

rm AlignmentDevRepa.o

ghci -i../Alignment -i../AlignmentRepa ../AlignmentRepa/AlignmentForeign.o
:set +m
:l AlignmentDevRepa

rp $ Set.fromList [1,2,3]

rp $ fudEmpty
You can’t perform that action at this time.