Global similarity (sequence alignment)
```> module GlobSim where

> import Array
> import List
```
The signature:
```> data Alignment = Nil Char               |
>                  D  Char Alignment      |
>                  I  Alignment Char      |
>                  R  Char Alignment Char
>                                            deriving (Eq, Show)
```
The yield grammar:
```> globsim alg f = axiom alignment where
>   (nil, d, i, r, h) = alg

>   alignment  = tabulated(
>                 nil <<< (char '\$')                    |||
>                 d   <<< achar -~~ alignment           |||
>                 i   <<<           alignment ~~- achar |||
>                 r   <<< achar -~~ alignment ~~- achar ... h)
```
Bind input:
```>   z         = mk f
>   (_,n)     = bounds z
>   achar     = acharSep' z '\$'
>   char      = char' z
>   tabulated = table n
>   axiom     = axiom' n
```
Enumeration algebra:
```> enum :: Globsim_Algebra Char Alignment
> enum = (nil, d, i, r, h) where
>   nil = Nil
>   d   = D
>   i   = I
>   r   = R
>   h   = id
```
Pretty printing algebra:
```> prettyprint :: Globsim_Algebra Char (String, String)
> prettyprint = (nil, d, i, r, h) where
>   nil _       = ("","")
>   d x (l,r)   = (x:l, gap:r)
>   i (l,r) x   = (gap:l, x:r)
>   r x (l,r) y = (x:l,y:r)
>   h           = id
>   gap         = '-'
```
Counting algebra:
```> count :: Globsim_Algebra Char Int
> count = (nil, d, i, r, h) where
>   nil s   = 1
>   d x s   = s
>   i s x   = s
>   r a s b = s
>   h []    = []
>   h xs    = [sum xs]
```
The scoring algebras:
```> wgap :: Globsim_Algebra Char Int
> wgap = (nil, d, i, r, h) where
>   nil a   = 0
>   d x s   = s + gap x
>   i s y   = s + gap y
>   r a s b = s + w a b
>   h []    = []
>   h xs    = [maximum xs]

>  -- simple definitions for gap and w:
>   gap x = (-1)
>   w a b = if a==b then 1 else (-1)

> unit :: Globsim_Algebra Char Int
> unit = (nil, d, i, r, h) where
>   nil a   = 0
>   d x s   = s - 1
>   i s y   = s - 1
>   r a s b = if a==b then s+1 else s-1
>   h []    = []
>   h xs    = [maximum xs]
```
The edit distance algebras:
```> unitDistance :: Globsim_Algebra Char Int
> unitDistance = (nil, d, i, r, h) where
>   nil a   = 0
>   d x s   = s + 1
>   i   s y = s + 1
>   r x s y = if x==y then s else s + 1
>   h []    = []
>   h xs    = [minimum xs]

> simpleLevenshteinDistance :: Globsim_Algebra Char Int
> simpleLevenshteinDistance = (nil, d, i, r, h) where
>   nil a   = 0
>   d x s   = s + 1
>   i   s y = s + 1
>   r x s y = if x==y then s else s + 2
>   h []    = []
>   h xs    = [minimum xs]
```
Algebra type:
```> type Globsim_Algebra alphabet answer = (
>   alphabet -> answer,                       -- nil
>   )
```
Algebra cross product:
```> infix ***
> (***) :: Eq answer1 =>
> alg1 *** alg2 = (nil, d, i, r, h) where
>    (nil1, d1, i1, r1, h1) = alg1
>    (nil2, d2, i2, r2, h2) = alg2
>
>    nil a = (nil1 a, nil2 a)
>    d x (s1,s2)   = (d1 x s1, d2 x s2)
>    i   (s1,s2) y = (i1 s1 y, i2 s2 y)
>    r x (s1,s2) y = (r1 x s1 y, r2 x s2 y)
>
>    h xs = [(x1,x2)| x1 <- nub \$ h1 [ y1 | (y1,y2) <- xs],
>                     x2 <-       h2 [ y2 | (y1,y2) <- xs, y1 == x1]]

```
For usage on your local machine: